Java歸并排序舉例分析

這篇文章主要介紹“Java歸并排序舉例分析”，在日常操作中，相信很多人在Java歸并排序舉例分析問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java歸并排序舉例分析”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

歸并排序原理

1.盡可能的一組數據拆分成兩個元素相等的子組，并對每一個子組繼續拆分，直到拆分后的每個子組的元素個數是1為止。
⒉將相鄰的兩個子組進行合并成一個有序的大組。
3.不斷的重復步驟2，直到最終只有一個組為止。

歸并排序API設計

歸并排序代碼實現

public class Merge {
    //輔助數組
    private static Comparable[] assist;
    //對數組a中的元素進行排序
    public static void sort(Comparable[] a){
        assist=new Comparable[a.length];
        int lo=0;
        int hi=a.length-1;
        sort(a,lo,hi);
    }
    //對數組a中從lo到hi的元素進行排序
    private static void sort(Comparable[] a,int lo,int hi){
        if(hi<=lo){
            return;
        }
        int mid=lo+(hi-lo)/2;
        //對lo到mid之間的元素進行排序
        sort(a,lo,mid);
        //對mid+1到hi之間的元素進行排序
        sort(a,mid+1,hi);
        //對lo到mid這組數據和mid到hi這組數據進行歸并
        merge(a,lo,mid,hi);
    }
    //對數組中，從lo到mid為一組，從mid+1到hi為一組，對這兩組數據進行歸并
    public static void merge(Comparable[] a,int lo,int mid,int hi){
        //lo到mid這組數據和mid+1到hi這組數據歸并到輔助數組assist對應的索引處
        int i=lo;//定義一個指針，指向assist數組中開始填充數據的索引
        int p1=lo;//定義一個指針，指向第一組數據的第一個元素
        int p2=mid+1;//定義一個指針，指向第二組數據的第一個元素
        //比較左邊小組和右邊小組中的元素大小，哪個小，就把哪個數據填充到assist數組中
        while(p1<=mid&&p2<=hi){
            if(less(a[p1],a[p2])){
                assist[i++]=a[p1++];
            }else{
                assist[i++]=a[p2++];
            }
        }
        //把未填充的數據填到assist中
        while(p1<=mid){
            assist[i++]=a[p1++];
        }
        while(p2<=hi){
            assist[i++]=a[p2++];
        }
        for(int index=lo;index<=hi;index++){
            a[index]=assist[index];
        }
    }
    //比較v元素是否小于w元素
    private static boolean less(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={8,4,6,5,7,1,3,6,2};
        Merge.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

歸并排序的時間復雜度分析

歸并排序是分治思想的最典型的例子，上面的算法中，對a[lo..hi]進行排序，先將它分為a[lo..mid]和a[mid+1..hi]兩部分，分別通過遞歸調用將他們單獨排序，最后將有序的子數組歸并為最終的排序結果。該遞歸的出口在于如果一個數組不能再被分為兩個子數組，那么就會執行merge進行歸并，在歸并的時候判斷元素的大小進行排序。

用樹狀圖來描述歸并，如果一個數組有8個元素，那么它將每次除以2找最小的子數組，共拆log8次，值為3，所以樹共有3層那么自頂向下第k層有2^k個子數組，每個數組的長度為2^(3-k)，歸并最多需要2^(3-k)次比較。因此每層的比較次數為2^k * 2^(3-k)=2^3,那么3層總共為3*2^3。

假設元素的個數為n，那么使用歸并排序拆分的次數為log2(n).所以共log2(n)層，那么使用log2(n)替換上面3*2^3中的3這個層數，最終得出的歸并排序的時間復雜度為︰log2(n)*2^(log2(n))=log2(n)*n,根據大O推導法則，忽略底數，最終歸并排序的時間復雜度為O(nlogn);
歸并排序的缺點∶
需要申請額外的數組空間，導致空間復雜度提升，是典型的以空間換時間的操作。

到此，關于“Java歸并排序舉例分析”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！