插入排序与希尔排序详解
一、插入排序
1. 算法思想
插入排序类似于打扑克牌的过程，将一张新牌插入到已有序的序列中。每次取一个数据 x，与前面的数据一一比较大小：若 x 比前一个数据小，则继续向前比较；若 x 比前一个数据大，则插入到这个数据的后面。
2. 实现思路
由算法可知，数据 x 前面的序列都是有序的，故每一次只需要将 x 插入其中即可。
- 第一步：给定下标范围 [0, end] 区间是有序的，tmp 为要插入的数据的值，即下标为 end + 1 所对应的值。
- 第二步：将下标为 end 所对应的值与 tmp 比较。若 tmp 比前一个数据小，则 tmp 就再向前一个数比较；若 tmp 比前一个数据大，则 tmp 就插入到这个数据的后面。
- 第三步：循环遍历整个数组，直到数组全部插入进去。
3. 代码演示
void InsertSort(int* a, int n) {
for (int i = 0; i < n - 1; i++) {
int end = i;
int tmp = a[end + 1];
while (end >= 0) {
if (tmp < a[end]) {
a[end + 1] = a[end];
end--;
} else {
break;
}
}
a[end + 1] = tmp;
}
}
二、希尔排序
1. 算法思想
希尔排序相当于间隔插入排序 n 次。每一次都越来越接近有序数组，直到最后一次排成有序。当 gap 为 1 时，就是普通的插入排序。
2. 实现思路
（1）分组
每次排序并不是一个一个排，而是每间隔几个数据成一组来排序。一组一组排，这组排完就到下一组，直到全部排完。
（2）预排序
分成了几组后，每一组就开始插入排序，称为预排序。预排序的主要功能就是让一个数组接近有序，为了给后面的插入排序节省大量的时间。
（3）最终排序
在排序完多组数据后，数组已经很接近有序，现在只需要用插入排序排最后一次收尾就行了。
（4）gap 的取值
gap 的值在排序过程中是不断发生变化的。根据经验，当 gap 为 n / 3 时，排序较快。因此，在函数外面再套一层循环，使 gap 动态变化，且最后一次循环的 gap 值为 1，恰好能完成一次普通的插入排序。
改进逻辑：gap = gap / 3 + 1。
3. 代码演示
{
gap = n;
(gap > ) {
gap = gap / + ;
( i = ; i < n - gap; i++) {
end = i;
tmp = a[end + gap];
(end >= ) {
(tmp < a[end]) {
a[end + gap] = a[end];
end -= gap;
} {
;
}
}
a[end + gap] = tmp;
}
}
}
