算法-分治

分治，字面意思就是分而治之，意思就是把一个复杂的问题分成两个或更多个相同或相似的子问题，解决子问题后再进行合并。典型的如归并排序和快排，都是以分治为基础的。

我们以 归并排序 来说明一个典型的分治算法的思路

分治算法可以分三步走：分解 -> 解决 -> 合并

1. 分解原问题为结构相同的子问题。
2. 分解到某个容易求解的边界之后，进行递归求解。
3. 将子问题的解合并成原问题的解。

归并排序，我们就叫这个函数 merge_sort 吧，按照我们上面说的，要明确该函数的职责，即 对传入的一个数组排序 。OK，那么这个问题能不能分解呢？当然可以！给一个数组排序，不就等于给该数组的两半分别排序，然后合并就完事了。

1
2
3
4
5
6

void merge_sort(一个数组) {
  if (可以很容易处理) return;
  merge_sort(左半个数组);
  merge_sort(右半个数组);
  merge(左半个数组, 右半个数组);
}

好了，这个算法也就这样了，完全没有任何难度。记住之前说的，相信函数的能力，传给它半个数组，那么这半个数组就已经被排好了。而且你会发现这不就是个二叉树遍历模板吗？为什么是后序遍历？因为我们分治算法的套路是 分解 -> 解决（触底）-> 合并（回溯） 啊，先左右分解，再处理合并，回溯就是在退栈，就相当于后序遍历了。至于 merge 函数，参考两个有序链表的合并，简直一模一样。