1：n个元素组成的集合，第i个顺序统计量，就是该集合中第i小的元素。所以，集合中的最小值就是第1个顺序统计量，最大值就是第n个顺序统计量。中位数是所属集合的中点元素，当n是奇数的时候，中位数唯一，位于(n+1)/2处。如果n是偶数，中位数有两个，分别位于n/2和(n/2) + 1。
2：选择问题，就是选择第i个顺序统计量的问题。如果利用排序的话，那最快可以在O(n lgn)时间内解决，但其实有更快的算法。
3：为了找到n个元素中的最小值或者最大值，最少需要n-1次比较：
MINIMUM(A)
min = A[1]
for i = 2 to A.len
if min > A[i]
min = A[i]
return min
4：对于需要同时找到最大值和最小值的问题，如果是独立找出最大值和最小值的话，需要2n-2次比较，实际上，采用某种方法可以实现比较次数最多到3（n/2）次。该方法是：记录已知的最大值和最小值，对输入的元素成对的进行处理，首先将2个输入元素相互比较，然后把较小的元素与最小值比较，较大的元素与最大值比较，这样，每两个元素共需比较3次。如果n是奇数，把最大值和最小值的初值都设置为第一个元素的值，所以，比较次数为3((n-1)/2)。如果n是偶数，把前两个元素作比较，确定最初的最大值和最小值，所以，比较次数为3((n-1)/2)。所以，不管哪一种情况，总的比较次数最多为3(n/2)。
如果要找第二小的元素，证明最坏情况下需要n + lg n – 2次比较。
证明：采用这样的方法找最小元素：将n个元素成对比较，找到n/2个小元素，然后对着n/2个元素再次成对比较，知道最后一个元素，也就是最小元素。
在该算法中，可以从底向上画出一棵完全二叉树，数有n个叶子结点，有n-1个内部结点，每个内部结点代表了一次比较，所以在寻找最小元素的过程中，需要n-1次比较。
为了找到第二小的元素，因该元素肯定是在与最小元素的比较过程中被淘汰掉了，所以为了寻找该元素，可以在该完全二叉树中，找到包含最小元素的分支，该分支一共有lg n个结点，在这lgn个结点中在找最小节点就好了，也是需要lg n – 1次比较。所以一共需要n + lg n – 2次比较。
5：对于一般的选择问题，可以采用类似于快速排序的方法，可以使运行时间达到Θ(n)。该算法称为RANDOMIZED-SELECT算法。该算法也是随机算法，因为其中调用了RANDOMIZED-PARTITION。算法伪代码如下：
RANDOMIZED-SELECT(A, p, r, i)
if(p == r)
return A
q = RANDOMIZED-PARTITION(A, p, r)
k = q – p + 1
if(k == i)
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)。
int randompartition(int *set, int begin, int end)
{
int i, j, k;
int x;
int ran;
srand((int)time(NULL));
ran = randomab(begin, end);
exchange(set+ran, set+end);
x = set[end];
i = begin - 1;
for(j = begin; j <= end - 1; j++)
{
if(set[j] <= x)
{
i++;
exchange(set+i, set+j);
}
}
exchange(set+i+1, set+end);
return i+1;
}
int partitionselect(int *set, int begin, int end, int index)
{
int q;
int k;
if(index <= 0="" index=""> (end-begin+1))
{
printf("error index: %d", index);
return -1;
}
if(begin == end)
{
return set[begin];
}
q = randompartition(set, begin, end);
k = q - begin + 1;
if(index == k)
{
return set[q];
}
else if(index < k)
{
partitionselect(set, begin, q-1, index);
}
else
{
partitionselect(set, q+1, end, index-k);
}
}
6：SELECT算法可以在最坏情况运行时间为O(n)来解决选择问题，该算法步骤如下： a、将输入数组的n个元素划分为n/5组，每组5个元素，且至多有一个组由剩下的nmod 5个元素组成。 b、寻找n/5个组中每一组的中位数。（方法首先对每组中的元素进行插入排序，然后从排序过的序列中选出中位数） c、对第2步中找出的n/5个中位数，递归调用SELECT找出其中位数x。（如果有偶数个中位数，根据约定，x是下中位数。） d、 利用修改过的PARTITION过程，按中位数的中位数x对输入数组进行划分。让k比划分低区的元素多1，所以x是第k小的元素，并且有n-k个元素在划分的高区。 e、如果i=k，则返回x，否则，如果ik，则在高区找第（i-k）个最小元素。
图中箭头指向表示大的数值指向小的数值，所以根据图可以看出，在x的右边，每一个包含5个元素的组中至少有3个元素大于x，x的左边，每一组中至少有3个元素小于x。（保证x分割一边必定有元素存在） 图中显示的中位数的中位数x的位置，每次选取x作为划分的好处是能够保证必定有一部分在x的一边。 所以算法最坏情况的递归公式可以写成：
使用替换法可以得出T（n）<=cn。
注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。
