目录
- 1.排序的作用
- 2.选择问题
2.1 最大值和最小值
2.2 期望为线性时间的选择算法
2.3 最坏情况为线性时间的选择算法（原因是选了一个好的主元，尽量居中的主元）
1.排序的作用
排序的意义在于排序后对有序序列的使用上。这种意义有两个：
1）方便将来的查找工作
2）告诉我们任何特定元素在一个团体里面的次序（排名）
2.选择问题
几个概念：
第i个顺序统计量：是该集合中第i小的元素
最小值：第一个顺序统计量(i = 1)
最大值：第n个顺序统计量
中位数：中点元素
选择问题：
根据排序的结果，可以在O(nlgn)时间内解决这个选择问题。
2.1 最大值和最小值
同时找最大值和最小值的方法：
分布独立地找，总共需要2(n-1)次比较
一种可以减小比较的方式（减少多余的比较）：
2.2 期望为线性时间的选择算法
分治算法：以快排为模型，将输入数组进行递归划分。但是该算法只处理划分的一边。（假设输入是互异的）
以下是RANDOMIZED-SELECT的伪代码，它返回数组A[p..r]中第i小的元素。
1）最坏情况运行时间
2）期望运行时间
1）这里的O(n)表示划分操作（RANDOMIZED-PARTITION）需要的时间。
2）T(max(k-1, n-k))表示包含较多元素的那一边，这种情况如果总是出现，就表示最差的情况，也即上界。
3）Xk和T(max(k-1, n-k))是独立的随机变量
其实这道题目的本质就是，通过随机选取之后，那个较多的那一边的数字大小排列仍然符合随机全排列
Xk选取后，并不影响k-1和n-k的任意排列，也即不影响其时间T(k-1)或者T(n-k)，因为k-1和n-k还是一个任意的排列
2.3 最坏情况为线性时间的选择算法（原因是选了一个好的主元，尽量居中的主元）
SELECT使用的是来自快排的确定性划分算法PARTITION，但做了修改，把划分的主元也作为输入参数。
特别注意：第二步、第三步只是递归地寻找中位数，其中对每个小组进行了插入排序
伪代码：
SELECT(A, p, r, i)
if p == r
return A[p]
m = FIND-MEDIAN(A, p, r) // m代表中位数
q = M-PARTITION(A, p, r, m)
k = q - p + 1
if i == k
return A[q]
else if i < k
return SELECT(A, p, q-1, i)
else return SELECT(A, q+1, r, i-k)
M-PARTITION(A, p, r, m)
exchange A[m] with A[r]
return PARTITION(A, p ,r)
FIND-MEDIAN(A, p, r)
divide to ceil(n/5) groups
use insertion sorting to get each median of gropus to new array B
if ceil(n/t) == 1
return B[0]
else
SELECT(B, 0, ceil(n/5) - 1, (h-1)/2)
最坏时间分析：
