困难的不是算法的思想，而是证明时间复杂度是线性。首先可以修改快排的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)