线性时间选择
元素选择问题的一般提法：给定线性序集中 $n$ 个元素和一个整数 $k$，$1 \leqslant k \leqslant n$，要求找出这 $n$ 个元素中第 $k$ 小的元素。即如果将这个 $n$ 个元素依基线排列时，排在第 $k$ 个位置的元素即为我们所找的元素。
在数组有序的情况下，可以很容易地通过递归的方法找到其中第 $k$ 小元素。
- 如果 $k \leqslant i-p+1 $，则 $a[p:r]$ 的第 $k$ 小元素落在子数组 $a[p:i]$ 中。
- 如果 $k > i-p+1$，则 $k$ 落在 $a[i+1:r]$ 是其中第 $k-(i-p+1)$ 小元素。
算法代码
template <class Type>
Type RandomizedSelect(Type a[], int p, int r, int k) {
if (p == r) {
return a[p];
}
int i = RandomizedPartition(a, p, r);
j = i - p + 1;
if (k <= j) {
return RandomizedSelect(a, p, i, k);
} else {
return RandomizedSelect(a, i + 1, r, k - j);
}
}
算法分析
在最坏情况下，线性时间选择算法需要 $O(n^2)$ 的计算时间。但可以证明，线性时间选择算法可以在 $O(n)$ 平均时间内找出 $n$ 个输入元素中的第 $k$ 小元素。
堆排序
现在问题升级，如果数组不是有序的，即在有 $n$ 个元素的数组中找第 $k$ 小的元素。
此问题的解决思路可以先对原始数组进行排序，然后再采用线性时间选择算法求解。这里可以采用堆排序的方法找第 k 小元素。
算法思想
为了找第 $k$ 小元素，需要将数组按照升序排序，因此建立最大堆。循环执行以下步骤，直至所有元素出堆：
- 每次堆顶元素（即最大元素）与堆中最后一个元素交换。
- 剔除最大元素后调整为最大堆。
算法分析
- 调整为最大堆：$O(\log {n})$
- 循环弹出堆顶元素：$O(n)$
因此堆排序的时间复杂度为 $O(n \log {n})$。
最终对排序后的数组进行线性时间选择，时间复杂度为 $O(n \log {n})$。因此，采用堆排序的方法求解第 $k$ 小元素的时间复杂度为 $O(n \log {n})$。
复杂度为 $O(n)$ 的算法
设数组 S 的长度为 $n$。若 $n < 50$，则采用堆排序的方法找出第 $k$ 小元素。否则，
- 将 $n$ 个元素分为 $\left \lceil n/5 \right \rceil$ 组，每组 $5$ 个元素并排序。
- 将每组的第 $3$ 个元素取出，得到大小为 $\left \lceil n/5 \right \rceil$ 的数组
M。 - 在数组
M中找第 $\left \lceil \left \lceil n/5 \right \rceil /2 \right \rceil$ 小的元素m。 - 将原数组
S分为大于m、等于m和小于m的三个集合，并计算集合中元素的个数，并将之与 $k$ 作比较，确定第 $k$ 小元素所在的集合。