Java 十大排序算法之希爾排序刨析

Posted on by

希爾排序是插入排序的一種，又稱”縮小增量排序”，是插入排序算法的一種更高效的改進版本。

希爾排序原理

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

希爾排序的API設計

類名 Shell
構造方法 Shell():創建Shell對象
成員方法

1.public static void sort(Comparable[] a):對數組內的元素進行排序

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

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

希爾排序的代碼實現

public class Shell {
    //對數組a中的元素進行排序
    public static void sort(Comparable[] a){
        int N=a.length;
        //確定增長量h的最大值
        int h=1;
        while(h<N/2){
            h=2*h+1;
        }
        //當增長量h小於1，排序結束
        while(h>=1){
            //找到待插入的元素
            for(int i=h;i<N;i++){
                //a[i]就是待插入的元素
                //把a[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]進行比較，如果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;
    }
    //數組元素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));
    }
}

測試結果：

由於增量h沒有固定的值，希爾排序的時間復雜度較為復雜，但在處理大批量數據時，希爾排序的性能高於插入排序！

到此這篇關於Java 十大排序算法之希爾排序刨析的文章就介紹到這瞭,更多相關Java 排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：