本篇博客来梳理两种常见排序算法：插入排序与希尔排序
常见的排序算法如图
写排序算法的原则：先写单趟，再写整体
一、直接插入排序
1．算法思想
先假定第一个数据有序，把第二个数据插入；再假设前两个数据有序，把第三个数据插入…以此类推，直到整个序列有序
2．具体操作（以排成升序为例）
（1）单趟：针对单个数据
假设[0,end]有序，处理end+1处数据（用tmp存起来，原因：挪数据的时候会覆盖）,依次与前面的数比，用while循环控制
- tmp更大：插入
- tmp更小：挪数据，同时- -end
程序结构如下
while(end>=0)
{
if(tmp更小)
//挪数据;
--end;
else
break;
}
//插入数据
注意：如果处理最小的数据，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-2
int tmp = a[end + 1];//end+1最大是n-1
while (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换成了gap
for (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）稳定性：不稳定
