一种基于插入排序的快速排序算法。

对于大规模乱序数组插入排序很慢。因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。希尔排序为了加快速度简单地改进了插人排序，交换不相邻的元素以对数组的局部进行排序，并最终用插人排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。

算法实现就是将h有序数组依次进行插入排序，排序完成后缩小h再次进行插入排序，直至h为1，此时再进行最后一次插入排序。

本文中h的规则为h=3*h+1，h=1 3 4 13 40 121...，h不大于数组的长度N。

原始数组为SHELLSORTEXAMPLE。N=16，因此h从13开始递减至1。

排序过程分为三次

• 将13有序数组依次进行插入排序
• 将4有序数组依次进行插入排序
• 最后再进行一次插入排序

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);
            }
        }
        h /= 3;
    }
}

该算法的复杂度难以证明。但是通过大量数据测试可以发现，希尔排序的速度明显快于选择排序及插入排序，并且数组最大，优势越大。