【演算法】一個小白的演算法筆記：歸併排序演算法的編碼和優化 (,,? ? ?,,)

02-02

參考資料

《演算法（第4版）》 — — Robert Sedgewick， Kevin Wayne

歸併排序的概念

歸併排序的實現我是這樣來描述的：先對少數幾個元素通過兩兩合併的方式進行排序，形成一個長度稍大一些的有序序列。然後在此基礎上，對兩個長度稍大一些的有序序列再進行兩兩合併，形成一個長度更大的有序序列，有序序列的的長度不斷增長，直到覆蓋整個數組的大小為止，歸併排序就完成了。

歸併排序的兩種實現方式：遞歸和循環

歸併排序有兩種實現方式：基於遞歸的歸併排序和基於循環的歸併排序。（也叫自頂向下的歸併排序和自底向上的歸併排序）

這兩種歸併演算法雖然實現方式不同，但還是有共同之處的：

1. 無論是基於遞歸還是循環的歸併排序，它們調用的核心方法都是相同的：完成一趟合併的演算法，即兩個已經有序的數組序列合併成一個更大的有序數組序列（前提是兩個原序列都是有序的！）

2. 從排序軌跡上看，合併序列的長度都是從小（一個元素）到大（整個數組）增長的

單趟歸併演算法

單趟排序的實現分析

下面我先介紹兩種不同歸併演算法調用的公共方法，即完成單趟歸併的演算法。（兩個已經有序的數組序列合併成一個更大的有序數組序列）

在開始排序前創建有一個和原數組a長度相同的空的輔助數組aux

單趟歸併的過程如下：

1. 首先將原數組中的待排序序列拷貝進輔助數組的相同位置中，即將a[low...high]拷貝進aux[low...high]中

2. 輔助數組aux的任務有兩項：比較元素大小，並在aux中逐個取得有序的元素放入原數組a中 （通過1使aux和a在low-high的位置是完全相同的！這是實現的基礎）

3. 因為aux[low...high]由兩段有序的序列：aux[low...mid]和aux[mid...high]組成，這裡稱之為aux1和aux2,我們要做的就是從aux1和aux2的頭部元素開始，比較雙方元素的大小。將較小的元素放入原數組a中（若a[0]已被占則放在a[1]...依次類推），並取得較小元素的下一個元素，和另一個序列中較大的元素比較。因為前提是aux1和aux2都是有序的，所以通過這種方法我們能得到更長的有序序列

4. 如果aux的兩段序列中，其中一段中的所有元素都已"比較"完了, 取得另一段序列中剩下的元素，全部放入原數組a的剩餘位置。

過程3和4的實現方法

設置兩個游標 i 和 j 用於「元素比較」 （在aux中進行）：變數,i 和 j，分別代表左游標和右游標，開始時分別指向aux[low]和aux[mid]
設置游標k用於確定在a中放置元素的位置（在a中進行），k在開始時候指向a[low]
總體上來說i, j, k的趨勢都是向右移動的

過程3和4的圖示解說

圖A

結合上面的過程3，比較 i 和 j 當前所指的aux中的元素的大小，取得其中比較大的那個元素（例如上圖中的i）,將其放入數組a中，此時（在圖中假設情況下）： i加1，左游標右移。同時k也加1， k游標也向右移動

圖B

結合上面的過程4，

在 i 和 j 都向右移動的過程中，在圖中假設情況下，因為j當前所指的元素（圖中位置）大於左半邊即a[low...mid]的所有元素，導致 i

不斷增加（右移）且越過了邊界（mid）,

所以這時候就不需要比較了，只要把j當前所指位置到high的元素都搬到原數組中，填滿原數組中剩下的位置，單趟歸併就完成了，在這一段過程中 j

連續加1，右游標連續右移。同時k也連續加1， k游標也連續右移，直到 j == high且k == high為止

基於上面的表述，總結出單趟歸併演算法中最關鍵的4個條件判斷情形：

左半邊用盡（取右半邊的元素）
右半邊用盡（取左半邊的元素）
右半邊元素小於左半邊當前元素（取右半邊的元素）
右半邊元素大於等於左半邊當前元素（取左半邊的元素）

單趟排序演算法的代碼

有了上面的解釋，寫這個演算法就不難了吧

/**n * @description: 完成一趟合併n * @param a 輸入數組n * @param low,mid,high a[low...high] 是待排序序列，其中a[low...mid]和 a[mid+1...high]已有序n */n private static void merge (int a [],int low,int mid,int high) {n for(int k=low;k<=high;k++){n aux[k] = a[k]; // 將待排序序列a[low...high]拷貝到輔助數組的相同位置 n }n int i = low; // 游標i,開始時指向待排序序列中左半邊的頭元素 n int j = mid+1; // 游標j,開始時指向待排序序列中右半邊的頭元素 n for(int k=low;k<=high;k++){n if(i>mid){n a[k] = aux[j++]; // 左半邊用盡n }else if(j>high){n a[k] = aux[i++]; // 右半邊用盡n }else if(aux[j]<aux[i]){n a[k] = aux[j++]; // 右半邊當前元素小於左半邊當前元素，取右半邊元素n }else {n a[k] = aux[i++]; // 右半邊當前元素大於等於左半邊當前元素，取左半邊元素 n }n }n }nn n

【注意】在排序之初創建了一個長度和原數組a相同的輔助數組aux，這部分代碼上文未給出

單趟排序的過程圖解

為了更詳細的描述單趟排序的過程，下面在上面的圖A和圖B的基礎上給出每一步的圖解：

我們要排序的序列是 2 4 5 9 1 3 6 7， 合併的前提是2 4 5 9 和 1 3 6 7都是有序的

先比較aux中2和1的大小，因為2>1，所以將1放入a[0]。這時，游標 i 不動，游標 j 右移，游標 k 右移

比較aux中2和3的大小，因為2<3，所以將2放入a[1]。這時，游標 j 不動，游標 i 右移，游標 k 右移

比較aux中4和3的大小，因為3<4，所以將3放入a[2]。這時，游標 i 不動，游標 j 右移，游標 k 右移

類似以上，不解釋

注意，這這裡 j 增加導致 j> high, 現在的情形是「右半邊用盡」，所以將aux左半邊剩餘的元素9放入a剩下的部分a[7]中，單趟排序完成

【注意】上面這個例子中的序列只是數組的一部分，並不一定是整個數組

我在上面介紹過，兩種不同歸併演算法：基於遞歸的歸併和基於循環的歸併，都是以單趟歸併的演算法為基礎的。

下面先來講一下基於遞歸的歸併排序（自頂向下的歸併排序）

基於遞歸的歸併排序（自頂向下）

基於遞歸的歸併排序又叫做自頂向下的歸併排序

遞歸歸併的思想

最關鍵的是sort(int a [], int low,int high)方法裡面的三行代碼：

sort(a,low,mid); nsort(a,mid+1,high);nmerge(a,low,mid,high);n

分別表示對左半邊序列遞歸、對右半邊序列遞歸、單趟合併操作。

全部代碼：

/**n * @Author: HuWan Pengn * @Date Created in 9:44 2017/11/29n */npublic class MergeSort {n private static int aux [];n /**n * @description: 1. 初始化輔助數組aux，使其長度和原數組相同n * 2. 包裝sort，向外只暴露一個數組參數n */n public static void sort(int a []){n aux = new int[a.length];n sort(a,0,a.length-1);n }n /**n * @description: 基於遞歸的歸併排序演算法n */n private static void sort (int a [], int low,int high) {n if(low>=high) { return; } // 終止遞歸的條件 n int mid = low + (high - low)/2; // 取得序列中間的元素n sort(a,low,mid); // 對左半邊遞歸n sort(a,mid+1,high); // 對右半邊遞歸n merge(a,low,mid,high); // 單趟合併 }n n /**n * @description: 單趟合併演算法n * @param a 輸入數組n * @param low,mid,high a[low...high] 是待排序序列,其中a[low...mid]和 a[mid+1...high]已有序n */n private static void merge (int a [],int low,int mid,int high) {n int i = low; // 游標i,開始時指向待排序序列中左半邊的頭元素 n int j = mid+1; // 游標j,開始時指向待排序序列中右半邊的頭元素 n for(int k=low;k<=high;k++){n aux[k] = a[k]; // 將待排序序列a[low...high]拷貝到輔助數組的相同位置 n }n for(int k=low;k<=high;k++){n if(i>mid){n a[k] = aux[j++]; // 左半邊用盡n }else if(j>high){n a[k] = aux[i++]; // 右半邊用盡n }else if(aux[j]<aux[i]){n a[k] = aux[j++]; // 右半邊當前元素小於左半邊當前元素，取右半邊元素n }else {n a[k] = aux[i++]; // 右半邊當前元素大於等於左半邊當前元素，取左半邊元素 n }n }n }n}n

測試代碼：

public class Test {n public static void main (String args[]){n int [] a = {1,6,3,2,9,7,8,1,5,0};n MergeSort.sort(a);n for(int i=0;i<a.length;i++){n System.out.println(a[i]);n }n }n}n

輸出結果

0n1n1n2n3n5n6n7n9n

遞歸棧深度和調用順序

遞歸導致的結果是，形成了一系列有層次、有先後調用順序的merge, 如下圖左邊的寫入編號的merge列表

從上到下，是各個merge的先後調用順序，1最先調用， 15最後調用

從右到左，遞歸棧由深到淺，例如 1,2,4,5的遞歸深度是相同的，而3比它們淺一個層次

（這裡是按照字母排序， A最小， Z最大）

對上圖可根據代碼來理解

sort(a,low,mid); // Ansort(a,mid+1,high); // Bnmerge(a,low,mid,high);// Cn

首先，在第一層遞歸的時候，先進入的是第一行的sort方法里（A處），然後緊接著又進入了第二層遞歸的第一行sort方法（A處），如此繼續，由(a, low,mid)的參數列表可知其遞歸的趨勢是一直向左移動的，直到最後一層遞歸，所以最先執行merge的對象是a[0]和a[1]（上圖編號1），再然後執行的是最後一層遞歸的第二行代碼（B處），這時候merge的對象是a[2]和a[3]（上圖編號2）。再然後，返回上一層遞歸，對已經有序的a[0]、a[1]和a[2]、a[3]進行merge。（上圖編號3）如此繼續，遞歸的深度不斷變淺，直到對整個數組的左右兩半進行merge。（上圖編號3）

遞歸歸併的軌跡圖像

（下面展示的歸併進行了一些優化，對小數組使用插入排序）

根據上文所講的遞歸棧和調用順序，下面的軌跡圖像就不難理解了：從最左邊的元素開始合併，而且左邊的數組序列在第一輪合併後，相鄰右邊的數組按同樣的軌跡進行合併，直到合併出和左邊相同長度的序列後，才和左邊合併（遞歸棧上升一層）

基於遞歸歸併排序的優化方法

優化點一：對小規模子數組使用插入排序

用不同的方法處理小規模問題能改進大多數遞歸演算法的性能，因為遞歸會使小規模問題中方法調用太過頻繁，所以改進對它們的處理方法就能改進整個演算法。 因為插入排序非常簡單，因此一般來說在小數組上比歸併排序更快。這種優化能使歸併排序的運行時間縮短10%到15%；

怎麼切換呢? 只要把作為停止遞歸條件的

if(low>=high) { return; }n

改成

if(low + M>=high) { // 數組長度小於10的時候n InsertSort.sort(int a [], int low,int high) // 切換到插入排序 return;n}n

就可以了，這樣的話，這條語句就具有了兩個功能：

1. 在適當時候終止遞歸

2. 當數組長度小於M的時候（high-low <= M），不進行歸併排序，而進行插排

具體代碼：

private static void sort (int a [], int low,int high) {n if(low + 10>=high) { // 數組長度小於10的時候 n InsertSort.sort(int a [], int low,int high) // 切換到插入排序 n return;n } // 終止遞歸的條件 n int mid = low + (high - low)/2; // 取得序列中間的元素n sort(a,low,mid); // 對左半邊遞歸n sort(a,mid+1,high); // 對右半邊遞歸n merge(a,low,mid,high); // 單趟合併n }n

優化點二: 測試待排序序列中左右半邊是否已有序

通過測試待排序序列中左右半邊是否已經有序，在有序的情況下避免合併方法的調用。

例如對單趟合併，我們對a[low...high]中的a[low...mid]和a[mid...high]進行合併

因為a[low...mid]和a[mid...high]本來就是有序的，存在a[low]<a[low+1]...<a[mid]和a[mid+1]<a[mid+2]...< a[high]這兩種關係， 如果判斷出a[mid]<=a[mid+1]的話，不就可以保證從而a[low...high]本身就是不需要排序的有序序列了嗎？

private static void sort (int a [], int low,int high) {n if(low>=high) {n return;n } // 終止遞歸的條件 n int mid = low + (high - low)/2; // 取得序列中間的元素n sort(a,low,mid); // 對左半邊遞歸n sort(a,mid+1,high); // 對右半邊遞歸 n if(a[mid]<=a[mid+1]) return; // 避免不必要的歸併n merge(a,low,mid,high); // 單趟合併n }n

優化點三：去除原數組序列到輔助數組的拷貝

在上面介紹的基於遞歸的歸併排序的代碼中，我們在每次調用merge方法時候，我們都把a對應的序列拷貝到輔助數組aux中來，即

for(int k=low;k<=high;k++){n aux[k] = a[k]; // 將待排序序列a[low...high]拷貝到輔助數組的相同位置n}n

實際上，我們可以通過一種看起來比較逆天的方式把這個拷貝過程給去除掉。。。。。

為了達到這一點，我們要在遞歸調用的每個層次交換輸入數組和輸出數組的角色，從而不斷地把輸入數組排序到輔助數組，再將數據從輔助數組排序到輸入數組。

卧槽？！還有這麼騷的操作要怎麼搞？ 請看：

public static void sort(int a []){n aux = a.clone(); // 拷貝一個和a所有元素相同的輔助數組n sort(a,aux,0,a.length-1);n }n /**n * @description: 基於遞歸的歸併排序演算法n */n private static void sort (int a[], int aux[], int low,int high) {n if(low>=high) { return; } // 終止遞歸的條件 n int mid = low + (high - low)/2; // 取得序列中間的元素n sort(aux, a,low,mid); // 對左半邊遞歸 n sort(aux, a,mid+1,high); // 對右半邊遞歸n merge(a, aux, low,mid,high); // 單趟合併n }n

在這裡我們做了兩個操作：

在排序前拷貝一個和原數組元素完全一樣的輔助數組（不再是創建一個空數組了！）
在遞歸調用的每個層次交換輸入數組和輸出數組的角色

注意，外部的sort方法和內部sort方法接收的a和aux參數剛好是相反的

這樣做的話，我們就可以去除原數組序列到輔助數組的拷貝了！

但是你可能會問：騷年，我們要排序的可是原數組a啊！你不怕一不小心最後完全排序的是輔助數組aux而不是原數組a嗎？

Dont worry !! 這種情況不會發生，看圖：

由圖示易知，因為外部sort和merge的參數順序是相同的，所以，無論遞歸過程中輔助數組和原數組的角色如何替換，對最後一次調用的merge而言（將整個數組左右半邊合為有序的操作），最終被排為有序的都是原數組，而不是輔助數組！

全部代碼：

/**n * @Author: HuWan Pengn * @Date Created in 9:44 2017/11/29n */npublic class MergeSort {n private static int aux [];n /**n * @description: 1. 初始化輔助數組aux，使其和原數組元素完全相同n * 2. 包裝sort，向外只暴露一個數組參數n */n public static void sort(int a []){n aux = a.clone(); // 拷貝一個和a所有元素相同的輔助數組n sort(a,aux,0,a.length-1);n }n /**n * @description: 基於遞歸的歸併排序演算法n */n n private static void sort (int a[], int aux[], int low,int high) {n if(low>=high) { return; } // 終止遞歸的條件 n int mid = low + (high - low)/2; // 取得序列中間的元素n sort(aux, a,low,mid); // 對左半邊遞歸n sort(aux, a,mid+1,high); // 對右半邊遞歸n merge(a, aux, low,mid,high); // 單趟合併 n }n n /**n * @description: 單趟合併演算法n * @param a 輸入數組n * @param low,mid,high a[low...high] 是待排序序列,其中a[low...mid]和 a[mid+1...high]已有序n */n private static void merge (int a [],int aux [],int low,int mid,int high) {n int i = low; // 游標i,開始時指向待排序序列中左半邊的頭元素 n int j = mid+1; // 游標j,開始時指向待排序序列中右半邊的頭元素n n // 這裡的for循環拷貝已經去除掉了 nn for(int k=low;k<=high;k++){n if(i>mid){n a[k] = aux[j++]; // 左半邊用盡n }else if(j>high){n a[k] = aux[i++]; // 右半邊用盡n }else if(aux[j]<aux[i]){n a[k] = aux[j++]; // 右半邊當前元素小於左半邊當前元素，取右半邊元素n }else {n a[k] = aux[i++]; // 右半邊當前元素大於等於左半邊當前元素，取左半邊元素 n }n }n }n}n

測試代碼和輸出結果同上文。

基於循環的歸併排序（自底向上）

基於循環的歸併排序又叫做自底向上的歸併排序

循環歸併的基本思想

基於循環的代碼較為簡單，這裡就不多贅述了

/**n* @Author: HuWan Pengn* @Date Created in 23:42 2017/11/30n*/npublic class MergeSort2 {n private static int aux [];n n public static void sort(int a []){n int N = a.length;n aux = new int [N];n for (int size =1; size<N;size = size+size){n for(int low =0;low<N-size;low+=size+size) {n merge(a,low,low+size-1,Math.min(low+size+size-1,N-1));n }n }n }n n private static void merge (int a [],int low,int mid,int high) {n int i = low; // 游標i,開始時指向待排序序列中左半邊的頭元素 n int j = mid+1; // 游標j,開始時指向待排序序列中右半邊的頭元素 n for(int k=low;k<=high;k++){n aux[k] = a[k];n }n for(int k=low;k<=high;k++){n if(i>mid){n a[k] = aux[j++]; // 左半邊用盡n }else if(j>high){n a[k] = aux[i++]; // 右半邊用盡n }else if(aux[j]<aux[i]){n a[k] = aux[j++]; // 右半邊當前元素小於左半邊當前元素，取右半邊元素n }else {n a[k] = aux[i++]; // 右半邊當前元素大於等於左半邊當前元素，取左半邊元素 n }n }n }n}n

循環歸併的軌跡圖像

（下圖中的sz同上面的變數size）

【演算法】一個小白的演算法筆記： 歸併排序演算法的編碼和優化 (,,? ? ?,,)