之前給大家介紹了幾個簡單排序，大家只需了解即可，下面介紹的大家就需要熟練掌握了，是面試高頻考點，該文章分別用了遞歸法和迭代法實現 2 路歸并，希望對大家有一丟丟的幫助。

歸并排序 (Merge Sort)

歸并排序是必須要熟練掌握的排序算法，是面試高頻考點，下面我們就一起來扒一扒歸并排序吧，原理很簡單，大家一下就能搞懂。

袁記菜館內

第 23 屆食神爭霸賽開賽啦!

袁廚想在自己排名前4的分店中，挑選一個最優秀的廚師來參加食神爭霸賽，選拔規則如下。

第一場 PK：每個分店選出兩名廚師，首先進行店內 PK,選出店內里的勝者

第二場 PK: 然后店內的優勝者代表分店挑戰其他某一分店的勝者(半決賽)

第三場 PK：最后剩下的兩名勝者進行PK,選出最后的勝者。

示意圖如下

廚神爭霸賽

上面的例子大家應該不會陌生吧，其實我們歸并排序和食神選拔賽的流程是有些相似的，下面我們一起來看一下歸并排序吧。

歸并這個詞語的含義就是合并，并入的意思，而在我們的數據結構中的定義是將兩個或兩個以上的有序表合成一個新的有序表。而我們這里說的歸并排序就是使用歸并的思想實現的排序方法。

歸并排序使用的就是分治思想。顧名思義就是分而治之，將一個大問題分解成若干個小的子問題來解決。小的子問題解決了，大問題也就解決了。分治后面會專門寫一篇文章進行描述，這里先簡單提一下。

下面我們通過一個圖片來描述一下歸并排序的數據變換情況，見下圖。

歸并排序

我們簡單了解了歸并排序的思想，從上面的描述中，我們可以知道算法的歸并過程是比較難實現的，這也是這個算法的重點，我們先通過一個視頻來看一下歸并函數的具體步驟，看完我們這個視頻就能懂個大概啦。

視頻號

視頻中歸并步驟大家有沒有看懂呀，沒看懂也不用著急，下面我們一起來拆解一下，歸并過程共分三步走。

第一步：創建一個額外大集合用于存儲歸并結果，長度則為那兩個小集合的和，從視頻中也可以看出

第二步：我們從左自右比較兩個指針指向的值，將較小的那個存入大集合中，存入之后指針移動，并繼續比較，直到某一小集合的元素全部都存到大集合中。見下圖

合并

第三步：當某一小集合元素全部放入大集合中，則需將另一小集合中剩余的所有元素存到大集合中，見下圖

好啦，看完視頻和圖解是不是能夠寫出個大概啦，了解了算法原理之后代碼寫起來就很簡單啦，

下面我們看代碼吧。

注：這里用了System.arraycopy()，大家也可以使用其他方法,其中的五個參數分別是，源數組，目的數組，源數組起始索引，目的數組放置的起始索引，復制的長度

class Solution { 
    public int[] sortArray(int[] nums) { 
        mergeSort(nums,0,nums.length-1); 
        return nums; 
    } 
    public void mergeSort(int[] arr, int left, int right) { 
        if (left < right) { 
            int mid = left + ((right - left) >> 1); 
            mergeSort(arr,left,mid); 
            mergeSort(arr,mid+1,right); 
            merge(arr,left,mid,right); 
        } 
    }  
    //歸并 
    public void merge(int[] arr,int left, int mid, int right) { 
        //第一步，定義一個新的臨時數組 
        int[] temparr = new int[right -left + 1]; 
        int temp1 = left, temp2 = mid + 1; 
        int index = 0; 
        //對應第二步，比較每個指針指向的值，小的存入大集合 
        while (temp1 <= mid && temp2 <= right) { 
            if (arr[temp1] <= arr[temp2]) { 
                temparr[index++] = arr[temp1++]; 
            } else { 
                temparr[index++] = arr[temp2++]; 
            } 
        } 
        //對應第三步，將某一小集合的剩余元素存到大集合中 
        if (temp1 <= mid) System.arraycopy(arr, temp1, temparr, index, mid - temp1 + 1); 
        if (temp2 <= right) System.arraycopy(arr, temp2, temparr, index, right -temp2 + 1);     
        System.arraycopy(temparr,0,arr,0+left,right-left+1);  
    } 
} 

歸并排序時間復雜度分析

我們一趟歸并，需要將兩個小集合的長度放到大集合中，則需要將待排序序列中的所有記錄掃描一遍所以時間復雜度為O(n)。

歸并排序把集合一層一層的折半分組，則由完全二叉樹的深度可知，整個排序過程需要進行 logn(向上取整)次,則總的時間復雜度為 O(nlogn)。

另外歸并排序的執行效率與要排序的原始數組的有序程度無關，所以在最好，最壞，平均情況下時間復雜度均為 O(nlogn) 。

雖然歸并排序時間復雜度很穩定，但是他的應用范圍卻不如快速排序廣泛，這是因為歸并排序不是原地排序算法，空間復雜度不為 O(1)，那么他的空間復雜度為多少呢?

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

歸并排序所創建的臨時結合都會在方法結束時釋放，單次歸并排序的最大空間是 n ,所以歸并排序的空間復雜度為 O(n).

歸并排序的穩定性分析

歸并排序的穩定性，要看我們的 merge 函數，我們代碼中設置了 arr[temp1] <= arr[temp2] ，當兩個元素相同時，先放入arr[temp1] 的值到大集合中，所以兩個相同元素的相對位置沒有發生改變，所以歸并排序是穩定的排序算法。

等等還沒完嘞，不要走呀。

歸并排序的遞歸實現是比較常見的，也是比較容易理解的，下面我們一起來扒一下歸并排序的迭代寫法?？纯此窃趺磳崿F的。

我們通過一個視頻來了解下迭代方法的思想

視頻號

是不是通過視頻了解個大概啦，下面我們來對視頻進行解析。

迭代實現的歸并排序是將小集合合成大集合，小集合大小為 1,2,4,8,…..。依次迭代，見下圖

比如此時小集合大小為 1 。兩個小集合分別為 [3],[1]。

然后我們根據合并規則，見第一個視頻，將[3],[1]合并到臨時數組中，則小的先進，進而實現了排序，然后再將臨時數組的元素復制到原來數組中。則實現了一次合并。

下面則繼續合并[4],[6]。具體步驟一致。所有的小集合合并完成后，則小集合的大小變為 2，繼續執行剛才步驟，見下圖。

此時子集合的大小為 2 ，則為 [2,5],[1,3] 繼續按照上面的規則合并到臨時數組中完成排序。這就是迭代法的具體執行過程，

下面我們直接看代碼吧。

注：遞歸法和迭代法的 merge 函數代碼一樣。

class Solution { 
    public int[] sortArray (int[] nums) { 
        //代表子集合大小，1，2，4，8，16..... 
        int k = 1; 
        int len = nums.length; 
        while (k < len) { 
            mergePass(nums,k,len); 
            k *= 2; 
        } 
        return nums; 
 
    } 
    public void mergePass (int[] array, int k, int len) { 
 
         int i; 
         for (i = 0; i < len-2*k; i += 2*k) { 
             //歸并 
             merge(array,i,i+k-1,i+2*k-1); 
         } 
         //歸并最后兩個序列 
         if (i + k < len) { 
             merge(array,i,i+k-1,len-1); 
         } 
 
    } 
     public void merge (int[] arr,int left, int mid, int right) { 
        //第一步，定義一個新的臨時數組 
        int[] temparr = new int[right -left + 1]; 
        int temp1 = left, temp2 = mid + 1; 
        int index = 0; 
        //對應第二步，比較每個指針指向的值，小的存入大集合 
        while (temp1 <= mid && temp2 <= right) { 
            if (arr[temp1] <= arr[temp2]) { 
                temparr[index++] = arr[temp1++]; 
            } else { 
                temparr[index++] = arr[temp2++]; 
            } 
        } 
        //對應第三步，將某一小集合的剩余元素存到大集合中 
        if (temp1 <= mid) System.arraycopy(arr, temp1, temparr, index, mid - temp1 + 1); 
        if (temp2 <= right) System.arraycopy(arr, temp2, temparr, index, right -temp2 + 1);    
        //將大集合的元素復制回原數組 
        System.arraycopy(temparr,0,arr,0+left,right-left+1);  
    } 
} 

通過上面的視頻解析和代碼，希望大家能夠將歸并排序給拿下，下面會給大家寫一下，歸并排序在實際刷題時的應用，感謝閱讀。

本文轉載自微信公眾號「袁廚的算法小屋」，可以通過以下二維碼關注。轉載本文請聯系袁廚的算法小屋 公眾號。