Shell排序

相对于最简单的选择排序，插入排序在解决具有某些规律的乱序数组排序时会更有优势，但由于插入排序只会交换相邻的元素，因此元素只能一点一点的从一端移到另一端。
Shell排序简单的改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序对局部有序的数组排序。

public class Shell{
    public static void sort(Comparable[] a){
        int N = a.length;
        int h = 1;
        while(h<N/3) h = 3*N+1;
        while(h>=1){
            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 = h/3;
        }
    }
}

上面的代码采用的h序列为1/2(3^k-1)。
希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序数组创造方便。
实现希尔排序的一种方法是对于每个h，用插入排序将h个子数组独立的排序。但因为子数组是独立的，更简单的方法是在h子数组中将每个元素交换到比他大的元素之前去，只需将插入排序的移动元素的距离由1改为h即可。