算法，其本质是一种思维方式。具体实现是术，思维方式是道。对于分治算法，它对应的数学理论是数学归纳法。在程序的表现中，它 一般会和递归一起使用。
在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题 分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
这是维基百科对分治法的定义。分治法的核心思想如下：
比如在Haskell中，列表求和函数可以如下实现：
mySum :: [Int] -> Int -- 函数签名
mySum [] = 0 -- 基准情况，空列表，不能再切分为子问题了
mySum (x:xs) = x + mySum xs -- 分治
我们可以把一个列表看作是一个元素和一个列表拼在一起，比如有一个列表为 [1, 2, 3]，我们可以看成是 1 和 [2, 3] 拼在一起，
我们发现，这样可以把列表求和的问题分成一个相似的子问题，那就是1和 [2, 3] 的和，同理，[2, 3] 还可以继续细分为 2
和 [3] 的和，而 [3] 可以分为 3 和 [] 的和，那么 [] 就是基准情况，空列表的和是多少呢？显然是0，因此我们开始把
展开的递归层层向上收缩，得出最终的结果为6。
那有可能有人想问，为啥要这样做呢？为啥不直接迭代过去累加呢？这是两种不同的思维方式，关于分治，我们再来看很熟悉的一个 排序算法：合并排序。
使用Python实现合并排序如下：
def merge(array):
if len(array) == 1:
return array
mid = len(array) >> 1
left = merge(array[:mid])
right = merge(array[mid:])
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] > right[j]:
result.append(right[j])
j += 1
else:
result.append(left[i])
i += 1
result.extend(left[i:])
result.extend(right[j:])
return result
同样，基准情况是当数组只有一个值的时候，这个时候原样返回；而当数组内有多个值的时候，把数组一分为二，递归处理，然后将 递归的返回值进行合并，合并方法是，将左右两边同时遍历，每次都选择最小的那个；最后将没有遍历完的那一部分拼上去。
那么为什么可以把递归的返回值直接进行合并呢？这里就涉及到分治算法一个比较难理解的地方，突破了这一点，也就掌握了分治算法。 那就是递归信任。也就是我们的目标是，将左右半部分排序的操作分别放到递归函数里去做，当递归函数返回的时候，他们必然是有序 的，为什么呢？因为所有的递归函数都执行了合并的那一部分操作。可能有些绕，但是仔细去理解一下，就会发现不难。
我们继续扩展，除了合并排序，还有什么地方是可以用分治法去解决的呢？
日常业务实现中，也有分治法的影子。比如，在一个数据库查询中，使用IN操作，而IN后面接了10240个值，这个时候如果直接丢到SQL 里查询，那必然是要出问题的，我们可以分为10个批次，每批次1024个值去查询，然后把他们的结果进行合并处理。
这个场景是不是很熟悉呢？再比如，线程池，进程池处理多任务的时候，如果一次发起1024个线程执行任务，那系统可能会吃不消，
这个时候我们会选择一个合适大小的线程池，让他们慢慢执行，最后我们再统一处理结果(或者忽略结果)，这样的例子很多，比如
Python中的ThreadPoolExecutor，Go里的 sync.WaitGroup，Java的线程池等等。
还有什么数据结构我们可以用递归的方式(因此也就可以用分治来解决)来看待呢？
这些我们都可以把它们拆城一个值和一个相同性质的子问题来看待，因此也就可以使用分治的思维方式去解决他们。
参考资料：
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。