快速排序与快速选择算法

之所以突然会对这个问题感兴趣是因为，大概一年前，在毫无准备的情况下去参加某互联网公司的面试，被问到了这样一个问题：“给定一个长度为n的数列，如何快速的找出其中第m大的元素。假设m远小于n。”因为对排序和选择算法完全不熟悉，只知道quicksort的时间复杂度应该是$n\log(n)$，以及从数列中找出最大值的复杂度是 $n$。只好回答最简单暴力的算法，每次选出最大值然后剔除，这样m次后就找到了第m大的元素，相应的复杂度是$mn$。其实当时心里也清楚这显然离最优解有相当大的差距。毕竟这种算法不仅把第m大的元素找出来，还把前m大的都找了出来，而且排好了顺序，多做了很多无用功。况且找出最大值的复杂度只是$n$，找出第m大的不应该比这一复杂度高太多。最近又要准备面试，刷算法题，所以就把排序和选择问题专门看了看。

首先，排序问题和选择问题相关但又不同。排序问题的复杂度要高于选择问题。但是选择问题在解决的过程中又不可避免的会一定程度的对数列进行部分排序——当然如果仅仅是为了选择，副产品部分排序越少越好。我们这里集中在快速排序quicksort，快速选择quickselect，以及mergesort，三种算法。从名字就可以看出，一三是排序算法，二是选择算法。其中quickselect又涉及一种pivotselect的算法：median of medians。

QuickSort

quicksort算法的核心想法就是“分而治之”(divide and conquer)。随机选择一个轴(pivot)，把大于轴的数移到轴的左侧，小于轴的值移到右侧，这样轴的位置就处于最终正确排序的位置。然后对轴两侧重复这一操作，直到排出全序。时间复杂度的分析也很简单，由于每一轮的比较操作都小于$n$，所以只要知道迭代多少次停止即可。最好的情况，每次都恰好选到中位数做轴，这样最多$\log_2(n)$轮就可以完成排序，总的时间复杂度就是$n\log(n)$。最差的情况，每次都选到最大或最小值做轴，这样相当于每轮迭代序列的长度只减少了1，所以就需要$n$轮才能完成排序，复杂度就是$n^2$。至于平均的情况，假设长度为$n$的序列quicksort的平均时间代价是$C(n)$，而排序后轴值左边的序列长度为$i$，那么

$$\begin{align} C(n) & = n-1 + \frac{1}{n}\sum_{i=0}^{n-1}C(n-i-1)+C(i) \\ C(n) & = n-1 + \frac{2}{n}\sum_{i=0}^{n-1}C(i) \\ nC(n)-(n-1)C(n-1) & = 2(n-1) + 2C(n-1) \\ C(n) & = \frac{2(n-1)}{n} + \frac{n+1}{n}C(n-1) \\ \frac{C(n)}{2n} & \le \frac{C(n-1)}{2(n-1)} + \frac1n \\ C(n) & \le 2n\ln(n)\,. \end{align}$$

QuickSelect

下面我们在来看看快速选择算法。核心思想与quicksort一样，也是不断的将轴放到正确的位置。但因为只需要选择一个元素，所以每次只需要对包含目标元素的那一侧继续处理。对于简单版本的quickselect来说，这就足够了，其平均时间代价就是$O(n)$。因为轴是按照均匀分布选取，那么它落在四分位区间的概率就是$1/2$，也就是说较长的那边最多也只有$3n/4$。而另外$1/2$的概率，我们用$n$作为上界。这样按照不断选取子序列的方式，到子序列长度为$1$。假设长度为$n$的情况下，quickselect的平均代价为$C(n)$，那么我们就有

$$\begin{align} C(n) & \le n+\frac12C(3n/4)+\frac12C(n) \\ C(n) & \le 2n + C(3n/4) \\ C(n) & \le \sum_{i=0}^\infty\left(\frac34\right)^i2n \\ & = O(n)\,. \end{align}$$

当然，最差的情况时间代价会达到$n^2$。

为了避免最差的情况出现，我们在选择轴的时候就需要慎重一些。相应的就有了median of medians的算法。其想法就是把当前序列划分成长度为5或者更大的奇数的片段，找出每个片段的中位数，再去找出这些中位数的中位数。在一个小片段上求中位数显然只需要依赖于片段长度的时间，在所有片段上都求中位数就是$O(n)$的复杂度。而去求中位数们的中位数时，使用迭代回quickselect的办法。迭代回去的序列长度就只有$n/5$。而找出中位数的中位数作为轴，最差也能使序列长度减少$1/5+1/10 = 3/10$。假设结合了median of medians的quickselect的平均代价为$C(n)$，那么，

$$\begin{align} C(n) & \le n + C(7n/10) + C(n/5) + O(n) \\ C(n) & \le O(n) + C(9n/10) \\ & = O(n)\,. \end{align}$$

显然，median of medians与quicksort结合也可以将它在最差情形下的时间代价提升至$O(n\log n)$。

MergeSort

最后我们再来看看mergesort。它是一种最好，最差和平均复杂度都是$O(n\log n)$的排序算法。其想法十分简单，就是把序列分解为长度为2的小片段，经过$n/2$次比较，将他们完全排序。然后再将小片段两两合并，形成每个长度为4的片段最多需要3次比较，共$3n/4$次比较。然后继续两两结合，以此类推。显然总的时间复杂度就介于$n\log_2 n$与$\frac n2\log_2 n$之间。但是mergesort的优势在于易于并行实现。