前言
本文主要介绍插入排序和能略微提升其性能的代码细节，以及插入排序的改进——希尔排序
一、插入排序
先上代码：
//原始插入排序
void originInsertSort(vector<int> iv) {
for (size_t i = 1; i < iv.size(); ++i) {
//不断交换直至 a[i]>=a[i-1]
for (size_t j = i; i != 0 && iv[j] < iv[j - 1]; --j) {
swap(iv[j], iv[j - 1]);
}
}
}
插入排序是通过将 0 到 n-1 中每一个 i ，将 a[i] 与 a[0] 至 a[i-1] 中比它小的数依次交换。排序从左往右进行，因此 i 左边的元素都是有序的，当 i 到末尾时，整个数组就都是有序的了。
插入排序的时间复杂度和数组元素一开始的顺序有关，最好情况下 (元素已排好序)，只需要 n-1 次比较和0次交换即可完成 (O(N)级)。而在最坏情况下(元素完全逆序)，需要Σ (n-1）次比较和相同次数的交换 (O(N²)级)。
二、细节改进
在原始的插入排序代码中，内循环为了防止循环到最后时的数组溢出，每次都需要判断 i 是否不为0，(平均需要判断n²/4次)。而在交换时，需要两次从数组中取数。这些无疑增加了不必要的时间开销。对此我们可以进行一些细节改进：先用选择排序将第一位的数排好作为哨兵 (用选择排序只找出第一位只需要n-1次判断和1次交换)，来去除内循环的判0。将交换操作改为右移操作，以在每次交换时减半访问数组的次数。
这些细节虽然不能让算法在整体的时间复杂度上有所改进，但是实际运行时可以真正地减少时间开销。
上代码：
//哨兵不交换插入排序
void insertSort(vector<int>& intVe) {
if (intVe.size() == 0) { return; }
unsigned tempMin = 0;
for (size_t i = 1; i < intVe.size(); ++i) {
if (intVe[tempMin] > intVe[i]) {
tempMin = i;
}
}
swap(intVe[0], intVe[tempMin]);
for (size_t i = 2; i < intVe.size(); ++i) {
size_t j = i;
int temp = intVe[j];
for (; intVe[j - 1] > intVe[j]; --j) {
intVe[j] = intVe[j - 1];
}
intVe[j] = temp;
}
}
经数据实验，对于10万个随机double，原始插入排序所需时间是改进后所需时间的1.1倍。
三、希尔排序
相比一个一个比较并交换的插入排序，希尔排序对其进行了改进。交换不相邻的元素对数组局部进行排序，在最后用插入排序将局部有序的数组进行排序。
希尔排序的思想是使数组中任何间隔为h的元素都是有序的。在进行排序时，如果h很大，我们就可以将元素移动的相对于原位置很远的地方，为接下来的小一点的h排序创造方便。在最后，h缩小为1时，所需排序的数组和原来相比已经有序多了，这时进行插入排序（h为1的希尔排序）所需时间会大大降低。这就是希尔排序。
上代码：
void shellSort(vector<int>& intVe) {
unsigned stepValue = 1;
size_t vsize = intVe.size();
while (3 * stepValue < vsize) { stepValue = stepValue * 3 + 1; }//h = 1,4,13,40......
while (stepValue >= 1) {
for (unsigned i = stepValue; i < vsize; ++i) {
for (unsigned j = i; j >= stepValue && intVe[j] < intVe[j - stepValue]; j -= stepValue) {
swap(intVe[j], intVe[j - stepValue]);
}
}
stepValue /= 3;
}
}
希尔排序的时间复杂度主要和h相关，目前最好的h增量序列是Sedgewick 提出的增量序列。
公式为：
$$
hi=max(9∗4j−9∗2j+1,4k−3∗2k+1)
$$
具体数据为：
1，5，19，41，109，209，505，929，2161，3905，8929，16001，36289，64769，146305，260609，587521，1045505，2354689，4188161，9427969，16764929，37730305，67084289，150958081，268386305，603906049，1073643521
可以直接打表
鸣谢：Algorithm(4th)
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
