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)

最坏时间分析：

排序相关1——次序选择（顺序统计量）