算法导论 第九章：中位数和顺序统计学 笔记（最大值和最小值、以期望线性时间做选择、最坏情况线性时间的选择）
本章主要讲的内容是如何在线性时间内O(n)时间内在集合S中选择第i小的元素，最基本的是选择集合的最大值和最小值。一般情况下选择的元素是随机的，最大值和最小值是特殊情况，书中重点介绍了如何采用分治算法来实现选择第i小的元素，并借助中位数进行优化处理，保证最坏保证运行时间是线性的O(n)。
顺序统计量：
在一个由n个元素组成的集合中，第i个顺序统计量是值该集合中第i小的元素。例如最小值是第1个顺序统计量，最大值是第n个顺序统计量。
中位数：
一般来说，中位数是指它所在集合的“中间元素”，当n为奇数时，中位数是唯一的，出现位置为n/2；当n为偶数时候，存在两个中位数，位置分别为n/2（上中位数）和n/2+1（下中位数）。
选择问题描述：
输入：一个包含n个（不同的）数的集合A和一个数i，1≤i≤n。
输出：元素x∈A，它恰大于A中其他的i-1个元素。
最直接的办法就是采用一种排序算法先对集合A进行排序，然后输出第i个元素即可。可以采用前面讲到的归并排序、堆排序和快速排序，运行时间为O(nlgn)。接下来书中由浅入深的讲如何在线性时间内解决这个问题。
最大值和最小值：
在一个有n个元素的集合中，要做多少次比较才能确定其最小元素呢？依次查看集合中的每个元素，并记录比较过程中的最小元素。在下面的过程中，假设集合存放于数组A中，且length[A] = n 。
伪代码：
MINIMUM(A)
min <- A[1]
for i <- 1 to length[A]
do if min > A[i]
then min <- A[i]
return min同样地，最大值也可以通过n-1次比较找出来。
如：
求集合A={32,12,23,67,45,78}的最大值。
同时找出集合的最大值和最小值：
我们可以分别独立的找出集合的最大值和最小值，各用n-1次比较，共有2n-2次比较。
我们还可以用另一种方法：
在两两比较过程中同时记录最大值和最小值，这样最大需要3n/2次比较。现在的做法不是将每一个输入元素与当前的最大值和最小值进行比较，而是成对的处理元素，先将一对输入元素进行比较，然后把较大者与当前最大值比较，较小者与当前最小者比较，因此每两个元素需要3次比较。初始设置最大值和最小值方法：如果n为奇数，就将最大值和最小值都设置为第一个元素的值，然后成对的处理后续的元素。如果n为偶数，那么先比较前面两个元素的值，较大的设置为最大值，较小的设置为最小值，然后成对处理后续的元素。这样做的目的保证能够成对的处理后续的元素。
如：
找出集合A={32,23,12,67,45,78,10,39,9,58}最大值和最小值。
以期望线性时间做选择：
这是一种分治算法：以快速排序为模型：随机选取一个主元，把数组划分为两部分，A[p...q-1]的元素比A[q]小，A[q+1...r]的元素比A[q]大。与快速排序不同，如果i=q，则A[q]就是要找的第i小的元素，返回这个值；如果i < q，则说明第i小的元素在A[p...q-1]里；如果i >q，则说明第i小的元素在A[q+1...r]里；然后在上面得到的高区间或者低区间里进行递归求取，直到找到第i小的元素。
伪代码：
RANOOMIZED-SELECT(A, p, r, i)
if p= r
then return A[p]
q <- RANOOMIZED-PARTITION(A, p, r)
k <- q-p+1
if i= k //the pivot value is the answer
then return A[q]
else if i<k
then retorn RANOOMIZED-SELECT(A, p, q-1, i)
else return RANOOMIZED-SELECT(A,q+1,r,i-k)在算法第3行的RANOOMIZED-PARTITION 执行之后，数组A[p.. r] 被划分成两个（可能是空的）子数组A[p.. q-1]和A[q+1...r], 使得A[p...q-1] 中的每个元素都小于或等于A[q],进而小于A[q+1...r] 中的每个元素。与快速排序中一样，称A [q]为主元元素(pivot element) 。
RANDOMIZED-SELECT 的第4行计算子数组A[p.. q] 内的元素个数k, 即处于划分低区的元素的个数加上一个主元元素。然后，第5 行检查A[q]是不是第i小的元素。如果是，就返回A[q]。否则，算法要确定第i小的元素落在两个子数组A[p.. q-1] 和A[q+1..r] 中的哪一个之中。如果i<k, 则要找的元素落在划分的低区中，于是，第8行就在低区的子数组中进一步递归选择。如果i>k, 则要找的元素落在划分的高区子数组中。因为我们已经知道了有k个值（即A[p.. q]中的所有元素）小于A[p.. r] 中的第i小元素，故所求元素必是A[q+1...r] 中的第(i-k) 小元素，它在第9行中被递归地选取。
在最坏情况下，数组被划分为n-1和0两部分，而第i个元素总是落在n-1的那部分里，运行时间为Ө(n^2)；但是，除了上述很小的概率情况，其他情况都能达到线性；在平均情况下，任何顺序统计量都可以在线性时间Θ(n)内得到。
最坏情况线性时间的选择：
相比于上面的随机选择，我们有另一种类似的算法，它在最坏情况下也能达到O(n)。它也是基于数组的划分操作，而且利用特殊的手段保证每次划分两边的子数组都比较平衡；与上面算法不同之处是：本算法不是随机选择主元，而是采取一种特殊的方法选择“中位数”，这样能使子数组比较平衡，避免了上述的最坏情况（Ө(n^2)）。选出主元后，后面的处理和上述算法一致。
如图所示：
算法步骤：
将输入数组的n个元素划分为n/5组，每组（上图中的每列为一组）5个元素，且至多只有一个组有剩下的n%5个元素组成；
首先对每组中的元素（5个）进行插入排序，然后从排序后的序列中选择出中位数（图中黄色数）；
对第2步中找出的n/5个中位数，递归调用SELECT以找出其中位数x（图中红色数）（如果有偶数个中位数取较小的中位数）；
调用PARTITION过程，按照中位数x对输入数组进行划分。确定中位数x的位置k；
如果i=k，则返回x。否则，如果i<k，则在地区间递归调用SELECT以找出第i小的元素，若干i>k，则在高区找第(i-k)个最小元素。