前言

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。

希尔排序，也称递减增量排序算法，以其设计者希尔（Donald Shell）的名字命名，该算法由 1959 年公布。

算法思想

如何对原始数组进行预处理呢？聪明的科学家想到了一种分组排序的方法，以此对数组进行一定的“粗略调整”。

所谓分组，就是让元素两两一组，同组两个元素之间的跨度，都是数组总长度的一半，也就是跨度为4。

如图所示，元素5和元素9一组，元素8和元素2一组，元素6和元素1一组，元素3和元素7一组，一共4组。

接下来，我们让每组元素进行独立排序，排序方式用直接插入排序即可。由于每一组的元素数量很少，只有两个，所以插入排序的工作量很少。每组排序完成后的数组如下：

这样一来，仅仅经过几次简单的交换，数组整体的有序程度得到了显著提高，使得后续再进行直接插入排序的工作量大大减少。这种做法，可以理解为对原始数组的“粗略调整”。

但是这样还不算完，我们可以进一步缩小分组跨度，重复上述工作。把跨度缩小为原先的一半，也就是跨度为2，重新对元素进行分组：

如图所示，元素5，1，9，6一组，元素2，3，8，7一组，一共两组。

接下来，我们继续让每组元素进行独立排序，排序方式用直接插入排序即可。每组排序完成后的数组如下：

此时，数组的有序程度进一步提高，为后续将要进行的排序铺平了道路。

最后，我们把分组跨度进一步减小，让跨度为1，也就等同于做直接插入排序。经过之前的一系列粗略调整，直接插入排序的工作量减少了很多，排序结果如下：

让我们重新梳理一下分组排序的整个过程：

像这样逐步分组进行粗调，再进行直接插入排序的思想，就是希尔排序，根据该算法的发明者，计算机科学家Donald Shell的名字所命名。

上面示例中所使用的分组跨度（4，2，1），被称为希尔排序的增量，增量的选择可以有很多种，我们在示例中所用的逐步折半的增量方法，是Donald Shell在发明希尔排序时提出的一种朴素方法，被称为希尔增量。

可想而知，步长的选择是希尔排序的重要部分。算法最开始以一定的步长进行排序，然后会继续以更小的步长进行排序，最终算法以步长为 1 进行排序。当步长为 1 时，算法变为直接插入排序，这就保证了数据一定会被全部排序。

算法分析

希尔排序的算法性能

1、时间复杂度
步长的选择是希尔排序的重要部分，只要最终步长为1任何步长序列都可以工作。

算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。

步长序列的不同，会导致最坏的时间复杂度情况的不同。

本文中，以N/2为步长的最坏时间复杂度为N^2。

Donald Shell 最初建议步长选择为N/2并且对步长取半直到步长达到1。虽然这样取可以比O(N^2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法...

课后习题

【2018年真题】对初始数据序列（8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 ）进行希尔排序。若第一趟排序结果为（1,3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ），第二趟排序结果为（1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9  ），则两趟排序采用的增量（间隔）依次是    。
A.3, 1    B. 3,2    C. 5,2    D. 5,3

参考答案：D

【2015年真题】希尔排序的组内排序采用的是（）。

A．直接插入排序    B．折半插入排序    C．快速排序    D．归并排序

参考答案：A

【2014年真题】用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）可能是（）
A．2 
B．3 
C．4 
D．5

参考答案：B
答案解析：首先，第二个元素为1，是整个序列中的最小元素，所以可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为2，第 1+2 个元素4明显比第1个元素9要大，A 排除；若增量为3，第 i、i+3、i+6 个元素都为有序序列(i=1,2,3)，符合希尔排序的定义；若增量为4，第1个元素9比第1+4个元素7要大，C排除；若增量为5，第1个元素9比第1+5个元素8要大，D排除，选B。