希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經(jīng)過改進(jìn)之后的一個更高效的版本，也稱為縮小增量排序，同時該算法是沖破O(n2）的第一批算法之一。本文會以圖解的方式詳細(xì)介紹希爾排序的基本思想及其代碼實(shí)現(xiàn)

希爾排序原理

1.選定一個增長量h，按照增長量h作為數(shù)據(jù)分組的依據(jù)，對數(shù)據(jù)進(jìn)行分組。
2.對分好組的每一組數(shù)據(jù)完成插入排序。
3.減小增長量，最小減為1，重復(fù)第二步操作。

希爾排序的API設(shè)計(jì)

類名

Shell

構(gòu)造方法

Shell():創(chuàng)建Shell對象

成員方法

1.public static void sort(Comparable[] a):對數(shù)組內(nèi)的元素進(jìn)行排序

2.private static boolean greater(Comparable v,Comparable w):判斷v是否大于w

3.private static void exchange(Comparable[] a,int i,int j):交換a數(shù)組中，索引i和索引j處的值

希爾排序的代碼實(shí)現(xiàn)

public class Shell {
    //對數(shù)組a中的元素進(jìn)行排序
    public static void sort(Comparable[] a){
        int N=a.length;
        //確定增長量h的最大值
        int h=1;
        while(h<N/2){
            h=2*h+1;
        }
        //當(dāng)增長量h小于1，排序結(jié)束
        while(h>=1){
            //找到待插入的元素
            for(int i=h;i<N;i++){
                //a[i]就是待插入的元素
                //把a(bǔ)[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中
                for(int j=i;j>=h;j-=h){
                    //a[j]就是待插入的元素，依次和a[j-h],a[j-2h],a[j-3h]進(jìn)行比較，如果a[j]小，
                    // 那么交換位置，如果不小于，a[j]大，則插入完成
                    if(greater(a[j-h],a[j])){
                        exchange(a,j,j-h);
                    }else{
                        break;
                    }
                }
            }
            h/=2;
        }
    }
    //比較v元素是否大于w元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    //數(shù)組元素i和j交換位置
    private static void exchange(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
class Test{
    public static void main(String[] args) {
        Integer[] a={9,1,2,5,7,4,8,6,3,5};
        Shell.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

測試結(jié)果：