希尔排序【C语言】

希尔排序

前言

在上一篇文章中我们了解了直接插入排序算法（建议先阅读），但其实这个算法还是有一定优化空间的。而它优化之后，就变成了另一个大名鼎鼎的排序算法：希尔排序。

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序的算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

正文

记得么，我们说直接插入排序最差的情况也就是降序（我们要排升序）时的情况。那么有什么办法可以让这种情况的时间复杂度得到提升吗？

是有的，我们可以将我们要排序的数组划分为几段，在一段中进行直接插入排序，排完后再划分为大一点的段，再各自直接插入排序…这样我们的时间复杂度就会小于O(n²)。

希尔排序其实就是两步：

预排序
直接插入排序

希尔排序法的基本思想是：先选定⼀个整数（通常是gap=n/3+1），把待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序;

然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序;

当gap=1时，就相当于直接插⼊排序。它是在直接插⼊排序算法的基础上进⾏改进⽽来的，综合来说它的效率肯定是要⾼于直接插⼊排序算法的。

我们来画图理解一下这个排序过程：

现在我们先有这10个数据（n=10），让gap为5（n/2），也就是步长为5。也就是每隔5个数我们将其划分到一个组中。

9和4为一组，1和8为一组，2和6为一组，5和3为一组，7和5为一组。

我们划分了5组，每组2个数据，在每组里进行直接插入排序。

（为了方便观察与直接插入排序的区别，将直接插入排序代码放在这：)

在每组里进行直接插入排序，也就是说在第一组里，让end为9，tmp为4。

按照我们之前的直接插入算法的做法，我们比较end与tmp的大小，end更大应该往后放，但是不再是放到end+1的位置了，而是放到end+gap的位置;

end再往前走也不再是减1而是减gap了;

end越界了，此时我们将tmp不再是放到end+1而是放到end+gap的位置。

剩下的4组也是同样的操作。

可以看到这样进行完，我们基本把小的数据放到前面而大的数据放到后面了。这第一步就叫做预排序。

然后我们gap/2，让gap变为2。每隔2划分为一组。

我们先尝试写这个代码。

我们仍用刚才的数据，但先让gap为3来看看。

这一步我们将end与tmp比较，满足条件后将tmp位置替换为end的值。

这一步我们让end往前走，发现end>=0不满足，跳出了循环，执行arr[end+gap]=tmp这一句。

然后我们再次进入外层循环。这时我们将i++改为i+=gap，来观察我们一组排完再排下一组的情况。

所以这时进入外层循环end来到的是第一组的第二个数据，也就是现在的9的位置，tmp就走到了第一组的第三个数据也就是8的位置。然后再次进行组内直接插入排序:

可见，这时第一组（黄色）的前三个数据5 8 9就排为有序了。又回到外层循环，i+=gap，所以end来到现在的9，tmp来到现在5的位置。

最后，我们的第一组就有序了。

可以看到我们此时的外循环已经结束了，但是我们只排了一组，也就是说我们外面要再来一层循环。

但是这些排完之后我们也只是把三组各自直接插入排序了，也就得到5 1 2 5 6 3 8 7 4 9，接近有序但仍然不是有序的。所以我们的gap还要除3，变为1，也就是变成了直接插入排序了。

通过预排序，小的靠前，大的靠后，基本有序，然后再直接插入排序（gap=1），时间复杂度就比直接插入排序低很多。

然后我们会发现，由于gap要改变，代码会变成4层循环：

这样循环太多层了，我们需要优化。

怎么优化呢？

我们刚才是一组一组分开去排的，一组排完了才能排下一组，现在我们不这么做，将代码改为：

将刚才第二层循环去掉，并且将剩下的for循环里的i+=gap改为i++。

现在我们就变成了end从前往后逐次加一，也就是排完第一组的前两个数据后我们就先排第二组的前两个数据，然后再排第三组的前两个数据……这样走下去我们会走到第一组的第二个数据和第三个数据，这样我们也能把一组排好。总之，不再是一组一组去排。

还有一个问题，我们的gap到底取取多少呢？

我们一般用gap/3，也就是先分为3组。然后我们刚才所说，gap>1时我们是预排序，而gap=1时则为直接插入排序，也就是最后的一次排序。所以我们要让gap最后一次除3为1。假如我们现在n为6，第一次除3为2，第二次除3变为0，达不到我们要的效果。所以我们改为gap=gap/3+1，保证最后一次gap一定为1。

然后容易写错的，是我们的外层while循环条件，注意不能写为>=，否则在gap变为1后也就是理应最后一次排序后，gap/3+1还是1，又进入循环，变成了死循环。

希尔排序与直接插入排序对比

//直接插入排序
void InsertSort(int* arr, int n)
{for (int i = 0; i < n-1; i++){int end = i;//end是有序区间的最后一个数据int tmp = arr[end + 1];while (end>=0){if (arr[end] > tmp){arr[end + 1] = arr[end];//往后放一位end--;}else{break;}}arr[end + 1] = tmp;}
}

//希尔排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap>1)//不能是gap>=1，否则会死循环！！{gap = gap / 3;for (int i = 0; i < n - gap; i++)//这样tmp才不会越界{int end = i;//end最后一次为n-gap-1int tmp = arr[end + gap];//tmp最后一次为n-1while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

可以看到是非常相似的。有意思的是我们明明加了一个外层循环while，却让时间复杂度下降了。

测试代码：排序性能对比

在上一篇文章“直接插入排序”中我们写的10万个随机数的时间测试，我们在这里再次使用（具体代码详见上一篇文章）：

从直接插入排序和希尔排序的对比我们可以直观地看到这个优化的显著效果。

希尔排序时间复杂度的分析

我们知道对于直接插入排序，时间复杂度最差情况也就是随着有序区间的增大，交换的次数也越来越多。而希尔排序我们分组，每组的交换并不多，且最后能实现（升序）小的数据基本在左边，大的数据基本在右边（也就是预排序），这样我们随着有序区间的增大，交换的次数也很少。在这种情况下再去直接插入排序，时间复杂度就好了很多。

我们先来看外层循环多少次，gap>1，gap=gap/3（忽略常数1），也就是说gap一开始为n，每次除3直到为1，那么会进行多少次呢？假设进行x次，那么 $3^x=n$ 成立，所以 $x=log_3n$ 。我们说过底数可以忽略不计，所以外层的复杂度就为logn。