分而治之 divide and conquer, D&C ----- 一种解决问题的策略
先看一个例子，比如，你是一个农场主，有一小块土地，大小为1680m x 640m
现在，你想把这块土地分成许多方块，这些方块应该尽可能地大，并且均匀。解释一下这个要求就是，首先，分出的形状应该是正方形，其次，这些正方形的面积应该尽可能大，并且，分得的方块要一样大。按照这个要求，下面的分法都不符合要求：
先看第一个要求，必须是正方形，这个很好做到。只要相邻的两条边长度一样即可。
第二，分出的方块要尽可能地大。对于这块1680m x 640m的土地，我们可以找出其中存在的最大的方块，那就是640mx640m的方块。
现在，余下一块640mx400m的土地，它不是正方形。
对于这块余下的土地，我们继续使用同样的算法，找出它包含的最大的方块。显然，它是一个400mx400m的方块。
经过这一番操作，余下一块更小的土地，它的大小是400mx240m:
采用同样的方法继续划分，找出它包含的最大方块，即240mx240m的方块，又剩下一块更小的土地，它的尺寸是240mx160m:
使用一模一样的方法，从这块240mx160m的土地划出最大的方块，即160mx160m，又剩下一块160mx80m的土地：
此时此刻，我们惊奇地发现，这块160mx80m的土地，可以分成两个80mx80m的方块，因为160是80的整数倍呀，嘻嘻。
到这里，整块土地就被我们划分完成了。那么，为什么要这么分呢，这是欧几里得他老人家告诉我们的，在这里就不做证明了。用划分土地的语言来说就是，适用于余下土地的划分策略，也适用于整块地。也就是说，如果余下的一块地可以均匀地分成axa的方块，那么整块地都可以分成axa的方块。在这个例子中，最后余下的这块160mx80m的土地，可以划分成2块80mx80m的土地，所以，一开始的整块1680mx640m的土地，可以划分成好多块80mx80m的土地。这就符合了第三个划分条件，即方块的大小一样。
总结一下，我们不断找出一块土地中最大的方块，并在余下的土地中重复使用这个方法，直到最后余下一块土地，它的一条边的长度是相邻一条边长度的整数倍，此时问题得以解决。好了，现在是顿悟时间，你有木有发现，之前的原始问题，即划分1680mx640m土地的问题，每经过一步找最大方块的操作，都会变成和原来一模一样的问题，那就是找符合上面说的三个条件的划分策略，只不过这个新的问题规模比之前小，直到遇见一块相邻边可以整除的土地。其实，最后余下的这块可以被轻易分成方块的土地，是这个土地划分问题中最简单的情况，在这种情况中，我们可以一眼看出这块土地怎样划分。
也就是说，我们重复使用同样的方法，不断缩小了问题的规模（同时也降低了问题的难度），最后把一个复杂的问题变成了一个同样条件下最简单的问题，从而解决了这个问题。这种解决问题的思路称为divide and conquer，简称D&C
D&C需要注意两点：
（1）找出这个问题最简单的情况，我们把它称为基线条件。当用D&C的思想解决问题时，如果遇到了基线条件，那就可以停止缩小问题的规模了。
（2）找到一种方法，它可以不断使用以缩小问题的规模，使其符合基线条件。
递归 recursion ------ 一种编程方法
对于程序员来说，递归与D&C有着密切联系，可以说，递归就是D&C在程序上的体现。
在编程中，递归就是一个函数自己调用自己。通俗地来说，函数可以理解为一个问题的解决方法，比如在上面这个问题中，找出一块土地中最大的方块，就可以当成一个函数（就把它称为划分函数吧）。这里存在一个问题，那就是如果一个函数自己调用自己，就会陷入无限循环，永远不会停止。所以，需要基线条件，当符合基线条件时，函数停止调用自己，跳出递归。
在上面的土地次划分问题中，把1680mx640m的土地输入给划分函数，划分函数检查它并不符合基线条件（一条相邻边是另一条的整数倍），然后从这块土地中找出最大的640mx640m的方块，剩下一块640mx400m的土地。于是，最开始的问题被简化成了划分这块640mx400m的土地，这和原始问题一模一样，只是规模缩小了。划分函数是用来划分土地的，它并不在乎输入的土地尺寸有多大，重点来了，于是，它在解决原始问题的过程中，用了一次自己，由此不断调用自己，直到遇到基线条件：
划分土地函数：
输入：土地尺寸
输出：划分的方块大小
if 符合基线条件
{
return 划分的方块大小
}
else
{
找出最大的方块
以余下的土地为输入，调用划分土地函数，即调用自己
}
需要知道的是，递归程序比较耗费内存，因为每增加一层函数的调用，调用栈（call stack）就会保存上一层函数的返回地址，在这里不展开讲了。
下一个笔记正式进入快速排序算法。
参考资料：算法图解》[美] Aditya Bhargava 译者：袁国忠