算法说明

希尔排序是基于插入排序的一种快速的排序算法。它的思想是使数组中的任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个相互独立的有序数组编织在一起组成的一个数组。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，我们都能够将数组排序。

例：如果原始数据是这样子
4 5 1 2 3 9 8 11 6 12 13 7
那么设h=4,则有以下子数组,对四个子数组分别进行插入排序:

数组1:[4,3,6]->[3,4,6]-->变换1次

数组2:[5,9,12]->[5,9,12]-->无变换

数组3:[1,8,13]->[1,8,13]-->无变换

数组4:[2,11,7]->[2,7,11]-->变换一次

则原始数组变成
3 5 1 2 4 9 8 7 6 12 13 11
再设h=2,则有以下子数组,再对两个子数组分别进行插入排序:

数组1:[3,1,4,8,6,13]->[1,3,4,6,8,13]--> 变换两次

数组2:[5,2,9,7,12,11]->[2,5,7,9,11,12]--> 变换三次

则原数组变成
1 2 3 5 4 7 9 8 11 13 12
最后对整个数组进行插入排序
1 2 3 4 5 7 8 9 11 12 13  变换三次

算法复杂度

算法的性能不仅取决于h，还取决于h之间的数学性质，比如他们的公因子。有很多论文研究了各种不同的递增序列，但都无法证明某个序列是“最好的”。
希尔排序比插入排序和选择排序要快得多，并且数组越打，优势越大。
该算法的性能，目前最重要的结论是它的运行时间达不到平方级别。
在下面几节中我们会看到更加高效的算法，但除了对于很大的N，它们可能只会比希尔排序快两倍（可能还不到）。

源代码

package edu.princeton.cs.algs4;

public class Shell {

    private Shell() { }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        int n = a.length;

        // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
        int h = 1;
        while (h < n/3) h = 3*h + 1; 

        while (h >= 1) {
            // h-sort the array
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                    exch(a, j, j-h);
                }
            }
            assert isHsorted(a, h); 
            h /= 3;
        }
        assert isSorted(a);
    }



   /***************************************************************************
    *  Helper sorting functions.
    ***************************************************************************/
    
    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
        
    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }


   /***************************************************************************
    *  Check if array is sorted - useful for debugging.
    ***************************************************************************/
    private static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }

    // is the array h-sorted?
    private static boolean isHsorted(Comparable[] a, int h) {
        for (int i = h; i < a.length; i++)
            if (less(a[i], a[i-h])) return false;
        return true;
    }

    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    /**
     * Reads in a sequence of strings from standard input; Shellsorts them; 
     * and prints them to standard output in ascending order. 
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        String[] a = StdIn.readAllStrings();
        Shell.sort(a);
        show(a);
    }

}

算法分析

程序输入来自tiny.txt，内容为

S O R T E X A M P L E

程序入口:

public static void main(String[] args) {
    String[] a = StdIn.readAllStrings();
    Shell.sort(a);
    show(a);
}

逻辑分析:

public static void sort(Comparable[] a) {
    int n = a.length;

    // 设定3x+1为h的递增序列 1, 4, 13, 40, 121, 364, 1093, ...
    int h = 1;
    while (h < n/3) h = 3*h + 1; 

    while (h >= 1) {// 最外层循环保证h值固定,第一次为13
        // h-sort the array
        for (int i = h; i < n; i++) {
                // 这层循环表示，每次把j和j-h比较，再把j减去h，for循环几次，相当于把数向前移动几h个位置,从而保证子数组有序
            for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                exch(a, j, j-h);
            }
        }
        assert isHsorted(a, h); 
        h /= 3;
    }
    assert isSorted(a);
}