困难的不是算法的思想，而是证明时间复杂度是线性。首先可以修改快排的Partition步骤，获得一个期望时间为O(n)的算法，这里姑且称之为算法1。用一些特别的办法改进Partition时主元的选择，可以获得一个最坏情况下时间复杂度为O(n)的算法，这里姑且称之为算法1a
算法1
步骤：
- 任选一个元素x作为主元，应用快排\text{Partition}的对数组进行分块（小的在前），记分块后x的下标为k
- 若k\lt \lfloor n/2\rfloor ，那么说明中位数大于x，对右侧执行第一步
- 若k\gt \lfloor n/2\rfloor ，那么说明中位数小于x，对左侧执行第一步
- 若k = \lfloor n/2 \rfloor，那么x就是中位数
\text{Partition}伪代码如下
partition(A[], l, r) {
i = l-1, j = l
p_i = random(l, r) // 等概率在[l, r)中选取一个整数
swap(A[r-1], A[p_i])
pivot = A[r-1]
while (j < r) {
if (A[j] <= pivot) {
i = i + 1
swap(A[j], A[i])
}
++j
}
return i // 返回分块后主元的位置
}
下面分析时间复杂度，可以得到递归式
T(n) = T(\max \{ n-k, k\}) + O(n)
我们假设选取主元是随机的，并且每个元素有相等的概率（即P = 1/n）被选为主元，那么对上式取期望
\begin{aligned}
E[T(n)] & = E[T(\max \{ n-k, k\}) + O(n)] \\
&= E[T(\max \{ n-k, k\})] + O(n) \\
&= \frac{1}{n} \sum_{i=0}^{n-1}E[T(\max \{ n-k, k\})] + O(n)
\end{aligned}
注意到，当k < \lfloor n/2 \rfloor时，n-k \ge k，否则k \ge n-k，那么在上面的那个合式中，T(\lfloor n/2 \rfloor + 1), T(\lfloor n/2 \rfloor + 2) , \dots, T(n-1)出现了两次，所以得到
\begin{aligned}
E[T(n)] &= \frac{1}{n} \sum_{i=0}^{n-1}E[T(\max \{ n-k, k\})] + O(n) \\
&\le \frac{2}{n} \sum_{i=\lfloor n/2\rfloor}^{n}E[T(i)] + O(n)
\end{aligned}
我们假设存在n_0，使n < n_0时有E[T(n)] = O(1)
那么n = n_0时，有
E[T(n)] = O(n)
n_0的存在是合理的，规模很小的时候，可以视为O(1)。因为递归到最后，肯定有个终止条件。比如说在这个算法中，分块的区间等于1的时候，我们可以立即得到结果。
因此我们有理由假设一直到n_1，都存在c使得E[T(n)] \le cn，当n > n_1时，把上式带入递归式
E[T(n)] \le \frac{2c}{n} \frac{ (\lfloor n/2 \rfloor + n )\lfloor n/2 \rfloor }{2} + O(n) = O(n)
由此证明了E[T(n)] = O(n)
不过这个算法最坏情况是O(n^2)的。
算法1a
虽然说算法1实现起来并不困难，但是最坏时间有时候会退化到O(n^2)，其实我们完全有办法改进选取主元的方式，使之最坏情况下时间复杂度是O(n)。
改进后的选取主元的步骤：
- 将数组切分成\lfloor n/5 \rfloor个长度为5的数组（如果最后一组不足5个元素，就丢弃掉这组，所以是向下取整）
- 找出每个切分后的组的中位数，逻辑上构成一个新的数组B
- 调用本算法，找到中位数数组的中位数，将其作为算法1第一步的主元
在数组B的中位数大于至多\lfloor 7n/10 \rfloor个元素，小于至多\lfloor 7n/10 \rfloor个元素。那么算法1的递归式可以改成。
T(n) \le T\left( \frac{7n}{10} \right) + O(n)
同样假设有T(n) \le cn，代回即可验证这一假设是正确的
T(n) \le \frac{7cn}{10} + O(n) = O(n)
