希尔排序

java描述

public class Shell {
    
    // 实现了Comparable接口的都可以比较
    public static void sort(Comparable[] a){
        int N = a.length;
        int h = 1;
        
        // 递归数量
        while(h < N/3){
            h = 3*h + 1;    // 1, 4, 13, 40 ...
        }
        while(h >= 1){
            // 将数组变为h有序
            for (int i = h; i < N; i++){
                while( i > 0 && less(a[i], a[i-h])){
                    exch(a, i, i-h);
                    i -= h;
                }
            }
            h /=3;
        }

    }
    
    public static void main(String[] args) {
        Integer[] a = {2, 3, 1, 3, 4, 8, 6, 10};
        sort(a);
        assert isSorted(a);
        show(a);
    }
    
    public static boolean less(Comparable V , Comparable W){
        return V.compareTo(W) < 0;
    }
    
    public static void exch(Comparable[] a, int i, int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    public static void show(Comparable[] a){
        for (int i = 0; i < a.length; i++){
            System.out.print(a[i] + " ");   
        }
        System.out.println();
    }
    
    // 测试数组元素是否有序
    public static boolean isSorted(Comparable[] a){
        for (int i = 1; i < a.length; i++){
            if(less(a[i], a[i-1])){
                return false;
            }
        }
        return true;
    }
}