6.1 分治：从O(N^2)到O(NlgN)

    三部曲：

    1）将一个复杂问题分解成若干个简单子问题，即divide

    2）解决每一个子问题，即conquer，如果子问题依然很大，则需要递归调用分治进一步分解，直到被分出的子问题能够被直接解决为止

    3）对子问题的结果进行合并，即combine

    1）先分为5组，每组5人，赛5次后，根据速度分别编号A1～A5，B1～B5，...，E1～E5，其中A1>A2>...>A5，以此类推

    2）A1，B1，...，E1五个小组跑最快的人赛一次，不是一般性，设速度：A1>B1>...>E1

    3）因为A1不需要赛了（已经第一），D和E组最快的人前面至少有三个人，也不用赛了直接整组淘汰。同理，可以让A2，A3，B1，B2，C1再赛一场找亚军和季军

    当K<<N时，可以综合使用【归并排序】和【堆排序】的思想，时间复杂度O((K+N)lgN)，该方法常用作国际大学挑选每个国家的新生候选人的算法：

    具体为：

    1）将N个序列从大到小排列

    2）分别在每个序列中取出最大的那个数，建堆（Max Heap）

    3）取出MaxHeap中的最大元素，并根据该元素所属的序列号来更新该序列的指针下移一个

6.2 分割算法：快速排序和中值问题

    找K个最大需要建最小堆，逆向思维排除N-K个，剩下K个，找K个最小元素则反之建最大堆

    如果使用堆排，K=N/2，那么时间复杂度退化为O(nlgn)，这时使用快速选择更好O(n)，详见《算法导论》，或者使用主定理（Master Theorem）也可：

    和快速排序相比，寻找中值或某一个K大的数虽然在代码上相差无几，但实际上，基于分割原理的中值算法并没有解决pivot之上或之下的系列数字的相互关系，因此要少做很多计算。并且，从过程上看，虽然快排和中值算法都要经过很多迭代，但是前者每次都是针对整个数组的元素，后者每次迭代比较的元素则是呈等比数列递减的。

    N选K问题有很多实际应用，比如在一亿个游戏玩家中寻找100个最活跃者奖励，或机器学习中，为权衡计算和存储成本，只保留前K个最有效的特征等。

    解决了单机版本的中值问题，那分布式的中值问题该如何解决呢？

6.4 并行初探：矩阵相乘和MapReduce

    大规模矩阵乘法可以使用分治思想进行处理：