线性时间选择
元素选择问题的一般提法:给定线性序集中
在数组有序的情况下,可以很容易地通过递归的方法找到其中第
- 如果
,则 的第 小元素落在子数组 中。 - 如果
,则 落在 是其中第 小元素。
算法代码
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);
}
}
算法分析
在最坏情况下,线性时间选择算法需要
堆排序
现在问题升级,如果数组不是有序的,即在有
此问题的解决思路可以先对原始数组进行排序,然后再采用线性时间选择算法求解。这里可以采用堆排序的方法找第 k 小元素。
算法思想
为了找第
- 每次堆顶元素(即最大元素)与堆中最后一个元素交换。
- 剔除最大元素后调整为最大堆。
算法分析
- 调整为最大堆:
- 循环弹出堆顶元素:
因此堆排序的时间复杂度为
最终对排序后的数组进行线性时间选择,时间复杂度为
复杂度为 的算法
设数组 S
的长度为
- 将
个元素分为 组,每组 个元素并排序。 - 将每组的第
个元素取出,得到大小为 的数组M
。 - 在数组
M
中找第 小的元素m
。 - 将原数组
S
分为大于m
、等于m
和小于m
的三个集合,并计算集合中元素的个数,并将之与 作比较,确定第 小元素所在的集合。