说明：该系列博客整理自《算法导论(原书第二版)》，但更偏重于实用，所以晦涩偏理论的内容未整理，请见谅。另外本人能力有限，如有问题，恳请指正！
在一个由n个元素组成的集合中，第i个顺序统计量是该集合中第i小的元素。例如，在一组元素所组成的集合中， 最小值 是第 1 个顺序统计量（ i = 1 ）， 最大值 是第 n 个顺序统计量（ i = n）。而 中位数 （median）是它所在集合的“中点元素”。当n为奇数时，中位数是唯一的，出现在i = (n+1)/2处。当n为偶数时存在两个中位数，分别出现在i = n/2和i = n/2+1处，因此，不考虑奇偶性，中位数总是出现在(n+1)/2向下取整(下中位数)和(n+1)/2向上取整处(上中位数)。
从一个由 n 个数值构成的集合(下面的讲解假设集合中的数互异，但实际上所有处理都可以推广到集合中包含重复数值的情况)中选择其第 i 个顺序统计量的问题，可以形式化地定义为 选择问题 （selection problem）：
输入： 一个包含 n 个（不同的）数的集合 A 和一个数 i ，1 <= i <= n 。
输出： 元素 x ∈ A ，它恰好大于 A 中其他的 i - 1个元素。
1、最大值和最小值==特殊选择问题
在一个有n个元素的集合中，要做多少次比较才能确定其最小元素呢？可以很容易的给出n-1次比较这个上界：依次查看集合中的每个元素，并记录比较过程中的最小元素。这是最小值算法最好的结果。
MINIMUM(A)
1 min = A[1]
2 for i = 2 to A.length
3 if min > A[i]
4 min = A[i]
5 return min
最大值算法同理最小值算法。
MAXIMUM(A)
1 max = A[1]
2 for i = 2 to A.length
3 if max < A[i]
4 max = A[i]
5 reutrn max
要设计出一个算法，使之通过渐近最优的Θ(n)次比较，就能从n个元素中找出最小值和最大值，做到这一点并不困难，只要独立的找出最大值和最小值，各用n-1次比较，共有2n-2次比较。
事实上，至多 3⌊n/2⌋次比较就足以同时找到最大值和最小值。做法是记录比较过程中遇到的最大值和最小值。我们并不是将每一个输入元素与当前的最大值和最小值进行比较，而是成对的处理元素。先将一对输入元素互相比较，然后将较小者和当前最小值比较，较大者和当前最大值比较，因此每两个元素需要三次比较。
如何设定当前最小值和最大值的初始值依赖于n是奇数还是偶数。如果n是奇数，就将最小值和最大值都设为第一个元素的值，然后成对的处理余下的元素。如果n是偶数，就对前两个元素做一次比较，以决定最小值和最大值的初值，然后成对的处理余下的元素。
2、一般选择问题
一般选择问题，即返回数组A[p..r]中第i小的元素，看起来要比找最小值的简单选择问题更难，但两种问题的渐近运行时间却是相同的：都是 Θ ( n )。这里介绍一种解决选择问题的分治算法，即 RANDOMIZED-SELECT 算法。该算法以之前第7章介绍的快速排序算法为基础。如同在排序算法中一样，此算法的思想也是对输入数组进行递归划分，但和快速排序不同的是，快速排序会递归处理划分的两边，而RANDOMIZED-SELECT 算法只处理划分的一边。
RANDOMIZED-SELECT 算法利用了快速排序算法的RANDOMIZED-PARTITION程序，所以RANDOMIZED-SELECT 算法也是一个随机算法。
RANDOMIZED-SELECT(A, p, r, i)
1 if p == r
2 return A[p]
3 q = RANDOMIZED-PARTITION(A, p, r)
4 k = q - p + 1//计算数组A[p..q]内元素的个数k，即处于划分低区的元素的个数加上一个主元元素
5 if i == k // the pivot value is the answer
6 return A[k]
7 elseif i < k
8 return RANDOMIZED-SELECT(A, p, q - 1, i)
9 else
10 return RANDOMIZED-SELECT(A, q + 1, r, i - k)
该随机选择算法的最坏情况运行时间为 Θ ( n2 )，但是由于采用了RANDOMIZED-PARTITION程序，所以非常小概率会出现最坏情况。
网友评论