8.2.2　希尔排序

希尔排序又称缩小增量排序，也是一种属于插入排序类的方法，但在时间效率上比直接插入排序方法有较大的改进，是Shell在1959年提出的。

1.希尔排序的基本思想

希尔排序的基本思想是：将待排序的记录划分成若干个组，对同一小组内的数据元素用直接插入法排序，从而减少参与直接插入排序的数据量；小组的个数逐次缩小，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序，使所有数据元素都在一个组内。

具体做法：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后取第二个增量d2＜d1重复上述的分组和排序，直至所取的增量dt＝1（dt＜dt－1＜…＜d2＜d1），即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

排序过程如图8－2所示。第1次增量d＝5，将关键字分为5组，每组排序；第2次增量d＝3，将关键字分为3组，每组排序；第3次增量d＝1，关键字合为1组，排序成功。

图8－2 希尔排序示例

希尔排序的最核心问题就是增量的选择问题，目前并没有研究出具体的方法来求得增量，只是研究出增量如何取才合理。好的增量序列的共同特征：①最后一个增量必须为1；②应该尽量避免序列中的值（尤其是相邻的值）互为倍数的情况。人们通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数在n1.25到1.6n1.25。

2.希尔排序算法

下面给出希尔排序的算法的实现过程。

（1）分别让每个记录参与相应分组中的排序

若分为d组，前d个记录就应该分别构成由一个记录组成的有序段，从d＋1个记录开始，逐一将每个记录a［i］插入相应组中的有序段中，其算法可以这样实现：

（2）将a［i］插入相应组的有序段中的操作可以这样实现：

①将a［i］赋予a［0］中，即a［0］＝a［i］；

②让j指向a［i］所属组的有序序列中最后一个记录；

③搜索a［i］的插入位置

算法8.2 希尔排序

3.希尔排序的算法复杂度

在希尔排序中，由于开始将n个待排序的记录分成了d组，所以每组中的记录数目将会减少。在数据量较少时，利用直接插入排序的效率较高。随着反复分组排序，d值逐渐变小，每个分组中的待排序记录数目将会增多，但此时记录的排列顺序将更接近有序，所以利用直接插入排序不会降低排序的时间效率。通常，di＋1＝di／2（结果取整）。

Knuth认为希尔排序的平均比较次数和平均移动次数均在n1.3左右。

希尔排序的优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。因为仅占用1个缓冲单元，其空间效率为O（1）；时间效率为O（nlog2n）。希尔排序是一种不稳定的排序方法。

希尔排序的时间性能优于直接插入排序的原因：

①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O（n）和最坏时间复杂度O（n2）差别不大。

③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di－1作为距离排过序，文件较接近于有序状态，所以新的一趟排序过程也较快。

因此，希尔排序在效率上较直接插入排序有较大的改进。