希尔排序

希尔排序(Shell's Sort)是D.L.Shell 于1959年提出的，它是一种基于插入排序的快速的排序算法。对于大规模乱序数组直接插入排序很慢，因为它只会交换相邻的元素。希尔排序加快了交换的过程。
希尔排序的思想是使数组中任意间隔为h的元素都是有序的，这样的数组被称为h有序数组。换句话说，希尔排序时数组中间隔为h的元素会组成一个独立的数组，例如，若数组长度为14，h为4，则数组在逻辑上会被分为这几个独立数组(以索引表示)：0、4、8、12为一组，1、5、9、13为一组，2、6、10为一组，3、7、11为一组，这些数组会在一轮循环后各自有序。
希尔排序的实现中h是以某种序列递减的(实际上这个序列被称为递增序列，只是代码中不断作除法，所以是递减的)，后面的代码实现中h是以序列1/2(3^k-1)递减的，最终会递减为1，且最终必须递减为1，才能使数组有序。
希尔排序高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组较短；排序之后子数组都是部分有序的，这两种情况都很适合插入排序。

1. 排序过程

以 int[] arr = {41,60,8,83,33,71,23,4,34,1,70,3,25,6,56,75}; 说明希尔排序的过程：
trip 1：此时h为13，本轮循环会使arr[0]、arr[13]，arr[1]、arr[14]，arr[1]、arr[15]三组分别有序
trip 2：此时h为4，本轮循环会使arr[0]、arr[4]、arr[8]、arr[12]，arr[1]、arr[5]、arr[9]、arr[13]，arr[2]、arr[6]、arr[10]、arr[14]，arr[3]、arr[7]、arr[11]、arr[15]四组分别有序
trip 3：此时h为1，本轮循环就是一次直接插入排序，结束后整个数组处于有序状态

2. 代码实现

    // 希尔排序
    public static void shellSort(int[] arr) {
        int N = arr.length;
        int h = 1;
        // h为 1、4、13、40、121、...
        // h(k) = 1/2(3^k - 1)，k = 1、2、3、...
        while (h < N/3) h = h*3 + 1;
        while (h >= 1){
            // 这里i从h开始，以保证各独立数组前面部分先有序
            for (int i = h; i < N; i++) {
                // 将arr[i]插入到元素为arr[i-h]、arr[i-2*h]、arr[i-3*h]、...的独立数组中
                for (int j = i; j >= h && (arr[j] < arr[j-h]); j -= h) {
                    int tmp = arr[j-h];
                    arr[j-h] = arr[j];
                    arr[j] = tmp;
                }
            }
            h = h/3;
        }
    }

3. 示例

示例说明：

读示例时逐行来看
所有中间行中(除了第一行和最后一行)，灰色表示未移动元素，黑色表示发生移动的元素

4. 总结

4.1 递增序列的选择

很多论文研究了各种不同的递增序列，但都无法证明哪个序列是最好的。上述代码中递增序列的计算和使用都很简单，和复杂的递增序列性能接近。但是最坏情况下复杂序列的性能要优于上述代码中的递增序列。

4.2 特点

对于乱序数组，希尔排序是唯一无法准确描述性能特征的排序方法，但实际测试后，它比选择排序和(直接)插入排序快得多，并且数组越大，优势越大。
对于中等大小的数组希尔排序的运行时间是可以接受的。它代码量小、无需额外内存空间。后面将会介绍更加高效的算法，对于不是很大的数组，它们仅比希尔排序快将近两倍，而且实现复杂。