数据结构 - 2-路插入排序 具体解释 及 代码(C++)
2024-10-12 05:35:27
2-路插入排序 具体解释 及 代码
本文地址: http://blog.csdn.net/caroline_wendy/article/details/24267679
2-路插入排序的思想非常有意思:
通过一个辅助的循环数组, 假设大于最大的元素, 则插入至尾部, 假设小于最小的元素, 则插入至头部,
假设在两者之间, 採用折半查找的方式,移动一部分的元素;
设计到循环数组的中间值的查找和数据移动的问题.
因为折半查找能够降低比較次数,
首尾插入又不须要移动元素, 即移动次数约为[(n^2)/8], 有1/2的元素不须要移动, 每次移动(1/2*1/2), 所以移动次数为[(n^2)/8];
可是须要n个辅助空间, 时间复杂度扔是O(n^2);
代码例如以下:
/*
* test.cpp
*
* Created on: 2014.04.21
* Author: Spike
*/ /*eclipse cdt, gcc 4.8.1*/ #include <iostream>
#include <deque> void print(const std::deque<int>& L) {
for(auto i: L) {
std::cout << i << " ";
} std::cout << std::endl;
} void insertSort(std::deque<int>& L)
{
int first(0), final(0);
std::size_t n(L.size()); std::deque<int> D(n); D[0] = L[0]; for(std::size_t i=1; i<n; ++i) {
if (L[i] < D[first]) { //小于最小元素
first = (first-1+n)%n;
D[first] = L[i];
print(D);
} else if (L[i] > D[final]) { //大于最大元素
final = (final+1+n)%n;
D[final] = L[i];
print(D);
} else {
//折半查找
int low(0), high((final-first)%n);
int temp(first), end(high);
while (low <= high) {
int m = (low + high)/2;
if (L[i] < D[(m+temp)%n])
high = m-1;
else
low = m+1;
}
for (int j=end; j>=high+1; --j) {
D[(j+temp+1)%n] = D[(j+temp)%n];
}
D[(high+temp+1)%n] = L[i];
final = (final+1+n)%n;
print(D);
}
} //复制数组
for (std::size_t k=0; k<n; k++) {
L[k] = D[(first+k)%n];
}
} int main(void)
{
std::deque<int> L = {9, 3, 2, 4, 5, 8, 7, 6};
print(L);
insertSort(L);
print(L);
return 0;
}
输出:
9 3 2 4 5 8 7 6
9 0 0 0 0 0 0 3
9 0 0 0 0 0 2 3
4 9 0 0 0 0 2 3
4 5 9 0 0 0 2 3
4 5 8 9 0 0 2 3
4 5 7 8 9 0 2 3
4 5 6 7 8 9 2 3
2 3 4 5 6 7 8 9
最新文章
- 学习Maven之Cobertura Maven Plugin
- Java枚举类型getClass和getDeclaringClass区别(未完待续)
- java web 学习 --第三天(Java三级考试)
- SAP S4 Finance6个支持企业实时财务管理的主要创新领域
- RVM 解决 Ruby 的版本问题
- Careercup - Google面试题 - 5680330589601792
- 查看mysql存储引擎
- BeanPostProcessor 的使用,实现在对象初始化之前或者之后对对象进行操作
- Unity中使用RequireComponent,没有添加上组件
- PHP 学习笔记 (三)
- 【BZOJ3110】【整体二分+树状数组区间修改/线段树】K大数查询
- Python重写C语言程序100例--Part9
- ES6之Proxy及Proxy内置方法
- 如何在joomla上展示word,pdf,xlsx,ppt
- nginx中root和alias的区别
- Shader、Draw Call和渲染管线(Rendering Pipeline)
- Dynamic Programming | Set 1 (Overlapping Subproblems Property)
- 服务 AIDL 定向tag IPC Parcelable 案例 MD
- wcf 数值类型赋值不能的问题解决
- ubuntu安装ruby的几种方法总结
热门文章
- 正余弦信号的DFT频谱分析
- golang 引用相对路径package
- html5模拟平抛运动
- DOM对象之document对象
- 沉浸式Web初体验
- Xcode 5.0.1安装插件:规范注释生成器VVDocumenter + OSX 10.9.2
- iOS-如何让xcode自动检查内存泄露
- jquery.timers使用说明
- SharePoint 设置客户端上传文件大小
- 关于android studio 出现Error:Execution failed for task &#39;:app:preDebugAndroidTestBuild&#39;. 的解决办法