簡介： 分治算法，即分而治之：把一個複雜問題分成兩個或更多的相同或相似子問題，直到最後子問題可以簡單地直接求解，最後將子問題的解合併為原問題的解。
「分治算法」三步走
主要思想
分治算法，即分而治之：把一個複雜問題分成兩個或更多的相同或相似子問題，直到最後子問題可以簡單地直接求解，最後將子問題的解合併為原問題的解。歸併排序就是一個典型的分治算法。
在這篇文章中我們將先介紹分治算法的「三步走套路」，然後通過經典的歸併排序算法體驗一番分治算法的核心，最後再通過真題演練一試身手！
三步走
和把大象塞進冰箱一樣，分治算法只要遵循三個步驟即可：分解 -> 解決 -> 合併。
1.分解：分解原問題為結構相同的子問題（即尋找子問題）
2.解決：當分解到容易求解的邊界後，進行遞歸求解
3.合併：將子問題的解合併成原問題的解
簡介： 分治算法，即分而治之：把一個複雜問題分成兩個或更多的相同或相似子問題，直到最後子問題可以簡單地直接求解，最後將子問題的解合併為原問題的解。
「分治算法」三步走
主要思想
分治算法，即分而治之：把一個複雜問題分成兩個或更多的相同或相似子問題，直到最後子問題可以簡單地直接求解，最後將子問題的解合併為原問題的解。歸併排序就是一個典型的分治算法。
在這篇文章中我們將先介紹分治算法的「三步走套路」，然後通過經典的歸併排序算法體驗一番分治算法的核心，最後再通過真題演練一試身手！
三步走
和把大象塞進冰箱一樣，分治算法只要遵循三個步驟即可：分解 -> 解決 -> 合併。
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
……
整個歸併排序完整過程如下：
上部分為「分解」，下部分為「解決」與「合併」
實現
<code>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/<code>總結
分治算法的核心是尋找子問題的解，解題步驟遵循「三步走」：
1.找到子問題並分解
2.解決子問題（遞歸）
3.合併子問題的解
點擊“瞭解更多”算法必看系列其他內容
關鍵詞：算法、搜索推薦
