前面介绍过，若能在严格线性时间内选择出一个足够接近中位数的数，快速排序的时间复杂度在最坏情况下也将保持$O(nlogn)$。同理，如果这样的轴点选取算法存在，那么quickselect也可以改进为线性。
Median of Medians，或称为五取样划分，直译为“中位数的中位数”算法，就是这样一种算法。它是BFPRT算法的最简单的形式(BFPRT是五位大神的姓氏缩写：Blum,Floyd,Pratt,Rivest,Tarjan)。算法的思路其实很简单，一共五步
BFPRT算法：对于输入序列A，找其第k大的元素
- 将A划分为A/5个区间。除了最后一个区间的元素数量可能少于五外，其余区间元素个数都是五。（这一步需要线性时间）
- 对于每一个区间，使用任意一种排序算法排序，从而得到一组5-排序的序列。将每一个区间的中位数取出形成新序列B（线性）
- 递归调用算法自身，得到B的中位数M（T(n/5)时间）
- 以M为轴点进行划分，记录划分后M的秩Q(线性)
- 将Q与k比较，如果k小于Q，在M左侧递归；大于则在右侧递归；若相等，则算法结束（这一步的成本见下）
我的能力有限，简化其复杂度递推式为:
$$ T(n) = T(n/5) + T(\frac{3}{4}n) + O(n) $$其中O(n)是累计的各种线性操作，T(n/5)是轴点递归需要的时间，T(3n/4)是问题缩减后的规模。
由于M是B的中位数，而B中的元素本身也是中位数，都至少大于或小于对应5-序列的一半元素。所以进行一轮算法后，问题的规模至少会缩减1/2*1/2=1/4。也就是问题规模缩减为$\frac34n$
根据主定理，形如$T(n)=\sum_{i=1}^{k}T(a_{i}n) + O(n)$的递推式。如果$\sum_{i=1}^{k}a_i$小于1，则算法是线性的。显然这个算法满足此条件，所以是线性算法。
那么问题来了，为什么是五取样呢？
考虑不等式$\frac{1}{q} + \frac{3}{4} < 1$。q的最小值即是5。对于大于5的划分长度，这个算法当然还是线性的，不过用于排序的时间会增加。
此算法一般没有工程价值，但是Java的标准库里在特定情况下使用了这一方法。查看STL的std::sort，使用的是introsort，而不是五取样划分。
