史上最清晰的「歸併排序」講解

  • 2020 年 10 月 29 日
  • 筆記

那我們借用 cs50 里的例子，比如要把一摞卷子排好序，那用並歸排序的思想是怎麼做的呢？

  1. 首先把一摞卷子分成兩摞；
  2. 把每一摞排好序；
  3. 把排好序的兩摞再合併起來。

感覺啥都沒說？
那是因為上面的過程里省略了很多細節，我們一個個來看。

  1. 首先分成兩摞的過程，均分，奇偶數無所謂，也就是多一個少一個的問題；

  2. 那每一摞是怎麼排好序的？

答案是用同樣的方法排好序。

  1. 排好序的兩摞是怎麼合併起來的？

這裡需要藉助兩個指針和額外的空間，然後左邊畫一個彩虹🌈右邊畫個龍🐲，不是，是左邊拿一個數，右邊拿一個數，兩個比較大小之後排好序放回到數組裡（至於放回原數組還是新數組稍後再說）。

這其實就是分治法 divide-and-conquer 的思想。
歸併排序是一個非常典型的例子。

分治法

顧名思義：分而治之。

就是把一個大問題分解成相似的小問題，通過解決這些小問題，再用小問題的解構造大問題的解。

聽起來是不是和之前講遞歸的時候很像？

沒錯，分治法基本都是可以用遞歸來實現的。

在之前，我們沒有加以區分，當然現在我也認為不需要加以區分，但你如果非要問它們之間是什麼區別，我的理解是：

  • 遞歸是一種編程技巧，一個函數自己調用自己就是遞歸；
  • 分治法是一種解決問題的思想：

    • 把大的問題分解成小問題的這個過程就叫「分」，
    • 解決小問題的過程就叫「治」，
    • 解決小問題的方法往往是遞歸。

所以分治法的三大步驟是：

「分」：大問題分解成小問題；

「治」：用同樣的方法解決小問題；

「合」：用小問題的解構造大問題的解。

那回到我們的歸併排序上來：

「分」：把一個數組拆成兩個；

「治」：用歸併排序去排這兩個小數組；

「合」：把兩個排好序的小數組合併成大數組。

這裡還有個問題，就是什麼時候能夠解決小問題了？

答：當只剩一個元素的時候，直接返回就好了，分解不了了。
這就是遞歸的 base case，是要直接給出答案的。

老例子：{5, 2, 1, 0}

暗示著齊姐對你們的愛啊～❤️

Step1.

先拆成兩半，
分成兩個數組：{5, 2} 和 {1, 0}

Step2.

沒到 base case，所以繼續把大問題分解成小問題：

當然了，雖然左右兩邊的拆分我都叫它 Step2，但是它們並不是同時發生的，我在遞歸那篇文章里有說原因，本質上是由馮諾伊曼體系造成的，一個 CPU 在某一時間只能處理一件事，但我之所以都寫成 Step2，是因為它們發生在同一層 call stack，這裡就不在 IDE 里演示了，不明白的同學還是去看遞歸那篇文章里的演示吧。

Step3.

這一層都是一個元素了，是 base case，可以返回併合並了。

Step4.

合併的過程就是按大小順序來排好，這裡藉助兩個指針來比較，以及一個額外的數組來輔助完成。

比如在最後一步時，數組已經變成了：
{2, 5, 0, 1}，
那麼通過兩個指針 i 和 j，比較指針所指向元素的大小，把小的那個放到一個新的數組？里，然後指針相應的向右移動。

其實這裡我們有兩個選擇：

  • 一種是從新數組往原數組合併，
  • 另一種就是從原數組往新數組裡合併。

這個取決於題目要求的返回值類型是什麼；以及在實際工作中，我們往往是希望改變當前的這個數組，把當前的這個數組排好序，而不是返回一個新的數組，所以我們採取從新數組往原數組合併的方式，而不是把結果存在一個新的數組裡。

那具體怎麼合併的，大家可以看下15秒的小動畫：

擋板左右兩邊是分別排好序的，那麼合併的過程就是利用兩個指針，誰指的數字小，就把這個數放到結果里，然後移動指針，直到一方到頭（出界）。

public class MergeSort {
public void mergeSort(int[] array) {
 if(array == null || array.length <= 1) {
  return;
 }
 int[] newArray = new int[array.length];
 mergeSort(array, 0, array.length-1, newArray);
}
private void mergeSort(int[] array, int left, int right, int[] newArray) {
  // base case
 if(left >= right) {
  return;
 }

  // 「分」
 int mid = left + (right - left)/2;
 
  // 「治」
  mergeSort(array, left, mid, newArray);
 mergeSort(array, mid + 1, right, newArray);
 
  // 輔助的 array
 for(int i = left; i <= right; i++) {
  newArray[i] = array[i];
 }
 
  // 「合」
 int i = left;
 int j = mid + 1;
 int k = left;
 while(i <= mid && j <= right) {
  if(newArray[i] <= newArray[j]) { // 等號會影響演算法的穩定性
   array[k++] = newArray[i++];
  } else {
   array[k++] = newArray[j++];
  }
 }
 if(i <= mid) {
  array[k++] = newArray[i++];
 }
}
}

寫的不錯，我再來講一下：

首先定義 base case，否則就會成無限遞歸死循環，那麼這裡是當未排序區間里只剩一個元素的時候返回，即左右擋板重合的時候，或者沒有元素的時候返回。

「分」

然後定義小問題，先找到中點，

  • 那這裡能不能寫成 (left+right)/2 呢？
  • 注意⚠️，是不可以的哦。
    雖然數學上是一樣的，
    但是這樣寫，
    有可能出現 integer overflow.

「治」

這樣我們拆好了左右兩個小問題，然後用「同樣的方法」解決這兩個自問題，這樣左右兩邊就都排好序了～

  • 為什麼敢說這兩邊都排好序了呢？
  • 因為有數學歸納法在後面撐著～

那在這裡，能不能把它寫成：

mergeSort(array, left, mid-1, newArray);
mergeSort(array, mid, right, newArray);

也就是說，

  • 左邊是 [left, mid-1]，
  • 右邊是 [mid, right]，

這樣對不對呢？

答案是否定的。

因為會造成無限遞歸。

最簡單的，舉個兩個數的例子，比如數組為{1, 2}.

那麼 left = 0, right = 1, mid = 0.

用這個方法拆分的數組就是：

  • [0, -1], [0, 1] 即：
  • 空集，{1, 2}

所以這樣來分並沒有縮小問題，沒有把大問題拆解成小問題，這樣的「分」是錯誤的，會出現 stack overflow.

再深一層，究其根本原因，是因為 Java 中的小數是「向零取整」。

所以這裡必須要寫成：

  • 左邊是 [left, mid]，
  • 右邊是 [mid + 1, right]。

「合」

接下來就是合併的過程了。

在這裡我們剛才說過了，要新開一個數組用來幫助合併，那麼最好是在上面的函數里開，然後把引用往下傳。開一個，反覆用，這樣節省空間。

我們用兩個指針：i 和 j 指向新數組，指針 k 指向原數組，開始剛才動畫里的移動過程。

要注意，這裡的等於號跟哪邊，會影響這個排序演算法的穩定性。不清楚穩定性的同學快去翻一下上一篇文章啦～

那像我程式碼中這種寫法，指針 i 指的是左邊的元素，遇到相等的元素也會先拷貝下來，所以左邊的元素一直在左邊，維持了相對順序，所以就是穩定的。

最後我們來分析下時空複雜度：

時間複雜度

歸併排序的過程涉及到遞歸，所以時空複雜度的分析稍微有點複雜，在之前「遞歸」的那篇文章里我有提到，求解大問題的時間就是把所有求解子問題的時間加起來，再加上合併的時間。

我們在遞歸樹中具體來看：

這裡我右邊已經寫出來了：

「分」的過程，每次的時間取決於有多少個小問題，可以看出來是
1，2，4，8…這樣遞增的，
那麼加起來就是O(n).

「合」的過程，每次都要用兩個指針走完全程，每一層的 call stack 加起來用時是 O(n)，總共有 logn 層，所以是 O(nlogn).

那麼總的時間，就是 O(nlogn).

空間複雜度

其實歸併排序的空間複雜度和程式碼怎麼寫的有很大的關係，所以我這裡分析的空間複雜度是針對我上面這種寫法的。

要注意的是，遞歸的空間複雜度的分析並不能像時間複雜度那樣直接累加，因為空間複雜度的定義是在程式運行過程中的使用空間的峰值，本身就是一個峰值而非累加值的概念。

那也就是 call stack 中，所使用空間最高的時刻，其實就是遞歸樹中最右邊的這條路線：它既要存著左邊排好序的那半邊結果，還要把右邊這半邊繼續排，總共是 O(n).

那有同學說 call stack 有 logn 層，為什麼不是 O(logn)，因為每層的使用的空間不是 O(1) 呀。

擴展：外排序

這兩節介紹的排序演算法都屬於內部排序演算法，也就是排序的過程都是在記憶體中完成。

但在實際工作中，當數據量特別大時，或者說比記憶體容量還要大時，數據就無法一次性放入記憶體中，只能放在硬碟等外存儲器上，這就需要用到外部排序演算法演算法來完成。一個典型的外排序演算法就是外歸併排序（External Merge Sort）。

這才是一道有意思的面試題，在經典演算法的基礎上，加上實際工作中的限制條件，和面試官探討的過程中，就能看出 candidate 的功力。

要解決這個問題，其實是要明確這裡的限制條件是什麼：

首先是記憶體不夠。那除此之外，我們還想盡量少的進行硬碟的讀寫，因為很慢啊。

比如就拿wiki[1]上的例子，要對 900MB 的數據進行排序，但是記憶體只有 100MB，那麼怎麼排呢？

  1. wiki 中給出的是讀 100MB 數據至記憶體中，我並不贊同，因為無論是歸併排序還是快排都是要費空間的，剛說的空間複雜度 O(n) 不是，那數據把記憶體都佔滿了，還怎麼運行程式？那我建議比如就讀取 10MB 的數據，那就相當於把 900MB 的數據分成了 90 份；
  2. 在記憶體中排序完成後寫入磁碟；
  3. 把這 90 份數據都排好序，那就會產生 90 個臨時文件；
  4. 用 k-way merge 對著 90 個文件進行合併，比如每次讀取每個文件中的 1MB 拿到記憶體里來 merge，保證加起來是小於記憶體容量且能保證程式能夠運行的。

那這是在一台機器上的，如果數據量再大，比如在一個分散式系統，那就需要用到 Map-Reduced 去做歸併排序，感興趣的同學就繼續關注我吧～

如果你喜歡這篇文章，記得給我點贊留言哦～你們的支援和認可，就是我創作的最大動力，我們下篇文章見！

我是小齊，紐約程式媛，終生學習者，每天晚上 9 點，雲自習室里不見不散！

更多乾貨文章見我的 Github: //github.com/xiaoqi6666/NYCSDE

參考資料

[1]

外排序: //zh.wikipedia.org/wiki/%E5%A4%96%E6%8E%92%E5%BA%8F


VirMach 便宜 VPS

QNews

QNews