希尔排序

希尔排序

• 介于O(n^2)和O(nlogn)之间
• 分组插入

public class ShellSort{
    private ShellSort(){}

    public static <E extends Comparable<E>> void sort(E[] data){
        int h=data.length/2;
        while(h>=1){
            for(int start=0;start<h;start++){
                for(int i=start+h;i<data.length;i += h){
                    E t = data[i];
                    int j;
                    for(j=i;j-h>=0&&t.comparTo(data[j-h])<0;j -= h){
                        data[j]=data[j-h];
                    }
                    data[j] = t;
                }
            }
            h /= 2;
        }
    }
}

• 优化1

public static <E extends Comparable<E>> void sort(E[] data){
    int h=data.length/2;
    while(h>=1){
        for(int i=h;i<data.length;i++){
            E t = data[i];
            int j;
            for(j=i;j-h>=0&&t.comparTo(data[j-h])<0;j -= h){
                data[j]=data[j-h];
            }
            data[j] = t;
        }
        h /= 2;
    }
}

• 优化2

public static <E extends Comparable<E>> void sort(E[] data){
    int h=1;
    while(h<data.length){
        h=h*3+1;
    }
    while(h>=1){
        for(int i=h;i<data.length;i++){
            E t = data[i];
            int j;
            for(j=i;j-h>=0&&t.comparTo(data[j-h])<0;j -= h){
                data[j]=data[j-h];
            }
            data[j] = t;
        }
        h /= 3;
    }
}