快速排序轴点选取的优化
优化快速排序常数,降低比较次数的一些办法。主要是关于轴点的选取方法,如随机选取,三取样取中值,五取样划分

前面介绍过,若能在严格线性时间内选择出一个足够接近中位数的数,快速排序的时间复杂度在最坏情况下也将保持$O(nlogn)$。同理,如果这样的轴点选取算法存在,那么quickselect也可以改进为线性。

Median of Medians,或称为五取样划分,直译为“中位数的中位数”算法,就是这样一种算法。它是BFPRT算法的最简单的形式(BFPRT是五位大神的姓氏缩写:Blum,Floyd,Pratt,Rivest,Tarjan)。算法的思路其实很简单,一共五步

BFPRT算法:对于输入序列A,找其第k大的元素

  1. 将A划分为A/5个区间。除了最后一个区间的元素数量可能少于五外,其余区间元素个数都是五。(这一步需要线性时间)
  2. 对于每一个区间,使用任意一种排序算法排序,从而得到一组5-排序的序列。将每一个区间的中位数取出形成新序列B(线性)
  3. 递归调用算法自身,得到B的中位数M(T(n/5)时间)
  4. 以M为轴点进行划分,记录划分后M的秩Q(线性)
  5. 将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,而不是五取样划分。