我们如何找到一个由nn个互异的元素构成的集合中第ii大的元素？

输入：一个包含nn个互异的数的集合AA和一个整数ii，1≤i≤n1 \le i \le n

输出：元素x∈Ax\in A，且AA中恰好有i−1i-1个其他元素小于他

最小值和最大值

在一个有nn个元素的集合中，需要多少次比较才能确定其最小元素呢？很简单，上界是n−1n-1

1
2
3
4
5
6
MINIMUM(A)
min = A[1]
for i = 2 to A.length
	if min > A[i]
		min = A[i]
return min

同时找到最小值和最大值

显然，可以分别独立地找出最小值和最大值，各需要n−1n-1次比较，共需要2n−22n-2次

事实上，只需要最多3⌊n/2⌋3\lfloor n/2\rfloor次比较就可以同时找到最小值和最大值。我们采用的策略是将一对输入元素相互进行比较，然后把较小的与当前最小值比较，把较大的与当前最大值比较。这样，对每两个元素共需3次比较。如果有奇数个，就将最小值和最大值的初值都设为第一个元素的值，然后成对处理余下元素。如果是偶数个，就先对前两个元素比较一次设定最大值最小值的初始值。

期望为线性时间的选择算法

基于快速排序，但是每次只处理划分的一边。

这其实是学院21级数据结构与算法期末考试题的一道程序设计题==，当时的我一下子就想起算法导论里的这个方法。EE的数据结构考的还是简单。。。

1
2
3
4
5
6
7
8
9
10
RANDOMIZED-SELET(A, p, r, i)
if p == r
	return A[p]
q = RANDOMIZED-PARTITION(A, p, r) //抽取某个位置作为分界
k = q - p + 1
if i == k
	return A[q] //中奖了，就是他了，结束
else if i < k	//和快速排序不同的地方就在于左右只选一个
	return RANDOMIZED-SELECT(A, p, q-1, i) //从左半边选
else return RANDOMIZED-SELECT(A, q+1, r, i-k) //从右半边选

最坏情况下，每次划分都按余下元素中最大的进行划分，划分需要Θ(n)\Theta(n)的时间，由于递归的分法，差不多要调用nn次，因此共需要Θ(n2)\Theta(n^2)的时间

下面分析一下算法的期望运行时间，设该算法在一个含有nn个元素的输入数组A[p..r]A[p..r]上的运行时间是一个随机变量，记为T(n)T(n)。抽取位置的程序以等概率返回任何元素，因此每个元素作为主元的概率都为1/n1/n，这也意味着子数组的元素个数k取从1到n的值的概率都是1/n1/n

设

Xk=I{子数组正好包含k个元素}X_k=I\{子数组正好包含k个元素\}

进而

E[Xk]=1/nE[X_k]=1/n

假设第ii个元素总是在划分中包含较大元素的一边

T(n)≤∑k=1nXk⋅(T(max(k−1,n−k))+O(n))T(n)\le\sum_{k=1}^n X_k\cdot(T(max(k-1, n-k))+O(n))

对于任何选中的的kk，只有Xk=1X_k=1，因此求和式将退化成单项式，后面的线性时间表示随机抽取的时间

两边取期望值，

E[T(n)]≤E[∑k=1nXk⋅(T(max(k−1,n−k))+O(n))]=∑k=1nE[Xk⋅T(max(k−1,n−k))]+O(n)=∑k=1nE[Xk]⋅E[T(max(k−1,n−k))]+O(n)=∑k=1n1n⋅E[T(max(k−1,n−k))]+O(n)E[T(n)]\le E[\sum_{k=1}^n X_k\cdot(T(max(k-1, n-k))+O(n))] \\ =\sum_{k=1}^n E[X_k\cdot T(max(k-1, n-k))]+O(n)\\ =\sum_{k=1}^n E[X_k]\cdot E[T(max(k-1, n-k))]+O(n)\\ =\sum_{k=1}^n \frac{1}{n}\cdot E[T(max(k-1, n-k))]+O(n)

下面问题在于

max(k−1,n−k)={k−1  若k>⌈n/2⌉n−k  若k≤⌈n/2⌉max(k-1,n-k)=\begin{cases} k-1\ \ 若k>\lceil n/2\rceil\\ n-k\ \ 若k\le\lceil n/2\rceil \end{cases}

若n是偶数，则从T(⌈n/2⌉)T(\lceil n/2\rceil)到T(n−1)T(n-1)的每一项在总和中恰好出现两次，例如n=6，k可以从1到6，对应的结果分别为T(6−1),T(6−2),T(6−3),T(4−1),T(5−1),T(6−1)T(6-1),T(6-2),T(6-3),T(4-1),T(5-1),T(6-1)。如果n是奇数，除了中间项出现1次，其他那些类似的也会出现两次

E(T(n))≤2n∑k=⌊n/2⌋n−1E[T(k)]+O(n)E(T(n))\le\frac{2}{n}\sum_{k=\lfloor n/2\rfloor}^{n-1}E[T(k)]+O(n)

设E[T(n)]≤cnE[T(n)]\le cn，代入上式可以得到右侧是一个线性结果

最坏情况为线性时间的选择算法

  1. 将输入数组的nn个元素划分为⌊n/5⌋\lfloor n/5\rfloor组，每组5个元素，且至多只有一组由剩下的nmod  5n \mod5个元素组成
  2. 寻找这些组中每一组的中位数：首先对每组插入排序，然后确定中位数
  3. 对第2步找到的中位数们，递归调用SELECT找出其中位数
  4. 按中位数的中位数xx对输入数组进行划分。让kk比划分的低区中的元素数目多1，因此xx是第kk小的元素，并且有n−kn-k个元素在划分的高区
  5. 如果i=ki=k，则返回xx。如果i<ki<k，则在低区递归调用SELECT来找出第ii小的元素。如果i>ki>k，则在高区递归查找第i−ki-k小的元素

前提是假设所有元素互异，那么xx一定小于同一行右侧的白圈，因此阴影部分一定大于xx