《算法导论》第9章：中位数与顺序统计量 (Medians and Order Statistics)

这一章主要研究这几个问题：

• 怎么求最大/最小
• 怎么同时求最大&最小
• 怎么求第二大/小（习题9.1-1）
• 怎么求第k小

这些问题的算法并不难，本质上我们是想探讨它们所需要的最小比较次数，所以希望大家把重点放在理解证明过程上，学习证明思路，理解排序的本质。下文中，数据规模都用 $n$ 表示。

求最大/最小

至少需要比较 $n-1$ 次才能保证求出。

证明：最开始一共有 $n$ 个潜在的最大/最小候选，每次比较都能且只能淘汰1个候选。

同时求最大&最小

至少需要比较 $\lfloor{3n/2}\rfloor-2$ 次才能保证求出。

证明：

最开始潜在的最大、最小候选各有 $n$ 个，所以一共需要排除 $2n-2$ 个候选。

每次进行比较时，如果双方同时是最大或最小的候选，就能保证排除1个对应的候选。例如，若A、B都是最大候选，则比较后必然有一个不再是最大候选；但如果B不是最大候选，那么在A大于B的情况下无法排除任何候选。这样的策略一定可以实施，因为在选出最大/最小值前，对应的候选者必然多于1个。

我们尽量让未比较过比较的数碰在一起，这样可以一次排除2个候选。若 $n$ 为奇数，那么最后会剩下一个未参与过比较的数，那么让它再和任意一个数比较一次就行了。这一步骤需要 $\lceil{n/2}\rceil$ 次比较，排除了 $n$ 个候选。

剩下 $n-2$ 个候选继续用之前的策略进行排除，每次比较排除一个，共 $n-2$ 次比较。

所以最少需要比较$\lceil{n/2}\rceil+n-2=\lfloor{3n/2}\rfloor-2$ 次。

求第二大/小

可以保证通过 $n+\lceil{\lg{n}}\rceil-2$ 次比较求出。

方法：两两淘汰至冠军，然后从冠军击败的候选中选出最大/小值，即为亚军的值。

正确性：亚军不可能被冠军以外的其他候选击败。

比较次数：决出冠军需要 $n-1$ 次比较，期间冠军经历了 $\lceil{\lg{n}}\rceil$ 轮比赛，击败了同等数量的对手。它们之间决出冠军又需要 $\lceil{\lg{n}}\rceil-1$ 次比较，所以总共是 $n+\lceil{\lg{n}}\rceil-2$ 次比较。

求第k小

期望是线性时间的算法

RANDOMIZED-SELECT(A,l,r,i)从数组A[l..r]中选出第i小的数。

RANDOMIZED-SELECT(A,l,r,i)
  if l == r
    return A[l]
  q = RANDOMIZED-PARTITION(A,l,r)
  k = q-l+1
  if i == k
    return A[q]
  elseif i < k
    return RANDOMIZED-SELECT(A,l,q-1,i)
  else
    return RANDOMIZED-SELECT(A,q+1,r,i-k)

RANDOMIZED-PARTITION(A,l,r)随机从数组选择一个数，把小于它的移到它左边，大于它的移到它右边。如果左半边的元素个数大于等于i，那么第i小的数一定在左半边，否则在右半边。每深一层递归，搜索范围就小一点，所以最后一定可以找到。

最坏情况下，搜索范围每次只缩小1，因此成了 $\Theta(n^2)$ 时间的算法，但是书上证明了期望时间是 $O(n)$ 。

最坏情况下是线性时间的算法

本算法叫做SELECT，输入为长为 $n$ 的数组 $A$ 和正整数 $i$，输出 $A$ 中第 $i$ 小的元素。大家欣赏一下就好。

1. 将 $n$ 个元素分为 $\lfloor{n/5}\rfloor$ 组，每组 5 个，剩下的不超过五个的元素再成一组
2. 用常数时间求出每组的中位数，共 $\lceil{n/5}\rceil$ 个
3. 递归调用 SELECT 算法，求出上述中位数的中位数 $x$
4. 用 PARTITION 算法将其他元素排列在 $x$ 的左侧和右侧，设左侧有 $k$ 个元素
5. 若 $i=k$，则返回 $x$；若 $i<k$，则在 $x$ 左侧调用 SELECT 寻找第 $i$ 小的元素；若 $i>k$，则在 $x$ 右侧调用 SELECT 寻找第 $i-k$ 小的元素

这个算法为什么是线性时间的呢？看书本的9-3节吧。大概意思是说，每次递归执行第3步时，数据规模都是原来的20%，而每次递归执行第5步时数据规模都是原来的70%，相当于把上一节的 RANDOMIZED-PARTITION 变得更加稳定了，每次都能按一定比例排除候选。

好，牛！但我还是会选择 RANDOMIZED-PARTITION，正如我选择随机版 quicksort 一样。