在一个由n个元素组成的集合中，第i个顺序统计量是该集合中第i小的元素。例如，在一个元素集合中，最小值是第1个顺序统计量(i=1),最大值是第n个顺序统计量。
假设集合中的元素都是互异的，但可以推广到集合中包含重复元素的情形。
输入：一个包含n个（互异的）数的集合A和一个整数i，1≤i≤n。
输出：数组中的元素x，且A中恰好有i-1个元素小于它。
可以在O(nlgn)时间内解决这个选择问题，因为可以用堆排序或归并排序对输入数据进行排序，然后在输出数组中根据下标找到第i个元素即可。
最大值和最小值
MINIMUM(A)
min = A[1]
for i = 2 to A.length
if min > A[i]
min = A[i]
return min
为了确定最小值，必须要做n-1次比较。因此，从所执行的比较次数来看，算法MINIMUM是最优的。
同时找到最小值和最大值 可以分别独立地找出最大值和最小值，这各需要n-1次比较，共需2n-2次比较。事实上，只需要最多次比较就可以同时找到最小值和最大值。具体的方法是记录已知的最小值和最大值。但我们并不是将每一个元素与当前的最大值和最小值进行比较-这样做的代价是每个元素需要2次比较，而是对输入元素成对地进行处理。首先，我们将一对输入元素相互进行比较，然后把较小的与当前最小值比较，把较大的与当前最大值进行比较。这样，对每对元素共需3次比较。
如果n为奇数，我们将最大值和最小值的初值都设为第一个元素的值，然后成对地处理剩下的元素。如果n是偶数，就对前两个元素进行一次比较，以决定最大值和最小值的初值，然后成对地处理余下的元素。
期望时间为线性时间的选择算法
一般选择问题看起来要比找最小值这样的简单问题更难。但令人惊奇的是，这两个问题的渐近运行时间却是相同的:Θ(n)。
以快速排序算法为模型，将输入数组进行递归划分。但与快速排序不同的是，快速排序会递归处理划分的两边，而RANDOMIZED-SELECT只处理划分的一边。RANDOMIZED-SELECT的期望运行时间为Θ(n)。这里，假设输入数据都是互异的。
RANDOMIZED-SELECT(A, p, r, i)
if p == r
return A[p]
q = RANDOMIZED-PARTITION(A, p, r)
k = q - p + 1
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)
最坏情形运行时间为Θ(n2)。
期望运行时间为O(n)，假设元素是互异的。
最坏情形为线性时间的选择算法
- 将输入数组的n个元素划分为
组，每组5个元素，且至多只有一组由剩下的n mod 5个元素组成。
- 寻找这
- 对第2步中找出的
- 利用修改过的PARTITION版本，按中位数的中位数x对输入数组进行划分。让k比划分的低区中的元素数目多1，因此x是第k小的元素，并且有n-k个元素在划分的高区。
- 如果i=k，则返回x。如果i<k，则在低区递归调用SELECT来找出第i小的元素。如果i>k,则在高区递归查找第i-k小的元素。
