『算法导论』第 9 章：中位数与顺序统计量

本章讨论 顺序统计量 ，即某个集合中大小排名第几的元素。比如最小值是第一个顺序统计量，最大值是最后一个顺序统计量， 中位数 是集合的中点元素。如果元素有奇数个，有唯一的中位数；如果元素有偶数个，有两个中位数，一般选取较小的那个。将问题一般化，则是从含有互异元素的集合中找到特定大小排名的元素。

最小值和最大值

在一个含有$n$个元素的集合中，最多需要$n-1$次比较就能确定最小元素。下面是代码实现：

int mininum(int A[], int n)
{
    int min = A[0];
    for (int i = 1; i < n; i++) {
        if (min > A[i]) {
            min = A[i];
        }
    }
    return min;
}

这是是最好的结果，对于最小值问题，至少也需要$n-1$次比较。

在某些应用中，我们需要同时找到最大值和最小值。最简单的办法是分别独立地找到最大值和最小值，那么一共需要$2n-2$次比较。实际上有更好的办法，可以对输入元素成对地处理：首先将它们相互比较，然后把较小的与当前最小值比较，把最大的与当前最大值比较。这样每两个元素共需要3次比较。总的比较次数至多是$3 \lfloor n/2 \rfloor$。

期望为线性时间的选择算法

一般选择问题看起来要比找最小值这样的简单问题更难，但其实这两个问题的渐进运行时间同为$\Theta(n)$。本节介绍一种解决选择问题的分治算法 RANDOMIZED-SELECT 。类似于快速排序，对数组进行递归划分。但不同的是，快速 排序 递归处理划分的两边，而该算法只处理划分的一边，所以性能也有差异。实现要用到第七章介绍的快速排序中的 randomized_partition 函数，代码如下：

int randomized_select(int A[], int p, int r, int i)
{
    if (p == r) {
        return A[p];
    }
    
    q = randomized_partition(A, p, r);
    
    k = q - p + 1;  // 主元是第k大的数
    if (i == k) {
        return A[q];
    } else if (i < k) {
        return randomized_select(A, p, q-1, i);    // 在左边找
    } else {
        return randomized_select(A, q+1, r, i-k);  // 在右边找
    }
}

可以证明，上述算法的期望运行时间为$O(n)$，即，若所有元素是互异的，在期望线性时间内，可以找到任一顺序统计量，特别是中位数。

最坏情况为线性时间的选择算法

还有一个最坏情况下运行时间为$O(n)$的选择算法 SELECT ，也通过对数组的递归划分来找出所需元素。过程和代码从略。