分治算法，顧名思義就是“分而治之”，即把規模較大的複雜問題拆分為若干規模較小的類似子問題，並逐個解決，最後再將各個子問題的解決結果合併，得到原始問題的結果的方法。這個技巧是很多高效算法的基礎，例如快速排序算法、歸併排序算法、快速傅里葉變換等等。
五大常用算法之分治算法
分治算法的通俗理解
一般來說，規模小的問題比規模大的問題解決起來簡單，例如數組排序問題，只有 2 個元素的數組處理起來要比有 2000 個元素的數組簡單。這是分治算法的基本立足點，也是使用條件之一，總結一下就是，對於一個規模較大的問題，可以拆分成若干不相關的子問題，並且子問題解決起來更加簡單。
分治算法在我們日常生活中無處不在，例如國家依次劃分為省市縣鎮村來管理，本質上也是因為解決“子問題”（管理村）要簡單許多。
有這樣一個非常經典的問題：生產線生產了 99 個工件，其中 1 個工件是劣品，比其他 98 個工件質量輕一些，如果用天平稱，至少多少次一定能找到這個劣品工件？
要解決這個問題，最簡單粗暴的方法是逐個比較，如果第 x 個工件比第 y 個工件輕，第 x 個工件就是劣品。那麼 99 個工件至少需要比較 50 次才能確保一定找到劣品。
逐個比較
能夠發現，使用逐個比較的方法的時間開銷與工件總數有關，如果工件總數很少，比如只有 2 個，那麼只需要比較一次就可以找到劣品了。因此該問題滿足使用“分治算法”的必要條件之一：規模較小的子問題解決起來更簡單。現在嘗試使用分治算法解決該問題：
- 將 99 個工件等分為 3 份，每份 33 個工件；
- 比較第 1、2 份，如果天平平衡，那麼劣品必定在第 3 份中，否則劣品在輕的那一份中；
- 將劣品所在的那一份再等分為 3 份，每份 11 個工件；
- 重複第 2 步；
- 將劣品所在那一份再分為 3 份，每份分別為 3、3、2 個工件；
- 重複第 2 步；
- 不管劣品所在那一份為 3 個工件還是 2 個工件，只需再比較一次，就可找到劣品。
可見，使用分治算法只需要比較 4 次就可以找到劣品，這遠低於逐個比較法的 50 次。不過也應該注意到，使用分治法找劣品時，每次拆分子問題時，
各個子問題是互不干擾的——例如其中一份的 33 個工件質量不會影響其他份的 33 個工件質量。歸併排序法
從前面這個簡單的實例可以看出，分治法有時的確能夠極大的提升解決問題的效率，事實上，在C語言程序開發中，許多優秀的算法本質上都是基於分治思想的，一個非常典型的例子就是歸併排序法，它在處理數組排序時有著不錯的效率。
在處理數組排序時，如果數組中只有 1 個元素，那麼該數組本身就可看作是排好序的數組。如果數組中有 2 個元素，那麼最多隻需比較一次就可以得到排好序的數組。這其實是歸併排序法的核心，也即規模越小的數組，對其排序越簡單。下圖是一個長度為 5 的數組，為了排序，先把它拆分到不能繼續拆為止。
拆分到不能繼續拆
顯然，“拆分到不能繼續拆”後，子問題已經變成了只有 1 個元素的數組，這樣的數組已經是“排好序”的數組了。按照我們前面討論的，現在需要做的就是把這些已經排好序的子數組合並，問題轉化為：按照順序合併有序數組，如下圖所示：
按照順序合併有序數組
歸併排序的C語言實現
根據前面的分析，使用C語言實現歸併排序法需要實現兩個子模塊：拆分和合並。拆分數組有多種方法，通常採用二等分法，設數組頭的索引為 start，數組尾的索引為 end，mid=(start+end)/2，每次平均拆分，都會將數組分為 start 到 mid，和 mid+1 到 end 兩個子數組，再對這兩個子數組執行同樣的拆分，一直到不能拆分為止。所謂“不能拆分”，其實就是數組中只有一個元素，也即 start 等於 end，這一過程非常適合使用遞歸實現。我們先確定遞歸的停止條件：
<code>void divide(int *arr, int start, int end){ if (start >= end) return;}/<code>否則，我們將繼續拆分子數組（start, mid）和（mid+1, end），這一過程的C語言代碼如下：
<code>void divide(int *arr, int start, int end){ if (start >= end) return; int mid = (start+end)/2; divide(arr, start, mid); divide(arr, mid+1, end);}/<code>關於 divide() 遞歸函數的理解，我之前的這篇文章詳細討論過。
搞定拆分模塊後，再來看看合併模塊。按照前面討論的，拆分到“不能拆為止”的都可認為是已經排好序的子數組，所以合併模塊要按照順序（本例從小到大）將子數組合並：
<code>int merge(int *arr, int start, int mid, int end){ int ln = mid-start +1; int rn = end - mid; int left[ln], right[rn]; for (int i=0; i 
C語言代碼1
我們先將要合併的拆分後的兩個子數組分別保存在 left 和 right 數組裡，應注意，這裡使用了C語言的變長數組語法，因此在編譯時要指定-std=c99選項。接著，我們逐個比較 left 和 right 中的元素，按照順序填入 arr，這一過程的C語言代碼如下所示：
<code>int merge(int *arr, int start, int mid, int end){... int i=0, j=0, k=0; for (k = start; i < ln && j < rn; ++k) { if (left[i] < right[j]) { arr[k] = left[i]; ++i; } else { arr[k] = right[j]; ++j; } }/<code>
C語言代碼2
執行完畢後，left 和 right 中可能還有剩餘元素，這些剩餘元素必定是需要放在 arr 後部分的，因此C語言代碼可以如下寫：
<code>int merge(int *arr, int start, int mid, int end){... if (i < ln) for (; i < ln; i++) { arr[k] = left[i]; ++k; } if (j < rn) for (; j < rn; ++j) { arr[k] = right[j]; ++k; }}/<code>
C語言代碼3
到這裡，merge() 函數就完成了，將之與 divide() 函數組合起來，也即：
<code>void divide(int *arr, int start, int end){ if (start >= end) return; int mid = (start+end)/2; divide(arr, start, mid); divide(arr, mid+1, end); merge(arr, start, mid, end);}/<code> 
C語言代碼4
現在 divide() 函數便可對輸入的數組 arr 排序了。
測試歸併排序法
這裡使用 8 個元素的數組做測試：
<code>int main(){ int arr[8] = {1, 3, 2, 5, 8, 7, 6, 4}; divide(arr, 0, 7); for (int i=0; i<8; i++) printf("%d ", arr[i]); printf("\\n"); return 0;}/<code>
C語言代碼5
編譯並執行這段C語言代碼，得到如下輸出：
<code># gcc t.c -std=c99# ./a.out 1 2 3 4 5 6 7 8/<code>
歸併排序算法的時間複雜度
在計算過程中，累加和比較的過程是關鍵操作，一個長度為 n 的數組在遞歸的每一層都會進行 n 次操作，分治法的遞歸層級在 logN 級別，所以整體的時間複雜度是 O(nlogn)。
歸併排序法是一個效率不錯的排序算法，可能時間複雜度看起來不是特別直觀，我們將之與簡單粗暴的“冒泡排序算法”對比，在我的機器上分別對不同規模的數組排序，得到如下結果：
排序效率對比
冒泡排序算法是比較簡單的算法，在處理規模較小的數組時和歸併排序法的效率不相上下，但是在處理規模較大的數組時，冒泡排序算法的效率逐漸遠離歸併排序了，且數組的規模越大，二者的效率差異越大，在處理 100 萬個數組元素時，歸併排序算法僅消耗 230 毫秒就處理完畢了，而冒泡排序算法在執行 2 分鐘後仍然還沒有完成，我沒有耐心等下去，提前結束它了。
小結
分治法是解決問題的優秀思想，不僅在現實生活中，在程序開發中更是如此，本文主要通過歸併算法實例討論了這一點。不過應該注意，使用分治法解決問題時，問題應該滿足以下條件：
- 問題可以拆分為若干類似的彼此不干擾的子問題
- 問題規模縮小時，更容易解決
- 子問題的解可以合併為原始問題的解
顯然，這些條件是容易理解的。
點個關注再走吧
歡迎在評論區一起討論，質疑。文章都是手打原創，每天最淺顯的介紹C語言、linux等嵌入式開發，喜歡我的文章就關注一波吧，可以看到最新更新和之前的文章哦。
閱讀更多 IT劉小虎 的文章
