排序算法(五): Shell Sort 希尔排序

基本排序算法中的插入排序虽然逻辑较为简单,但当排序规模较大时,经常需要将元素一位一位地从一端移动到另一端,效率非常低。于是Donald Shell设计了一种基于插入排序的改进版排序算法,故被命名为 Shell Sort 希尔排序

abstract.png

算法思想

插入排序效率低下是因为其移动元素每次只能移动一位,当排序元素的规模较大时,需要将元素一位一位地从一端移动到另一端。而如果我们能够让元素一次性地移动到较远的位置上,这样无疑就可以避免多次一位一位地移动操作。希尔排序正是基于此原理来优化、提高插入排序的效率。通过指定步长step,将原数组分为step个互相独立子数组,然后通过插入排序对这些子数组分别进行排序(即分组排序),这时我们称其为step有序数组。当step很大时,我们就可以将元素一次性移动到很远的位置上,为下一次较小的step有序创造便利;不断缩小步长step,重复上述过程建立step有序数组,达到局部有序的目的。当step最终为1做最后一次step有序时,就是我们平常所熟悉的插入排序了,由于该数组已经多次被较大的step进行分组排序了,此时只需要较少次数的元素移动就可以实现整个数组全局有序

figure 1.jpeg

在希尔排序中,需要经历若干次step有序。在每一次step有序过程中,分组所使用的step步长越来越小直到其为1,即其是一个最后项为1的递减序列。关于step序列的选取问题,不建议大家自行设计,这里给出一个合适并简单的step序列的通项公式。在实际使用时,根据排序规模计算到合适的第n项,然后将该数列反序。即为我们进行希尔排序时所用到的step序列

Java 代码示例

这里即是一个希尔排序的示例

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
* 希尔排序
*/
public class ShellSort {
/**
* 升序排列
*/
public static void sort() {
int[] array = getTestCase();
int size = array.length;

System.out.println("before sort: " + Arrays.toString(array) );

int step = 1; // 希尔排序的步长
// 根据排序规模计算step序列到第n项
while( step < size/3 ) {
step = 3 * step + 1; // step(n) = 1/2*(3^n-1) 的递推公式
}

while( step>=1 ) {
// 按指定步长step进行分组,对array[i]进行排序,使之step有序
for( int i=step; i<size; i++ ) {
// 将array[i]插入到array[i-step],array[i-2*step],array[i-3*step]...当中
for(int j=i; j-step>=0 && less(array[j], array[j-step]); j-=step ) {
exchange(array, j, j-step);
}
}
// 更新步长
step = step/3;
}

System.out.println("after sort: " + Arrays.toString(array) );
}

/**
* 判定a是否比b小
* @param a
* @param b
* @return
*/
private static boolean less(int a, int b) {
if(a<b) {
return true;
}
return false;
}

/**
* 交换数组中 i、j 位置的元素
* @param array
* @param i
* @param j
*/
private static void exchange(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

/**
* 获取测试用例
*/
private static int[] getTestCase() {
int[] caseArray = {-54,12,16,44,36,99,2,88,5,33,26,4,64,3,-44,-2,62,71,27,10,49,83,92};
return caseArray;
}
}

测试结果如下:

figure 2.jpeg

特性

空间复杂度

由于希尔排序是原地排序算法,故其空间复杂度为O(1)

时间复杂度

希尔排序的时间复杂度很大程度取决于step序列的设计,故此在前文中不建议大家自行设计step序列。对于本文所给出的step序列,其时间复杂度不超过平方阶。就到底什么样的step序列是最优的,目前该问题依然无解。但我们可以知道的是,在中等规模的排序需求中,一般情况下直接使用希尔排序已经足够了。如果经实际测试确实需要优化,此时再考虑使用快排等排序算法也不迟

稳定性

不稳定

参考文献

  1. 算法(第4版) Robert Sedgewick、Kevin Wayne 著
  2. 计算机程序设计艺术(第3卷):排序与查找 高德纳(Donald E.Knuth) 著
0%