【初级排序算法】希尔排序

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

Java代码

public class Shell extends Sort{

    public static void sort(Comparable[] a){
        int N = a.length;
        int h = 1;
        while (h < N/3){
            h = 3*h + 1;
        }
        while (h >=1 ){
            System.out.println(h);
            for (int i = h; i < N; i++){
                for (int j = i; j >=h && less(a[j], a[j-h]); j-=j){
                    exch(a,j,j-h);
                }
            }
            h = h/3;
        }
    }

}

使用递增序列1,4,13,40,121 ... 的希尔排序所需要的比较次数不会超出N的若干倍乘以递增序列的长度。