原文連結
「分治算法」三步走
主要思想
分治算法，即分而治之：把一個複雜問題分成兩個或更多的相同或相似子問題，直到最後子問題可以簡單地直接求解，最後将子問題的解合并為原問題的解。歸并排序就是一個典型的分治算法。
在這篇文章中我們将先介紹分治算法的「三步走套路」，然後通過經典的歸并排序算法體驗一番分治算法的核心，最後再通過真題演練一試身手！
三步走
和把大象塞進冰箱一樣，分治算法隻要遵循三個步驟即可：分解 -> 解決 -> 合并。
1.分解：分解原問題為結構相同的子問題（即尋找子問題）
2.解決：當分解到容易求解的邊界後，進行遞歸求解
3.合并：将子問題的解合并成原問題的解
分治算法三步走
這麼一說似乎還是有點抽象？那我們通過經典的排序算法歸并排序來體驗一下分治算法的核心思想。
歸并排序
思想
歸并排序的思想是：欲使序列有序，必先使其子序列有序。即先使得每個子序列有序，然後再将子序列合并成有序的清單。
是以，在歸并排序中的子問題就是：使子序列有序。
既然已經找到了問題的子問題，是時候套用我們上述的三步走方法了。歸并排序的「三步走」如下：
1.分解：将序列劃分為兩部分
2.解決：遞歸地分别對兩個子序列進行歸并排序
3.合并：合并排序後的兩個子序列
舉例
來看一個具體的例子。
現在有一個待排序的序列：
10, 4, 6, 3, 8, 2, 5, 7
先對序列進行分解，把該序列一分為二，直到無法拆分為止。整個拆分過程如下：
序列分解
然後對分解出的序列進行兩兩排序與合并：
10, 4 排序合并後：4, 10
6, 3 排序合并後：3, 6
8, 2 排序合并後：2, 8
5, 7 排序合并後：5, 7
……
整個歸并排序完整過程如下：
上部分為「分解」，下部分為「解決」與「合并」
實作
def merge_sort(lst):
# 從遞歸中傳回長度為1的序列
if len(lst) <= 1:
return lst
middle = len(lst) / 2
# 1.分解：通過不斷遞歸，将原始序列拆分成 n 個小序列
left = merge_sort(lst[:middle])
right = merge_sort(lst[middle:])
# 進行排序與合并
return merge(left, right)
def merge(left, right):
i, j = 0, 0
result = []
# 2.解決：比較傳入的兩個子序列，對兩個子序列進行排序
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 3.合并：将排好序的子序列合并
result.extend(left[i:])
result.extend(right[j:])
return result 總結
分治算法的核心是尋找子問題的解，解題步驟遵循「三步走」：
1.找到子問題并分解
2.解決子問題（遞歸）
3.合并子問題的解
參考資料
- OI Wiki: 遞歸 – 分治： https://oi-wiki.org/basic/divide-and-conquer/
下一章節來了解一下
什麼是連結清單？了解更多算法内容，請持續關注：
阿裡雲開發者社群算法程式設計官方技術圈!
來源 | 五分鐘學算法
作者 | 江子抑