第i个顺序统计量:在一个由n个元素组成的集合中，第i个顺序统计量(order statistic)是该集合中第i小的元素。
最小值是第1个顺序统计量(i=1)
最大值是第n个顺序统计量(i=n)
中位数：一个中位数(median)是它所在集合的“中点元素”，当n为奇数时，i=(n+1)/2，当n为偶数是，中位数总是出现在 （下中位数）和 （上中位数）。
找最大值/最小值问题，通过比较n-1次可以得出结果。
MINIMUM(A) 1 min ← A[1] 2 for i ← 2 to length[A] 3 do if min > A[i] 4 then min ← A[i] 5 return min如果要同时找出最大值和最小值，则比较次数最少并不是2*n-2，而是 ，我们可以将一对元素比较，然后把较大者于max比较，较小者与min比较，这样就只需要 。
如果是一般的选择问题，即找出一段序列第i小的数，看起来要比找最大值或最小值要麻烦，其实两种问题的渐进时间都是 。
首先看看这个强悍的伪代码：
RANDOMIZED-SELECT(A, p, r, i) 1 if p = r 2 then return A[p] 3 q ← RANDOMIZED-PARTITION(A, p, r) 4 k ← q - p + 1 5 if i = k ▹ the pivot value is the answer 6 then return A[q] 7 elseif i < k 8 then return RANDOMIZED-SELECT(A, p, q - 1, i) 9 else return RANDOMIZED-SELECT(A, q + 1, r, i - k)这个算法利用了随机化的Partition算法，这个实在第七章的随机化快排中讲到：http://www.wutianqi.com/?p=2368，不记得的可以先复习下前面的快排。
这个随机化的选择算法返回数组A[p..r]中第i小的元素。
具体实现如下：
template <class T>int randomPartition(T a[], int beg, int end){//随机选取与end交换 int randIndex = beg + rand() % (end - beg + 1); swap(a[randIndex], a[end]);//将end作为基准元素 T posElem = a[end];int pos = beg - 1;//从beg扫描到end-1 for (int i = beg; i < end; i++) {//将小于等于的元素交换到前面 if (a[i] <= posElem && pos != i) { pos++; swap(a[i], a[pos]); } }//交换基准元素到分割点 swap(a[pos + 1], a[end]);return pos + 1;}//随机选取递归版本template <class T>T randomSelect(T a[], int p, int r, int i){if (p == r)return a[p];//随机划分 int q = randomPartition(a, p, r);//划分后的左子序列个数 int k = q - p + 1;//刚好划分到q==i为第i个最小数 if (i == k) {return a[q]; }//继续搜索左子序列 else if (i < k) {return randomSelect(a, p, q - 1, i); }//继续搜索右子序列 elsereturn randomSelect(a, q + 1, r, i - k);}//随机选取迭代版本template <class T>T randomSelectUnrecursive(T a[], int p, int r, int i){int q = 0, k = 0;while (p != r) { q = randomPartition(a, p, r); k = q - p + 1;if (i == k) {return a[q]; }//与递归不同的是将搜索区间改变后循环即可 else if (i < k) { r = q - 1; }else { p = q + 1; i = i - k; } }return a[p];}转自：http://www.cppblog.com/tanky-woo/archive/2011/04/26/145044.html
转载于:https://www.cnblogs.com/yysblog/archive/2011/12/06/2278089.html
