插入排序
插入排序的核心思想类似于整理扑克牌。假设手中已经有一组有序牌，每次从待排序序列中取出一张牌（tmp），将其插入到前面有序序列的合适位置。
算法思想
数据 x 前面的序列都是有序的，每一次只需要将 x 插入其中即可。具体来说，给定下标范围 [0, end] 区间是有序的，tmp 为要插入的数据的值，即下标为 end + 1 所对应的值。
将下标为 end 所对应的值与 tmp 比较：
- 若
tmp比前一个数据小，则tmp就再向前一个数比较； - 若
tmp比前一个数据大，则tmp就插入到这个数据的后面。
循环遍历整个数组，直到数组全部插入进去。
代码实现
// 插入排序
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;
}
}
希尔排序
希尔排序是插入排序的优化版本。它通过引入增量（gap）将数组分组，先进行'预排序'，让数据整体趋向有序，最后再用 gap=1 的插入排序收尾。
算法思想
当你看完原理图会发现，希尔排序和插入排序很相似。只不过，希尔排序相当于间隔插入排序 n 次，而每一次都越来越接近有序数组，直到最后一次排成有序。
实现思路
分组
每次排序并不是一个一个排，而是每间隔几个数据成一组来排序。一组一组排，这组排完就到下一组，直到全部排完。这里先假设分成 3 组数据进行排序，也就是每隔 2 个数据成一组。
预排序
分成了几组后，每一组就开始插入排序，称为预排序。预排序的主要功能就是让一个数组接近有序，为了给后面的插入排序节省大量的时间。
最终排序
现在，在排序完三组数据后，我们的数组已经很接近有序，所以现在只需要用插入排序排最后一次收尾就行了。
gap 的取值
前面代码中的 gap 取值定为了 3，但这不可能对于每个数组都适应。根据实验发现，当 gap 为 n / 3 时，排序最快。所以，在排序的过程中，gap 的值是不断发生变化的。
