4、数据结构与算法——希尔排序 - liuxiaofei2010S/special-column GitHub Wiki

希尔排序实在插入排序的基础上进行改进的。首先，“h有序数组”指的是在某一数组中间隔 h 个项所组成的 h 个相互独立的数组。由于插入排序适合于“部分有序数组”，所以对于 h有序数组 希尔排序能有更好的性能表现。在将 h有序数组 排列顺序之后，可以给与一定的增幅，去再次排列 增幅（例如：1/3）倍的h的有序数组，最终为 “1 有序数组”便是最终的有序数组。

代码如下：

public class ShellSort {

public static void main(String[] args) {
    System.out.print("——————————————————————————————");
    int[] array = new int[]{2, 4, 7, 0, 6, 8, 1, 5, 9, 3};
    sort(array);
    System.out.print("——————————————————————————————");
}

/* h 有序数组进行排序，然后增幅排序 */
public static void sort(int[] array) {
    int N = array.length;
    int h = 1;
    while (h < N) {
        h = 2 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < N; i++) {
            for (int k = i; k > h && less(array[k], array[k - h]); k = k - h) {
                exch(array, k, k - h);
            }
        }
        h = h / 3;
    }
}

private static boolean less(int i, int j) {
    return i < j;
}

private static void exch(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
}

希尔排序的性能分析需要较深的数学基础。其性能高于插入排序，它的运行时间达不到平方级别。这样它就突破了平方级别的屏障。

一般中等级别的数组排序使用希尔排序可以接受。主要是代码量小，不使用额外内存，如果在这种情况下使用复杂算法，只是比希尔排序快两倍。