算法之排序-希尔排序

文章目录
  1. 1. 算法描述
  2. 2. 特点
  3. 3. 代码
  4. 4. 比较

算法描述

希尔排序为了加快速度简单的改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组成为h有序数组。在进行排序时，如果h很大，就能将元素移动到很远的地方，为实现更小的h有序创造方便。

特点

希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初各个子数组都很短，排序之后的子数组都是部分有序的，这两种情况都很适合插入排序。子数组的部分有序取决于递增序列的选择。

对于中等大小的数组它的运行时间是可以接受的。他的代码量小，不需要额外的内存空间。后面我们会看到更加高效的算法，但是对于很大的N，它们可能只比希尔排序快2倍（可能还达不到），而且更复杂。可以考虑先用希尔排序，然后在考虑是否值得将它替换为更加复杂的排序算法。

代码

使用序列1/2(3的k次方 - 1)，从N/3开始递减至1。这个序列成为递增序列。

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
public class Shell {
    public static void sort(Comparable[] a) {
        //将a按升序排列
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = h * 3 + 1;//1,3,13,40,121,364,1093...
        while (h >= 1) {
            for (int i = 0; i < N; i++) {
                //将a[i]插入到a[i-1],a[i-2],a[i-3]...之中
                for (int j = i; j > 0; j--) {
                    if (less(a[j], a[j - 1])) {
                        exchange(a, j, j - 1);
                    }
                }
            }
            h = h/3;
        }
    }

    public static void main(String[] args) {
        Character[] a = {'S','H','E','L','L','S', 'O', 'R', 'T', 'E', 'X', 'A', 'M', 'P', 'L', 'E'};
        sort(a);
        if (isSorted(a)) {
            show(a);
        }
    }
}

比较

和选择排序和插入排序形成鲜明对比的是，希尔排序也可以用于大型数组。它对任意排序（不一定是随机的）的数组表现也很好。

通过SortCompare可以看到，希尔排序比插入排序要快的多，并且数组越大，优势越大。