分治法，是算法思想里最基础的思想。这也和人的基本思维有关，当我们需要解决一个大的问题时，直觉的就会将这个大问题分成多个小问题来解决。
大量的经典算法，都是基于分治法。比如，快速排序，归并排序。当然，最让人想起来的，就是二分查找了。
分治法的步骤
分治，分而治之。分的原因是因为问题的规模太大，需要拆开了解决，目的是为了解决问题，分解只是手段。所以分治的步骤其实很明确:
- 分解：将大问题的分解成小问题，是这个算法的核心。也是使用分治法的效率保证，如果分解不合理。那么反而会弄巧成拙。
- 解决：解决问题，便是分解之后的小问题。他们的解决步骤是相同，至少是相似的。所以，分治法中经常用到递归，就是基于这样的目的。
- 合并：前面那么麻烦的两步，最终的目的仍然是为了解决这个问题。所以需要将分解问题得到的解，合并成最终需要的终极答案，便是这个算法的结束过程。譬如，你使用递归的时候，也需要最后退出的条件。分治法结束条件，就是合并步骤的结束。
递归与分治法的关系
虽然很多的运用分治法的算法，都使用到了递归。但是并不是意味着使用了递归的算法，就是使用了分治法。分治法也可使用迭代来实现呀。可以这么说，一切用尾递归方式的算法，都可以通过一个栈来迭代实现。递归只是算法的实现手段，基于各语言（大部分）都支持在函数内部调用本身特性，可以减少代码的重复。
我之所以特此说明，就是我曾经就有这种错误的认识。
运用实例
我前面已经提到的快速排序，归并排序，二分查找。这三种算法都是经典的算法，实现方法已有很多人写了。我就不献丑了，特别引用了维基百科的快排和归并的例子，当然依旧是python的实现。
维基百科的快速排序:
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)
