本文主要是介绍6.1排序——插入排序与希尔排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本篇博客来梳理两种常见排序算法：插入排序与希尔排序
常见的排序算法如图
写排序算法的原则：先写单趟，再写整体
一、直接插入排序
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）稳定性：不稳定
这篇关于6.1排序——插入排序与希尔排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
