分治法乡洼，是算法思想里最基礎(chǔ)的思想。這也和人的基本思維有關(guān)匕坯，當(dāng)我們需要解決一個(gè)大的問題時(shí)束昵，直覺的就會(huì)將這個(gè)大問題分成多個(gè)小問題來解決。
大量的經(jīng)典算法葛峻，都是基于分治法锹雏。比如，快速排序术奖，歸并排序礁遵。當(dāng)然，最讓人想起來的采记，就是二分查找了佣耐。
分治法的步驟
分治，分而治之唧龄。分的原因是因?yàn)閱栴}的規(guī)模太大兼砖，需要拆開了解決，目的是為了解決問題既棺，分解只是手段讽挟。所以分治的步驟其實(shí)很明確:
- 分解：將大問題的分解成小問題，是這個(gè)算法的核心丸冕。也是使用分治法的效率保證戏挡，如果分解不合理。那么反而會(huì)弄巧成拙晨仑。
- 解決：解決問題褐墅，便是分解之后的小問題。他們的解決步驟是相同洪己，至少是相似的妥凳。所以，分治法中經(jīng)常用到遞歸答捕，就是基于這樣的目的逝钥。
- 合并：前面那么麻煩的兩步，最終的目的仍然是為了解決這個(gè)問題拱镐。所以需要將分解問題得到的解艘款，合并成最終需要的終極答案持际，便是這個(gè)算法的結(jié)束過程。譬如哗咆，你使用遞歸的時(shí)候蜘欲，也需要最后退出的條件。分治法結(jié)束條件晌柬，就是合并步驟的結(jié)束姥份。
遞歸與分治法的關(guān)系
雖然很多的運(yùn)用分治法的算法，都使用到了遞歸年碘。但是并不是意味著使用了遞歸的算法澈歉，就是使用了分治法。分治法也可使用迭代來實(shí)現(xiàn)呀屿衅“Ｄ眩可以這么說，一切用尾遞歸方式的算法涤久，都可以通過一個(gè)棧來迭代實(shí)現(xiàn)涡尘。遞歸只是算法的實(shí)現(xiàn)手段，基于各語言（大部分）都支持在函數(shù)內(nèi)部調(diào)用本身特性拴竹，可以減少代碼的重復(fù)悟衩。
我之所以特此說明，就是我曾經(jīng)就有這種錯(cuò)誤的認(rèn)識(shí)栓拜。
運(yùn)用實(shí)例
我前面已經(jīng)提到的快速排序座泳，歸并排序，二分查找幕与。這三種算法都是經(jīng)典的算法挑势，實(shí)現(xiàn)方法已有很多人寫了。我就不獻(xiàn)丑了啦鸣，特別引用了維基百科的快排和歸并的例子潮饱，當(dāng)然依舊是python的實(shí)現(xiàn)。
維基百科的快速排序:
def qsort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
return qsort([x for x in arr[1:] if x < pivot]) + \
[pivot] + \
qsort([x for x in arr[1:] if x >= pivot])
維基百科的歸并排序：
from collections import deque
def merge_sort(lst):
if len(lst) <= 1:
return lst
def merge(left, right):
merged,left,right = deque(),deque(left),deque(right)
while left and right:
merged.append(left.popleft() if left[0] <= right[0] else right.popleft()) # deque popleft is also O(1)
merged.extend(right if right else left)
return list(merged)
middle = int(len(lst) // 2)
left = merge_sort(lst[:middle])
right = merge_sort(lst[middle:])
return merge(left, right)
