1.算法介绍

希尔排序又叫作缩小增量排序，其本质还是插入排序，只不过是将待排序列按某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。这个规则的体现就是增量的选取，如果增量为1，就是直接插入排序。例如，先以增量5来分割序列，即将下标为0、5、10、15…的关键字分成一组，将下标为1、6、11、16…的关键字分成另一组等，然后分别对这些组进行直接插入排序，这就是一趟希尔排序。将上面排好序的整个序列，再以增量2分割，即将下标为0、2、4、6、8…的关键字分成一组，将下标为1、3、5、7、9…的关键字分成另一组等，然后分别对这些组进行直接插入排序，这又完成了一趟希尔排序。最后以增量1分割整个序列，其实就是对整个序列进行一趟直接插入排序，从而完成整个希尔排序。

注意到增量5、2、1是逐渐缩小的，这就是缩小增量排序的由来。前面讲过，直接插入排序适合于序列基本有序的情况，希尔排序的每趟排序都会使整个序列变得更加有序，等整个序列基本有序了，再来一趟直接插入排序，这样会使排序效率更高，这就是希尔排序的思想。

2.执行流程

1）以增量5分割序列，得到以下几个子序列。

分别对这5个子序列进行直接插入排序，得到

一趟希尔排序结束，结果为：

2）再对上面排序的结果以增量3分割，得到以下几个子序列。

分别对这3个子序列进行直接插入排序，得到

又一趟希尔排序结束，结果为：

观察发现，现在已经基本有序了。

3）最后以增量1分割，即对上面结果的全体关键字进行一趟直接插入排序，从而完成整个希尔排序。最后希尔排序的结果为：

观察发现，两个49在排序前后位置颠倒了，所以希尔排序是不稳定的。

说明：对于希尔排序，考研中的重点是上边所讲的执行流程，考题经常给出一个待排序列，让考生写出每一趟排序的执行情况。而对于希尔排序的算法代码，考研要求得不多，考生应在熟练掌握了上述过程后，有时间再去掌握算法代码，算法代码严版数据结构书上有。

3.性能分析

（1）时间复杂度(www.daowen.com)

希尔排序的时间复杂度和增量选取有关，希尔排序的增量选取规则有很多，而考研数据结构中常见的增量选取规则有以下两个。

1）希尔（Shell）自己提出的：

n/2、n/4、…、n/2^k、…、2、1

即每次将增量除以2并向下取整，其中n为序列长度，此时时间复杂度为O（n²）。

2）帕佩尔诺夫和斯塔舍维奇（Papernov&Stasevich）提出的：

2k+1、…、65、33、17、9、5、3、1

其中，k为大于等于1的整数，2^k+1小于待排序列长度，增量序列末尾的1是额外添加的。此时时间复杂度为O（n^1.5）。

说明：希尔排序的时间复杂度分析过程十分复杂，因此考研数据结构中不会涉及分析过程的题目，只需记住上述两个常见的结果即可。

关于希尔排序的一个考点：

请回答希尔排序增量选取时需要注意的地方。

答：

1）增量序列的最后一个值一定取1。

2）增量序列中的值应尽量没有除1之外的公因子。

（2）空间复杂度

希尔排序的空间复杂度同直接插入排序一样，为O（1）。