在一个由n个元素组成的集合中，第i个顺序统计量（order statistic）是该集合中第i小的元素。用非形式化的描述来说，一个中位数（median）使它所属集合的“中点元素”。当n为奇数时，中位数是唯一的，位于i=(n+1)/2处。当n为偶数时，存在两个中位数，分别位于i=n/2和i=n/2+1处。因此不考虑n的奇偶性，中位数总是出现在i=floor((n+1)/2)处（下中位数）与i=ceil((n+1)/2)处（上中位数）。
本章将讨论一个由n个互异的元素构成的集合中选择第i个顺序统计量的问题。将这一问题形式化定义为如下的选择问题：
输入：一个包含n个（互异）数的集合A和一个整数：1<=i<=n。
输出：元素x属于A，且A中恰有i-1个其他元素小于它。

1. 最大值和最小值
在一个有n个元素的集合中，通过n-1次比较可找到其中的最小值。代码如下：

1 int Minimum(int A[], int n) {2     int min = A[1];3     int i;4 5     for (i=2; i<=n; ++i)6         if (min > A[i])7             min = A[i];8     return min;9 }

采用同样的方式，可通过2n-2次比较同时找到最大值和最小值。而事实上，仅需3*floor(n/2)次比较就可以找到最小值和最大值。即先成对比较后，用两者的较小值与最小值比较，用两者的较大值与最大值比较。这样，每对元素共需三次比较。
而对于最小值与最大值的初始值依赖于n是奇数还是偶数。若n是奇数，将最大值和最小值都设为第一个元素的值，然后成对的处理余下元素；若n为偶数，先对首对元素比较，两者的较小值作为最小值的初始值，两者的较大值作为最大值的初始值。
若n为奇数，进行3*floor(n/2)次比较；若n为偶数，进行3n/2-2次比较。总的比较次数至多为3*floor(n/2)。代码实现如下：

 1 static int min, max; 2 void MinAndMax(int A[], int n) { 3     int lt, gt; 4     int i; 5  6     if (n & 1) { 7         min = A[1]; 8         max = A[1]; 9         i = 2;10     } else {11         min = A[1]<A[2] ? A[1]:A[2];12         max = A[1]+A[2]-min;13         i = 3;14     }15 16     for (; i<=n; i+=2) {17         if (A[i] < A[i+1]) {18             lt = A[i];19             gt = A[i+1];20         } else {21             lt = A[i+1];22             gt = A[i];23         }24         if (min > lt) min = lt;25         if (max < gt) max = gt;26     }27 }

9.1-1 证明：在最坏情况下，找到n个元素中第二小的元素需要n+ceil(lgn)-2次比较。
证明：首先考虑找最小元素。采用两两成对比较，对筛选得到的最小值再成对比较，直到比较出唯一的最小值。如下图所示

因为1是最小值，所以第二小元素一定是那些作为根结点的最小值的叶子结点之一（另外一个叶子一定为它本身）。经过n-1次比较可以找到最小值，而又因为二叉树的叶子为元素n，则2^h<=n，故h<=ceil(lgn)，因为找到最小值后，需要针对最小值经过的结点的叶子结点进行比较得到第二小元素。因此，后续的比较次数为h-1，故总的比较次数为
T(n) = n-1+h-1 = n+h-2 = n+ceil(lgn)-2。

9.1-2 证明：在最坏情况下，同时找到n个元素中最大值和最小值的比较次数的下界时ceil(3n/2)-2。
证明：采用成对比较的方法，需要经过floor(n/2)次比较可以得到每一对儿元素的关系，每对元素中的较大值可能为最大值，每对元素中的较小值可能成为最小值。考虑奇偶性，可知经过预比较外，存在ceil(n/2)个元素可能成为最大值，存在ceil(n/2)个元素可能成为最小值。因此作为最大值最小值的候选元素，可通过ceil(n/2)-1次比较得到最大值或最小值。因此最坏情况下，总的比较次数T(n) >= floor(n/2) + ceil(n/2)-1 + ceil(n/2)-1。
所以T(n) >= (floor(n/2) + ceil(n/2) )+ ceil(n/2)-2，而n = floor(n/2) + ceil(n/2)，所以
T(n) >= n + ceil(n/2) - 2，因为n为整数，故n + ceil(n/2) = ceil(n+n/2) = ceil(3n/2)，所以
T(n) >= ceil(3n/2) - 2，所以下界为ceil(3n/2) - 2。

2. 期望为线性时间的选择算法
解决一般选择问题的RANDOMIZED-SELECT算法以快速排序为模型。不同点是，快速排序会递归处理划分的两遍，而RANDOMIZED-SELECT仅会递归处理划分的一边。这一差异在性能分析中体现出来，快速排序的期望运行时间为theta(nlgn)，而RANDOMIZED-SELECT的期望运行时间为theta(n)。
RANDOMIZED-SELECT算法返回数组A[p..r]中的第i小元素。代码实现如下：

 1 int Randomized_Select(int A[], int p, int r, int i) { 2     int q, k; 3  4     if (p == r) 5         return A[p]; 6     q = Randomized_Partition(A, p, r); 7     k = q-p+1; 8     if (i == k) 9         return A[q];10     else if (i < k)11         return Randomized_Select(A, p, q-1, i);12     else13         return Randomized_Select(A, q+1, r, i-k);14 }

9.2-1 证明：在RANDOMIZED-SELECT中，对长度为0的数组，不会进行递归调用。
证明：说实话，貌似真心可能会递归调用，取决于i。

9.2-3 给出RANDOMIZED-SELECT的一个基于循环的版本。
代码如下：

 1 int Randomized_Select(int A[], int p, int r, int i) { 2     int q, k; 3  4     if (p == r) 5         return A[p]; 6     do { 7         q = Randomized_Partition(A, p, r); 8         k = q - p + 1; 9         if (i == k)10             return A[q];11         else if (i < k) {12             r = q - 1;13         } else {14             p = q + 1;15             i -= k;16         }17     } while (1);18 }

3. 最坏情况为线性时间的选择算法
SELECT算法是最坏情况运行时间为O(n)的选择算法，如同RANDOMIZED-SELECT算法一样，SELECT算法通过对输入数组的递归划分来找出所需元素。SELECT算法使用的也是来自快速排序的确定性划分PARTITION，但做了修改，把划分的主元也作为输入参数（以下成为PARTITIONX）。
通过执行下列步骤，算法SELECT可以确定一个有n>1个不同元素的输入数组中第i小的元素。（若n=1，则SELECT只返回它的唯一输入数值作为第i小的元素。）步骤如下：
（1）将输入数组的n个元素划分为floor(n/5)组，每组5个元素，且至多只有一组由剩下的n%5个元素组成；
（2）寻找这ceil(n/5)组中每一组的中位数，首先对每组元素进行插入排序，然后确定每组有序元素的中位数；
（3）对第2步中找出的ceil(n/5)个中位数，递归调用SELECT以找出其中位数x（如果有偶数个中位数，约定x是较小的中位数）；
（4）利用PARTIONX，按中位数的中位数x对输入数组进行划分。让k比划分的低区中的元素多1，因此x是第k小的元素，并且有n-k个元素在高区。
（5）如果i=k，则返回x。如果i<k，则在低区递归调用SELECT来找出第i小的元素；如果i>k，则在高区递归调用SELECT找出第i-k小的元素。
代码实现如下：

 1 int Select(int A[], int p, int r, int i) { 2     int M[MAXN/5+2], m = 0; // M[]: store median, m: number of medians 3     int x, k, q;            // x: median of M[] 4     int j, n = 5; 5  6     if (p == r) 7         return A[p]; 8  9     for (j=p; j<=r; j+=5) {10         if (j+4 > r) {11             n = r-j+1;12         }13         InsertionSort(A+j-1, n);    // Sort14         M[++m] = A[j+(n-1)/2];      // then Add the median into M15     }16     x = Select(M, 1, m, (m+1)/2);17     q = PartitionX(A, p, r, x);18     k = q - p + 1;19     if (i == k)20         return x;21     else if (i < k)22         return Select(A, p, q-1, i);23     else24         return Select(A, q+1, r, i-k);25 }

算法难以理解的地方是借用中位数的中位数，如下图

在第（2）步找出的中位数中，至少有一半大于或等于中位数x。因此在这ceil(n/5)个子数组中，除了n不能被5整除产生的少于5个元素的组与中位数的中位数x所在组外，至少一半的组中有3个元素大于x，相反，至少有一半的组中有3个元素小于x。除上述两组外，大于x的元素个数至少为：
3*(ceil(1/2 * ceil(n/5)) - 2) >= 3n/10 - 6
同样，至少有3n/10-6个元素小于x。因此，在最坏情况下，SELECT的递归调用最多作用于7n/10+6个元素。
故T(n) <= T(ceil(n/5)) + T(7n/10+6) + O(n)，可解得T(n) <= cn + (-cn/10+7c+an)
若-cn/10+7c+an <= 0时，T(n) <= cn，解此不等式：
当n>70时，c >= 10a(n/(n-70))，满足T(n) <= cn，T(n) = O(n)。
书中选择140代替边界70，则SELECT过程的时间复杂度满足
当n<140时，T(n) <= O(1)；当n>=140时，T(n) <= T(ceil(n/5)) + T(7n/10+6) + O(n)。
因此，最坏情况下时间复杂度为O(n)。

9.3-1
证明: (1)每组7个元素，则4*(ceil(1/2 * ceil(n/7)) - 2) >= 2n/7-8，则至少有2n/7-8个元素大于x，同理，至少有
2n/7-8个元素小于x，则最坏情况下，SELECT递归调用最多作用于n-(2n/7-8)=5n/7+8个元素。因此，
T(n) <= T(ceil(n/7)) + T(5n/7+8) + O(n)，当不等式-cn/7+9c+an<=0时，满足T(n)<=cn，此时n>=63，
则当n<63时，T(n)<=O(1)；当n>=63时，T(n) <= cn。因此，T(n) = O(n)。

9.3-2
证明：大于x的元素个数为3*(ceil(1/2 * ceil(n/5)) - 2) >= 3n/10 - 6，即证明3n/10-6 >= ceil(n/4)，
因为ceil(n/4) < n/4+1，转为证明当n>=140时，3n/10-6 >= n/4+1，令f(n) = (3n/10-6) - (n/4+1)，
f(n) = n/20-7，当n>=140时，f(n) >= 0，则3n/10-6 >= n/4+1，因此得证。

9.3-3
解：核心思想是，每次先通过Select找到中位数x，然后通过PARTITIONX对数组进行划分。因为PARTITIONX与Select都是O(n)，并且划分后x位于数组中间，因此每次划分都会平衡，可保证快速排序的运行时间为O(nlgn)。
代码实现如下：

 1 void QuickSort(int A[], int p, int r) { 2     int x, q; 3  4     if (p < r) { 5         x = Select(A, p, r, (r-p+2)/2); 6         q = PartitionX(A, p, r, x); 7         QuickSort(A, p, q-1); 8         QuickSort(A, q+1, r); 9     }10 }

9.3-4
证明：假设x是第i小元素，那么在有序排列中，第i-1小元素一定在x前一个，
同时，有n-i个元素大于x，那么第n-i大元素一定在x的后一个，则第i元素处在第i-1小元素与第n-i元素之间，
采用比较确定第i小的元素，一定通过第i小元素的前者第i-1小元素及它的后者第n-i大元素比较后才会确定，
因此，不需要额外的比较即可确定。

9.3-5
解：
Select(A, p, r, i):
　　if (p == r)
　　　　return A[p];
　　x = GetMedian(A, p, r);
　　q = PartitonX(A, p, r, x);
　　k = q - p + 1;
　　if (i == k)
　　　　return x;
　　else if (i < k)
　　　　return Select(A, p, q-1, i);
　　else
　　　　return Select(A, q+1, r, i-k);
上述过程时间复杂度为T(n) = T(n/2) + O(n)，因此T(n) = O(n)。

9.3-6
解：
这道题目一定要搞清楚k分位是什么意思，可以理解成把元素分成k个子集（保证子集中元素个数相同）的那些分位点，共有k-1个分位点。算法的思想也是二分，每次都得到分位点的中位数x，然后对x左右两边的数组求解分位点。代码实现如下：

 1 void PartitionK(int A[], int p, int r , int k, int kn, int B[], int Bp) { 2     int x, q; 3  4     if (k == 0) 5         return ; 6  7     x = Select(A, p, r, (k+1)/2*kn); 8     B[Bp+(k+1)/2] = x; 9     q = (Bp+(k+1)/2) * kn;10     PartitionK(A, p, q, (k-1)/2, kn, B, Bp);11     PartitionK(A, q+1, r, k/2, kn, B, Bp+(k+1)/2);12 }13 14 void K_Partition(int A[], int n, int k, int B[]) {15     int kn;16 17     if (n%k != 0)18         return ;19     kn = n/k;20     PartitionK(A, 1, n, k-1, kn, B, 0);21 }

 9.3-7 设计一个O(n)时间的算法，对于一个给定的包含n个互异元素的集合S和一个正整数k<=n，该算法能确定S中最接近中位数的k个元素。
解：先通过Select从集合S中找到中位数x，同时引入辅助数组D，D的主元是S中各元素与x的差的绝对值，卫星数据是索引，从而通过Select找到D中的第k个元素，从而通过前k个元素的索引从D中获得最接近中位数x的k个元素。
从而T(n) = O(n)

9.3-8 设X[1..n]和Y[1..n]为两个数组，每个都包含有n个有序的元素。请设计一个O(lgn)时间的算法来找出数组X和Y中所有2n个元素的中位数。
解：思想还是二分，代码实现如下：

 1 int GetMedian(int X[], int Y[], int n) { 2     int mx, my; 3  4     if (n == 1) 5         return X[1]<Y[1] ? X[1]:Y[1]; 6     mx = Select(X, 1, n, (n+1)/2); 7     my = Select(Y, 1, n, (n+1)/2); 8     if (mx == my) 9         return mx;10     else if (mx < my)11         return GetMedian(X+n/2, Y, (n+1)/2);12     else13         return GetMedian(X, Y+n/2, (n+1)/2);14 }

9.3-9
解：这题目就是小学奥数，即通过X、Y的中位数确定最有位置。而中位数可以通过Select过程在O(n)内确定。

【算法导论】学习笔记——第9章 中位数和顺序统计量