基本思想

1. 先取一个小于n的整数d1作为第一个增量，把待排序的全部记录分成dx个组。所有距离为d1的倍数的记录放在同一个组中。
2. 先在各组内进行直接插人排序。
3. 然后，取第二个增量d2<d1重复上述的分组和排序。
4. 直至所取的增量dt=1(dt<dt-x<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

算法实现

希尔排序算法，Java实现，代码如下所示：

01	public abstract class Sorter {

02	public abstract void sort(int[] array);

03

}

04

05	public class ShellSorter extends Sorter {

06

07

@Override

08	public void sort(int[] array) {

09	int d = array.length;

10

do {

11

d /= 2;

12	shellPass(array, d); // 根据逐渐减小的间隔增量，循环调用一趟排序

13	} while (d > 1);

14

}

15

16

/**

17

* 希尔一趟排序

18	* @param d 间隔增量

19

*/

20	private void shellPass(int[] array, int d) {

21	Integer tmp;

22	for (int i = d; i < array.length; i++) { // 数组下标从0开始，初始i=d表示一趟排序中第二个元素

23	tmp = array[i]; // array[i]的拷贝

24	// 如果待处理的无序区第一个元素array[i] < 有序区最大的元素array[i-d]

25	// 需要将有序区比array[i]大的元素向后移动

26	if (array[i] < array[i - d]) {

27	int j = i - d;

28	while (j >= 0 && tmp < array[j]) {

29	array[j + d] = array[j]; // 将左侧有序区中元素比array[i]大的array[j+d]后移

30

j -= d;

31

}

32	// 如果array[i] >= 左侧有序区最大的array[i-d]，或者经过扫描移动后，找到一个比array[i]小的元素

33	// 将右侧无序区第一个元素tmp = array[i]放到正确的位置上

34	array[j + d] = tmp;

35

}

36

}

37

}

38

}

希尔排序算法，Python实现，代码如下所示：

01	class Sorter:

02

'''

03	Abstract sorter class, which provides shared methods being used by

04	subclasses.

05

'''

06	__metaclass__ = ABCMeta

07

08	@abstractmethod

09	def sort(self, array):

10

pass

11

12	class ShellSorter(Sorter):

13

'''

14	Shell sorter

15

'''

16	def sort(self, array):

17	length = len(array)

18	d = length

19	while d>1:

20

d //= 2

21

i = d

22	# for each d, execute one pass shell sort

23	while i<length:

24	tmp = array[i]

25	if array[i]<array[i-d]:

26

j = i - d

27	while j>=0 and tmp<array[j]:

28	array[j+d], array[j] = array[j], array[j+d]

29

j = j - d

30	array[j+d] = tmp

31

i = i + 1

排序过程

希尔排序的过程如下：

1. 首先初始化间隔d为待排序数组的长度，无需排序。减小d，对于每次得到的间隔d，执行多组排序，使得原始数组间隔为d的一个子数组为有序，该数组通过类似直接插入排序的算法来执行排序。
2. 直到，d减小为1的时候，整个数组为有序。这里，采用二分的策略来得到间隔d。

下面通过例子来说明，执行希尔排序的过程，如下所示：
假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，数组大小为20。整个排序过程的分组情况，如下所示：

1	{94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}

2	{37,5,34,76,26,9,0,37,55,49, 94,12,68,83,90,37,12,65,76,76}

3	{9,0,34,55,26, 37,5,37,76,49, 37,12,65,76,76, 94,12,68,83,90}

4	{5,0, 9,12,12, 37,26, 37,34,49, 37,55, 65,68,76, 76,76, 90,83,94}

5	{0, 5, 9, 12,12, 26, 34, 37, 37,37, 49, 55, 65, 68,76, 76, 76, 83, 90,94}

下面说明详细过程：
首先，初始化d = 20。在循环中反复得到间隔d，根据d执行一趟希尔排序。

• 对于d = 20/2 = 10：

根据d = 10来对数组排序，将原始数组分成2块： {94,12,34,76,26,9,0,37,55,76}与{37,5,68,83,90,37,12,65,76,49}，也就是对如下数组分别进行直接插入排序：
{array[0],array[10]} = {94,37}
{array[1],array[11]} = {12,5}
{array[2],array[12]} = {34,68}
{array[3],array[13]} = {76,83}
{array[4],array[14]} = {26,90}
{array[5],array[15]} = {9,37}
{array[6],array[16]} = {0,12}
{array[7],array[17]} = {37,65}
{array[8],array[18]} = {55,76}
{array[9],array[19]} = {76,49}
第一趟希尔排序后，各个子数组变为：
{37,5,34,76,26,9,0,37,55,49}与{94,12,68,83,90,37,12,65,76,76}，
即：array = {37,5,34,76,26,9,0,37,55,49,94,12,68,83,90,37,12,65,76,76}，

• 对于d = 10/2 = 5：

根据d = 5来对数组排序，将第一趟希尔排序后的数组分成4块 ：{37,5,34,76,26}、{9,0,37,55,49}、{94,12,68,83,90}与{37,12,65,76,76}，也就是对如下数组分别进行直接插入排序：
{array[0],array[5],array[10],array[15]} = {37,9,94,37}
{array[1],array[6],array[11],array[16]} = {5,0,12,12}
{array[2],array[7],array[12],array[17]} = {34,37,68,65}
{array[3],array[8],array[13],array[18]} = {76,55,83,76}
{array[4],array[9],array[14],array[19]} = {26,49,90,76}
第二趟希尔排序后，各个子数组变为：
{9,0,34,55,26}、{37,5,37,76,49}、{37,12,65,76,76}与{94,12,68,83,90}，
即：array = {9,0,34,55,26,37,5,37,76,49,37,12,65,76,76,94,12,68,83,90}。

• 对于d = 5/2 = 2：

根据d = 2来对数组排序，将第二趟希尔排序后的数组分成10块： {9,0}、{34,55}、{26,37}、{5,37}、{76,49}、{37,12}、{65,76}、{76,94}、{12,68}与{83,90}，也就是对如下数组分别进行直接插入排序：
{array[0],array[2],array[4],array[6],array[8],array[10],array[12],array[14],array[16],array[18]} = {9,34,26,5,76,37,65,76,12,83}
{array[1],array[3],array[5],array[7],array[9],array[11],array[13],array[15],array[17],array[19]} = {0,55,37,37,49,12,76,94,68,90}
第三趟希尔排序后，各个子数组变为：{5,0}、{9,12}、{12,37}、{26,37}、{34,49}、{37,55}、{65,68}、{76,76}、{76,90}与{83,94}，
即：array = ：{5,0,9,12,12,37,26,37,34,49,37,55,65,68,76,76,76,90,83,94}。

• 对于d = 2/2 = 1：

根据d = 1来对数组排序，将第二趟希尔排序后的数组分成20块：{5}、{0}、{9}、{12}、{12}、{37}、{26}、{37}、{34}、{49}、{37}、{55}、{65}、{68}、{76}、{76}、{76}、{90}、{83}、{94}，也就是对如下数组分别进行直接插入排序：
{5,0,9,12,12,37,26,37,34,49,37,55,65,68,76,76,76,90,83,94}
第四趟希尔排序以后，数组已经有序：
array = {0,5,9,12,12,26,34,37,37,37,49,55,65,68,76,76,76,83,90,94}。
因为 d= 1，希尔排序结束。

算法分析

希尔排序是基于插入排序的一种算法， 它的时间复杂度与增量序列的选取有关，例如：

• 希尔提出了增量序列 h1 ，h2 ，……，ht ，只要h1=1，任何增量序列都是可行的，使用希尔增量排序的时间复杂度为O(n^2)。
• Hibbard提出了一个增量序列：2^k-1，使用Hibbard增量排序的时间复杂度为O(n^(3/2))。
• Sedgewick提出了几种增量序列：9*4i – 9*2i +1 或者是 4i – 3* 2i + 1，最坏运行时间为O(n^(4/3))，对这些增量序列的平均运行时间猜测为O(n^(7/6))。

但是现今仍然没有人能找出希尔排序的精确下界。希尔排序没有快速排序算法快O(nlogn)，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(n^2)复杂度的算法快得多。
此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法。
本质上讲，希尔排序算法是直接插入排序算法的一种改进，减少了其复制的次数，速度要快很多，原因是，当n值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。当n值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。

• 时间复杂度

希尔排序的效率很大程度上依赖于增量序列的选择，好的增量序列有如下共同特征：

1. 最后一个增量必须为1。
2. 应该尽量避免序列中的值（尤其是相邻的值）互为倍数的情况。

有人通过大量的实验，给出了较好的结果：当n较大时，比较和移动的次数约在n^1.25到1.6*n^1.25之间。
另外，希尔排序的时间性能优于直接插入排序，原因是：

1. 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
2. 当n值较小时，n和的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0()差别不大。
3. 在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

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

• 空间复杂度

因为希尔排序依赖于增量序列，从而导致排序的趟数不固定，对于不同的增量执行一趟希尔排序，只用到一个辅助变量，所以空间复杂度为O(n)。

• 排序稳定性

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，通过上述元素76可以看到，希尔排序不稳定。
因此，希尔排序是不稳定的。