排序算法——希尔排序

发表于 更新于 分类于 ， ， ，

介绍

希尔排序(Shell Sort)按其设计者希尔（Donald Shell）的名字命名，该算法由希尔 1959 年公布。是一种插入排序的改进方式。插入排序在排序的时候，需要逐一比较两两元素之间的大小，效率不高。希尔排序按照下标的增量将序列先分组，每个组里使用插入排序，这样可以跳跃地比较元素的大小，确定元素间的宏观位置。再经过慢慢缩减增量(有不同增量选取方式，通常取原增量的二分之一)，可以微调元素位置，直到增量达到1时，所有元素排序完成。

看起来希尔排序的步骤要比插入排序的多很多，那它的时间复杂度应该比插入排序大很多才对呢，为什么效率更高了呢。可以拿希尔排序的增量为一的最后一步排序为例，经过前面的处理，希尔排序到最后一步大小相近的元素都被放到了相邻的位置，再进行插入排序至多一步就可以找到自己的最终位置跳出循环；而插入排序则可能一直比较到序列头部才找到自己的位置，所以效率低。

希尔排序的步骤虽复杂，但是整体上减少了时间复杂度，希尔排序的时间复杂度为\(O(n^{1-2})\)，并没有一个确定的值，取决于增量的选择。

实现

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
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = new int[]{20, 48, 27, 98, 15, 78, 85, 80, 59, 47};
        int gap = arr.length;
        while (gap >= 1) {
            gap = gap / 2;
            for (int i = 0; i < gap; i++) {
                for (int j = i; j < arr.length; j += gap) {
                    int k = j;
                    while (k > i) {
                        if (arr[k] < arr[k - gap]) {
                            int t = arr[k];
                            arr[k] = arr[k - gap];
                            arr[k - gap] = t;
                        }
                        k -= gap;
                    }

                }
            }
        }
        for (int i : arr) {
            System.out.println(i);
        }
    }
}
[out]:
15
20
27
47
48
59
78
80
85
98
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def shell_sort(a):
    gap = len(a)
    while gap >= 1:
        gap = gap // 2
        for i in range(gap):
            for j in range(i, len(a), gap):
                k = j
                while k > i:
                    if a[k] < a[k - gap]:
                        a[k], a[k - gap] = a[k - gap], a[k]
                    k -= gap
    return a


if __name__ == '__main__':
    arr = [20, 48, 27, 98, 15, 78, 85, 80, 59, 47]
    arr = shell_sort(arr)
    print(arr)

    
[out]:
15, 20, 27, 47, 48, 59, 78, 80, 85, 98