Intro

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。

希尔排序的出发点是插入排序,但是插入排序效率低下,效率低下的主要原因在于每个元素每次只向前移动一个位置,即使我们大概知道那些元素还需要移动很远的距离。
而希尔排序的思想则稍有不同,每次我们会将序列中的项移动若干位置,而不再是插入排序中的向前移动一个位置。

希尔排序的基本思想

希尔排序是将序列按照一定的增量进行分组,对每组使用直接插入排序算法进行排序,当增量减直到被减少为1的时候,整个序列为一组,进行直接插入算法排序进行最终排序,算法终止我们便得到了一个有序序列。
希尔排序算法通过此方法将序列使其在初始阶段宏观上达到基本有序,在增量达到1的时候,只需要微调整序列元素的位置即可达到有序的效果。

shell-sort-1

代码实现

这里我们选择增量为\( gap = 3x + 1 \),缩小增量我们继续以\( gap = 3x + 1 \)的方式,这种增量我们可以用一个序列来表示:

$$
\lbrace(3x + 1)\setminus3,…1\rbrace
$$

这是著名的唐纳德·克努特(Donald Ervin Knuth)提出的一种增量序列,但这并不是最优的增量序列。
其实通过这里也看出了希尔排序只是一个框架,选择了什么样的增量序列将会影响到这个算法的性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

package net.sunzhenyu.miscellaneous.dsa.sort;

public class ShellSort implements Sort {

@Override
public void sort(Comparable[] c) {
int length = c.length;
int gap = 1;
while (gap < length / 3) {
// 根据Knuth的增量序列 3x + 1
gap = gap * 3 + 1;
}

while (gap >= 1) {
for (int i = gap; i < length; i++) {
for (int j = i; j >= gap && less(c[j], c[j - gap]); j -= gap) {
exch(c, j, j - gap);
}
}
gap = gap / 3;
}
}

private void exch(Comparable[] c, int i, int j) {
Comparable oldValue = c[i];
c[i] = c[j];
c[j] = oldValue;
}
}

测试结果:
shell-sort-result