本篇博客来梳理两种常见排序算法：插入排序与希尔排序
常见的排序算法如图

写排序算法的原则：先写单趟，再写整体

一、直接插入排序

1．算法思想

先假定第一个数据有序，把第二个数据插入；再假设前两个数据有序，把第三个数据插入…以此类推，直到整个序列有序

2．具体操作（以排成升序为例）

（1）单趟：针对单个数据

假设[0,end]有序，处理end+1处数据（用tmp存起来，原因：挪数据的时候会覆盖）,依次与前面的数比，用while循环控制

• tmp更大：插入
• tmp更小：挪数据，同时- -end
  

程序结构如下

while(end>=0)
{if(tmp更小)//挪数据;--end;elsebreak;
}
//插入数据

注意：如果处理最小的数据，end会是-1（数据要插入到a[0]的位置）

（2）单趟变整体：用for循环控制end从0->n-2

end最大是n-2的原因：要动end+1处数据，保证不越界

（3）具体代码实现

// 直接插入排序（假设排成升序）
void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){//单趟int end = i;//end最大是n-2int tmp = a[end + 1];//end+1最大是n-1while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];//往后挪数据--end;}else{break;}}a[end + 1] = tmp;//插入数据}
}

3．特性总结

（1）时间复杂度：o(N²)
（2）空间复杂度：o(1)
（3）稳定性：稳定
（4）元素集合越接近有序，算法效率越高

二、希尔排序（缩小增量排序）

1.算法思想

先对整个序列进行预排序，使数组接近有序，最后进行直接插入排序的时候数组已经很接近有序，因此可以大大提升算法的效率

2.具体操作（以排成升序为例）

（1）第一步：预排序（让数组接近有序）——本质：gap>1的插入排序

取gap==3，把整组数据分成了3组
①单趟：处理一次之后黄色分组边界上的数字（9，5，8，5）就有序了，相当于对9，5，8，5进行插入排序，只不过中间跨越了gap这么多数据

//以下两层循环实际上就是直接插入排序的变种，把1换成了gap
for (int j = 0; j < n - gap; j+=gap)
{//单趟int end = j;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + 1] = tmp;
}

对比一下插入排序的代码，就是把1换成了gap
②单趟变整体——处理红色和蓝色的组别（在外面再用一层for循环控制）

//以下两层循环实际上就是直接插入排序的变种，把1换成了gap
for(int i = 0;i < gap; i++)
{for (int j = 0; j < n - gap; j+=gap){//单趟int end = j;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + 1] = tmp;}
}

三层循环看起来太多了，有时候可能会不好分析，于是就可以对（1）（2）进行优化
上面代码的逻辑：先处理黄色组，再处理红色组，最后处理蓝色组，其中对红色组和蓝色组的处理需要在最外层套入第三层循环
优化操作：“每组并着走”，而不是像上面那样“一组一组来”，把最外层循环去掉，然后第二层循环中j+=gap改成j++，处理顺序变成：黄->红->蓝->黄->红->蓝…

		for (int j = 0; j < n - gap; j++)//j+=gap改成了j++{//单趟int end = j;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + 1] = tmp;}

（2）第二步：插入排序——gap==1的插入排序

注意：gap越大，大的就更快跳到后面，小的就更快跳到前面，但不那么有序
gap越小，跳得更慢，但更有序
所以：gap要不断变小，直到最后变成1，这样最终插入排序处理的序列就更有序——再来一层循环控制gap(此处对上面优化版的代码进行操作，否则四层循环看着都晕了)

常见调整方式：gap=gap/3+1（保证最后一个gap是1）
此处没有单独写插入排序的原因：gap最后会迭代成1，此时执行的就是直接插入排序
至此，完整的希尔排序代码就出来了

（3）具体代码实现

// 希尔排序（假设排成升序）
void ShellSort(int* a, int n)
{//预排序int gap = 3;while(gap > 1)//外面再来一层循环，实现gap的迭代{gap = gap / 3 + 1;//保证最后一个gap是1//以下两层循环实际上就是直接插入排序的变种，把1换成了gapfor (int j = 0; j < n - gap; j++){//单趟int end = j;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + 1] = tmp;}}
}

3．特性总结

（1）希尔排序是对直接插入排序的优化
（2）gap>1时是预排序，目的是让数组更接近有序。当gap==1的时候，数组已经接近有序了，此时进行直接插入排序就会很快，性能得到了优化
（3） 希尔排序时间复杂度计算难度大，限于本人水平，只能在这里写个结论，大约是o(N^1.3)
（4）稳定性：不稳定