一次看懂遞迴 (Recursion) 的思維模式（二）

分治法（Merge Sort & Quick Sort）

這是遞迴系列文的第二篇文章，上一篇，我們介紹了遞迴的基本精神，不熟悉遞迴的朋友建議先看過上篇喔。本篇我們要將它應用在另一個非常經典的演算法範式 Divide And Conquer 上面，並帶大家看看用遞迴的精神要如何解決下面的兩大經典排序演算法：

1. Merge Sort
2. Quick Sort

先簡介一下，排序的用處，就是要將一個長度為 N 的 Array 中的元素，按照一定順序排列，在此我們統一採用從小到大的順序，目標如下：

將 [1,8,4,7,5,3,6,2] 轉變爲 [1,2,3,4,5,6,7,8]

但如果我們單純的用選擇排序法，也就是不停的尋找最小元素，然後放到最左邊去，這樣總共操作的次數會是 O(N²) 的時間複雜度，效能非常差。我們希望能用 O(NlogN) 的時間複雜度完成任務。上述兩個排序演算法就在做這件事，但本篇文章不會著重在時間複雜度的分析上，而是聚焦在遞迴的思維模式。那我們就開始進入正題啦！

Merge Sort

Merge Sort 中文稱作合併排序，顧名思義，他的核心精神就在合併（Merge）。所以讓我們先來理解合併這步在做什麼

假如我有兩個已經排序好的 Array，我可以在 O(N) 的時間複雜度內，將他們合併成一個排序好的 Array（N 代表兩個 Array 的長度相加）

給一個範例，假如我有兩個各自排序好的 Array 如下

1. [1, 3 ,4, 6]
2. [2, 5, 7, 8]

我們要把他們合併起來變成 [1, 2, 3, 4, 5, 6, 7, 8]。由於如何做到這件事不是本篇的重點，我們可以先當作有一個 merge(nums1, nums2) function 可以幫我們達成這件事即可！（最後我仍會附上完整程式碼，想知道細節的先不用急）。

現在，只要有了這個核心的 merge(nums1, nums2) function 後，來看我們如何靠遞迴思維解決整個排序演算法。

1. 大問題：將 [1, 8, 4, 7, 5, 3, 6, 2] 做排序
2. 小一點的問題 1：將前半部 [1, 8, 4, 7] 做排序
3. 小一點的問題 2：將後半部 [5, 3, 6, 2] 做排序

跟上一篇的問題不同，我們現在切分問題的方式不再是切下頭或尾的一個元素，而是一次就對半切，所以我們這次會生出兩個小問題，這就是鼎鼎大名的分治法 Divide and Conquer 的思維，先將問題分成兩半再各個擊破。

此時我們發現，如果能把那兩個小問題解決掉，大問題也就迎刃而解了。因為如果我們已經將左半跟右半都排序好了，接下來就是套上前面介紹的那個 merge(nums1, nums2) function 就搞定了。

那小一點的問題又該如何解決呢，你會發現結構是一模一樣的，以 [1, 8, 4, 7] 為例子：

1. 大問題：將 [1, 8, 4, 7] 做排序
2. 小一點的問題 1：將前半部 [1, 8] 做排序
3. 小一點的問題 2：將後半部 [4, 7] 做排序

於是，我們可以開始套公式了

def merge_sort(nums):
    mid = len(nums)//2 # 找到對半切的中間點
    left = merge_sort(nums[:mid]) # 處理第一個小問題，並得到回傳答案
    right = merge_sort(nums[mid:]) # 處理第二個小問題，並得到回傳答案
    return merge(left, right) # 將兩個小問題的答案，套用 merge 即可完成

最終，記得我們要定義最小問題，現在的最小問題就是 Array 裡面僅有一個元素或沒有任何元素，這時候我們什麼都不用做，因為沒有元素或僅有一個元素，當然本身就符合排序的定義了。補上最小問題後，整個演算法如下。

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    
    mid = len(arr)//2
    left = merge_sort(nums[:mid]) # 處理第一個小問題，並得到回傳答案
    right = merge_sort(nums[mid:]) # 處理第二個小問題，並得到回傳答案
    return merge(left, right) # 將兩個小問題的答案，套用 merge 即可完成

是不是非常乾淨簡單呢！最後附上完整的範例程式碼，讓大家可以實際跑跑看。其中 merge function 怎麼做跟遞迴無關，但對於喜歡知道完整細節的讀者也可以一起看。

Quick Sort

接下來，我們就來介紹 Quick Sort （中文稱快速排序法）。與 Merge Sort 相似的地方是，他也是靠對半切的概念來解決問題，只是這次我們不需要合併了，而是先透過巧妙的方式將元素換位，之後就可以讓左右半邊互不干擾。

快速排序法的核心思維：

1. 在 Array 中找到一個元素 Pivot 當中間點
2. 將 Array 元素重新排列，讓左半邊元素都小於 Pivot，右半邊元素都大於 Pivot
3. 以上這兩件事可以在 O(N) 時間內做到

下面來看實際例子

[1, 8, 4, 7, 9, 3, 6, 2, 5]

Pivot 選誰可以是隨機的，我們就先假定選擇最後一個元素（5）當作 Pivot，如此一來所有比 5 小的都要被丟到左邊去，比 5 大的都要丟到右邊去（但兩半邊各自內部的排序並無限制），我們將這個操作稱作 partition，操作完後，一種可能的結果如下

[1, 4, 3, 2, 5, 8, 6, 7, 9]

1. 左半邊的 [1, 4, 3, 2] 都比 5 小
2. 右半邊的 [8, 6, 7, 9] 都比 5 大

當然你也可以排成別的樣子，只要有符合上述條件即可。同樣的，如何做到這件事不是本篇的重點，所以我們就假設有一個已經寫好的 partition函數可以幫我們做這件事。但如果想詳細瞭解可以參考這邊。不過讀者也可以先自己想想看，只要在 O(N) 的時間複雜度內做到即可。

接下來，就是遞迴表演的時刻啦，再來看一次我們漸漸熟悉的公式

1. 大問題：將 [1, 8, 4, 7, 9, 3, 6, 2, 5] 做排序
2. 經過partition處理後的大問題：將 [1, 4, 3, 2, 5, 8, 6, 7, 9] 做排序
3. 小一點的問題 1：將 [1, 4, 3, 2] 做排序
4. 小一點的問題 2：將 [8, 6, 7, 9] 做排序

有沒有發現，這就是 partition 的妙用，一旦我們先用它將原始 Array 處理一遍，接下來，我們的 Pivot（例子中的 5）就已經擺在正確的位置上了，而接下來，我們就只需要對左半邊和右半邊各自排序完即可，而左右半邊是不會互相干擾的，這點大幅增加了我們的處理效率。

最終寫成程式碼如下（一樣不要忘了處理最小問題）

def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    
    mid = partition(nums) # 將輸入的 array 做 partition，並回傳中間點位置
    left = quick_sort(nums[:mid])
    right = quick_sort(nums[mid+1:])
    return left + [nums[mid]] + right

再回來跟我們的 Merge Sort 比較一下

1. Merge Sort: 先遞迴處理小問題，之後再做後處理 (merge)
2. Quick Sort: 先做預處理 (partition)，之後將小問題遞迴處理

兩者都是運用 Divide And Conquer 的精神，並且都是靠遞迴實現。如果到這邊都有看懂的話，恭喜你，已經開始能靈活的運用遞迴來思考問題了。

最後有一些小細節，雖然不是本篇重點，但為了怕誤人子弟，還是解說一下

1. 在 Quick Sort 選擇 Pivot 的時候，如果都選最後一個，有機會遇到很差的狀況導致時間複雜度變成 O(N²)，為了避免這件事，通常會多做一些處理，常見的手段有 randomized, median-of-3, median-of-median 等，想詳細瞭解的話一樣可以參考這邊的解釋，一般實作上喜歡用 randomized，因為寫起來容易效果也好。
2. 承上，還有另一種討人厭的狀況，是 Array 中有大量的重複元素，如果 pivot 又剛好抽到這個元素時，大量的元素會被分到同一側去（例如你讓 value 等於 pivot 的都分到左側去，那左側就會多很多），要解決這個問題，我們得採用 3-way partition，但實作上會更複雜一些。
3. 通常我們寫 Quick Sort 時，會希望可以做到 in-place 排序，也就是不再浪費額外的暫存用記憶體，直接對原始的 Array 做改動，因為這是 Quick Sort 演算法的一大優點。但要做到這件事，就不能像上面的寫法一樣使用 nums[:mid] 之類的方式，切割出 Array 的一部分去遞迴，而是僅將要處理得範圍資訊傳進遞迴的過程之中，且由於修改時是直接改動原始的 Array，因此也不需要回傳值了。

詳細完整的範例程式碼如下（採用 randomized partition），讀者可以試試看能不能看懂他，主要重點是 quick_sort_helper ，而left_index 與 right_index 分別代表當次要處理的左右界。至於 partition一樣可以先不細看。

PS: 大部分初學 quick sort 的人，應該都會覺得 partition 那段非常的難懂，事實上，如果僅是要 O(N) 時間內完成他想做的事，不管空間上的浪費的話，大可以有很多更簡單易懂的寫法，讀者也可以試著自己想想看。但由於 quick sort 的核心優勢就在於可以完全 in-place 做完，不像 merge sort 一定得浪費額外空間暫存，所以難其實是難在這個 in-place 的要求上，只準你在原本的 Array 上做各種 swap 類型的操作，當然就變得不容易懂了。

本篇到此為止，讀者如果覺得有學會的話，恭喜你對遞迴已經有初步的認識了。可以試著自己動手寫寫看，並在 Leetcode Sort an Array 上面驗證看看答案。

另外還是簡單提一下，上面兩個演算法之所以可以達到 O(NlogN) 的時間複雜度，是因為他們的遞迴深度都是 O(logN)（每次都是切一半，所以只需要 logN 步就會切到最小單位），而 Merge Sort 的後處理與 Quick Sort 的預處理都是 O(N)，所以最終乘起來就是 O(NlogN) 啦。

下一篇，我們將開始介紹另一種遞迴的常見應用 — Backtracking，他的概念會與前兩篇稍有不同，我會詳細介紹他的思維方式與使用時機，我們下回見！

系列連結

1. 遞迴基礎思維
2. 分治法 Divide And Conquer 與兩大排序法
3. 回溯法 Backtracking
4. 排列與組合（Permutation & Combination)
5. 基礎動態規劃（Dynamic Programming）