排序演演算法-歸併排序

排序演演算法-歸併排序

演演算法思想

歸併：將兩個或者兩個以上的有序表組合成一個新的有序表的過程。假定待排序表中含有n個記錄，則可以看成是n個有序的子表，每個子表的長度為1，然後兩兩歸併，得到$\lceil n/2\rceil$個長度為2或1的有序表；再兩兩歸併，如此一直重複，直到合併成一個長度為n的有序表為止，這種排序方法稱為2路歸併排序。

2路歸併排序的過程如下圖所示。

從歸併的過程不難看出，其程式碼實現可以基於分治思想遞迴實現。其基本問題是如何實現兩個有序序列的歸併操作，該操作可以通過使用輔助陣列以及雙指標的方式實現。

合併兩個有序陣列的程式碼：
其中nums為待排序序列，temp為輔助陣列，其長度與nums一致，low為要合併的左子序列的起點，mid為要合併的右子序列的起點。

public static void Merge(int[] nums,int[] temp, int low,int mid, int high){
        // 表的兩段nums[low...mid]與nums[mid+1...high]都有序，將兩段進行有序歸併
        for(int i=low;i<=high;++i)  // 將nums[low...high]元素複製到temp中，防止之後修改nums產生錯誤
            temp[i] = nums[i];
        int i,j,k;
        for(i=low,j=mid+1,k=i;i<mid+1 && j<=high;++k){
            if(temp[i]<temp[j])    //比較nums中的low和mid+1為起點的子序列元素
                nums[k] = temp[i++];  //將較小值複製到nums中，使得歸併後的序列有序
            else{
                nums[k] = temp[j++];
            }
        }
        while(i<mid+1) nums[k++] = temp[i++];  // 若左表未遍歷完，將左表剩餘元素複製到nums剩餘位置
        while(j<=high) nums[k++] = temp[j++];  // 若右表未遍歷完，將右表剩餘元素複製到nums剩餘位置
        // 以上while迴圈只有一最終會滿足條件
    }

Merge()的功能是將前後相鄰的兩個有序表歸併為一個有序表的演演算法。設兩段有序表$nums[low...mid]$和$nums[mid+1...high]$存放在同一順序表中相鄰的位置上，先將它們複製到輔助陣列temp中。每次從對應temp中的兩個段取出一個記錄進行關鍵字比較，將較小者放入nums中，當陣列temp中有一段的下標超出其對應的表長時（即該段的所有元素已經完全複製到nums中），將另一段的剩餘部分直接複製到nums中。

歸併排序

分解：將含有n個元素的待排序表分成各含n/2個元素的子表，採用2-路歸併排序演演算法對兩個子表遞迴地進行排序；
合併：合併兩個已排序的子表得到排序結果。

完整程式碼：

package com.sort;

public class MergeSort {
    public static void main(String[] args) {
        int[] nums = {3,8,4,5,6,8,9,0,1};
        int[] temp = new int[nums.length]; //建立輔助陣列，方便之後進行有序序列歸併
        mergesort(nums,temp,0,nums.length-1);
        for(int num:nums){
            System.out.print(num+" ");
        }
    }
    public static void mergesort(int[] nums,int[] temps,int low,int high){
        if(low<high){
            int mid = (low + high) /2;  // 從中間劃分兩個西序列
            mergesort(nums,temps,low,mid);  // 對左側子序列進行遞迴排序
            mergesort(nums,temps,mid+1,high);  // 對右側子序列進行遞迴排序
            Merge(nums,temps,low,mid,high);   //合併左右有序子序列
        }
    }
    public static void Merge(int[] nums,int[] temp, int low,int mid, int high){
        // 表的兩段nums[low...mid]與nums[mid+1...high]都有序，將兩段進行有序歸併
        for(int i=low;i<=high;++i)  // 將nums[low...high]元素複製到temp中，防止之後修改nums產生錯誤
            temp[i] = nums[i];
        int i,j,k;
        for(i=low,j=mid+1,k=i;i<mid+1 && j<=high;++k){
            if(temp[i]<temp[j])    //比較nums中的low和mid+1為起點的子序列元素
                nums[k] = temp[i++];  //將較小值複製到nums中，使得歸併後的序列有序
            else{
                nums[k] = temp[j++];
            }
        }
        while(i<mid+1) nums[k++] = temp[i++];  // 若左表未遍歷完，將左表剩餘元素複製到nums剩餘位置
        while(j<=high) nums[k++] = temp[j++];  // 若右表未遍歷完，將右表剩餘元素複製到nums剩餘位置
        // 以上while迴圈只有一最終會滿足條件
    }

}

複雜度分析

從2路歸併排序的過程圖中，易知2路歸併的歸併樹形態就是一棵「倒立」的二元樹。

時間複雜度：
如果「歸併樹」樹高為h，則歸併排序所需要的歸併趟數就為h-1趟。二元樹的第h層最多有$2^h-1$個結點。若樹高高為h，則應滿足$n<=2^h-1$，因為樹的第h層必然包含n的個結點，即可得$h-1=\lceil lo{g}_{2}n\rceil$。又因為對n個元素進行歸併排序，歸併總趟數為h-1，即n個元素進行二路歸併，歸併趟數為$\lceil lo{g}_{2}n\rceil$。
每一趟的歸併的時間複雜度，即Merge()的時間複雜度為$O(n)$，所以歸併排序的時間複雜度就為 歸併的時間複雜度 * 歸併的趟數，即時間複雜度為$O(nlo{g}_{2}n)$。無論序列有序、無序，其時間複雜度都為$O(nlo{g}_{2}n)$。

空間複雜度：
輔助陣列需要n個儲存單元，空間複雜度為$O(n)$。
遞迴的深度為數的高度，空間複雜度為$O(lo{g}_{2}n)$。
整體來看，歸併排序時間複雜度為$O(n)$。

穩定性：穩定。