9.1 最小值和最大值
同时求最小值和最大值，总的比较次数至多为3*[n/2]。只要成对处理数据即可。
9.2 期望为线性时间的选择算法
使用分治算法和快速算法用到的随机选择pivot。假设数据都不相同。
RANDONMIZED-SELECT(A, p, r, i) //从数组A的下标段p到r找第i大的数
q = RANDONMIZED-PARTITION(A, p, r) //选择排序通过pivot分段
k = q-p+1
RANDONMIZED-SELECT(A, p, q-1, i)
or RANDONMIZED-SELECT(A, q+1, r, i-k)
9.3 最坏情况为线性时间的选择算法
算法SELECT
1》将数组划分为每组5个元素的组
2》插入排序选择每组的中位数
3》用SELECT选择中位数的中位数
4》用其为pivot划分
5》递归调用SELECT
与比较排序一样，SELECT和RANDONMIZED-SELECT通过元素比较来确定相对次序。
见8.1(思考题8-1)，比较排序即使在平均情况下，也至少需要Ω(nlgn)时间。第八章的线性时间在输入上做了假设。
本章的线性选择算法不需要任何关于输入的假设。他们不受限于Ω(nlgn)的下界约束，因为没有排序。