第6章，分治法，divide & conquer
分治，分而治之，先把问题划分为小问题，先解决小问题，然后把小问题的解组合得到的大问题的解。这跟归纳法类似之处在于，都是先解决小问题，再由小问题得到大问题的解。只是归纳法中小问题的解与大问题的解之间是递推关系，分治法多个小问题之间是并列关系。
经典算法有合并排序，快速排序，大整数乘法，矩阵分块乘法，寻找第k小元素，最近点对。下面先看排序算法。
在review1.2里面，已经给除了集中经典的排序算法的实现，并且给出归并排序和快速排序的时间复杂度都是O(nlogn)，而这一章给出了一个平均比较次数(不是运行时间的)的测试结果，归并排序的性能比快速排序要好一些，自底向上排序与归并排序类似。但是在实际应用中，快速排序比归并排序用的更多，这是因为快速排序是原地排序，需要的额外空间少，平均情况O(nlogn)，它隐含的常数因子小，而归并排序需要用到额外的空间，实际运行时间没有快速排序快。在wikipedia上提到了introsort，内省排序，是C++标准库里排序所使用的算法，可以参考http://zh.wikipedia.org/zh/Introsort。
大整数乘法与负数乘法类似，将4次乘法化为3次，通过减少一次乘法运算以减小时间复杂度。虽然改进后使得计算结果容易溢出，但是如果会发生溢出，不采用这种方法也是有可能发生溢出的。
矩阵分块乘法，将矩阵乘法的时间复杂度从o(n^3)减少到o(n^2.81)，虽然减少的不多，但是减少的部分在指数上，所以效果还是可观的，在n相当大的时候。只是要达到这个效果，算法过程比较复杂。
下面看寻找第k小元素的算法。
直接方法，对所有元素排序，就得到第k小的元素。由于使用排序，时间复杂度是排序的最小时间复杂度O(nlogn)。而select算法却可以在O(n)时间内找出第k小元素，这是怎么做到的呢？
先看一个例子，数组A={8,13,9,4,7,6,5,10,12,24}共10个元素，我们把A先分成多个小组，每组3个元素，即{8,13,9},{4,7,6},{5,10,12},多出一个元素暂时不管。然后可以很容易的得到每一组的中项(排序后中间位置的元素)，取出所有组的中项，得到M={9,6,10}，选出这个集合的中项，为9，接下来把元素分为小于9，等于9，大于9三组，即A1={8,4,7,6,5},A2={9},A3={13,10,12,24},然后，如果要取第k=5小的元素，那么这个元素一定在A1中，然后在A1中找第k小的元素，如果k=6，则正好是A2中的元素，k=8，那么就在A3中找k-｜A1｜-｜A2｜的元素，这可以使用递归调用。可以发现，从在n=10个元素中找第k小的元素，变为在A1找第k小或A3中找k-|A1|-|A2|小的元素，问题规模减小，而且由于划分A的元素mm是中项的中项，所以A1与A2的大小基本相同，所以每一次问题规模基本上减小一半。最后这个算法的时间复杂度是O(n)的。
代码如下，
一个比较详细的讨论select算法的地方，http://blog.csdn.net/v_JULY_v/article/details/6431001
Partion过程可以使用快速排序的划分，需要做一些修改，没有解决的问题是如果Pivot存在相同的元素，该如何处理。