在C++编程中，求解数组的第k大元素是常见的基础算法问题，暴力解法通常是对整个数组进行排序后直接取第k个位置的元素，这种方式的时间复杂度为O(n log n)，当数组规模较大时效率偏低。快速选择算法基于快速排序的分区逻辑，不需要完成全数组排序，平均时间复杂度仅为O(n)，是解决该问题的高效方案。
快速选择算法核心原理
快速选择算法的核心思想和快速排序一致，都是通过选取一个基准元素，将数组分为两部分：小于基准的元素和大于等于基准的元素。不同之处在于，快速排序会递归处理左右两个子数组，而快速选择算法只需要根据目标位置所在的区间，递归处理对应的子数组即可，不需要处理另一部分，从而减少不必要的计算。
假设我们要找数组的第k大元素，首先选取一个基准值，经过一次分区后，基准值的位置为pos，那么：
- 如果pos正好等于k-1（数组下标从0开始），那么基准值就是第k大元素，直接返回即可
- 如果pos大于k-1，说明第k大元素在基准值左侧的子数组中，递归处理左子数组
- 如果pos小于k-1，说明第k大元素在基准值右侧的子数组中，递归处理右子数组
C++实现快速选择算法
分区函数实现
分区函数是快速选择的基础，作用是选取基准元素，将数组调整为基准左侧元素都大于等于基准，右侧元素都小于基准的结构，同时返回基准的最终位置。
#include <vector>
#include <iostream>
using namespace std;
// 分区函数，返回基准元素最终位置
int partition(vector<int>& nums, int left, int right) {
// 选取最右侧元素作为基准
int pivot = nums[right];
int i = left - 1;
for (int j = left; j < right; j++) {
// 找大于等于基准的元素放到左侧
if (nums[j] >= pivot) {
i++;
swap(nums[i], nums[j]);
}
}
// 将基准放到正确位置
swap(nums[i + 1], nums[right]);
return i + 1;
}
快速选择主函数实现
主函数通过递归调用分区函数，逐步缩小查找范围，直到找到第k大元素的位置。
// 快速选择函数，查找nums中第k大的元素
int quickSelect(vector<int>& nums, int left, int right, int k) {
if (left == right) {
return nums[left];
}
// 获取分区后的基准位置
int pos = partition(nums, left, right);
// 目标位置是k-1（下标从0开始）
if (pos == k - 1) {
return nums[pos];
} else if (pos > k - 1) {
// 目标在左侧子数组
return quickSelect(nums, left, pos - 1, k);
} else {
// 目标在右侧子数组
return quickSelect(nums, pos + 1, right, k);
}
}
// 对外暴露的接口函数
int findKthLargest(vector<int>& nums, int k) {
return quickSelect(nums, 0, nums.size() - 1, k);
}
测试代码示例
下面是一段测试代码，验证快速选择算法的正确性。
int main() {
vector<int> nums = {3, 2, 1, 5, 6, 4};
int k = 2;
int result = findKthLargest(nums, k);
cout << "数组的第" << k << "大元素是：" << result << endl;
// 输出结果：数组的第2大元素是：5
return 0;
}
算法注意事项
快速选择算法的平均时间复杂度为O(n)，但最坏情况下（每次选取的基准都是最小或最大元素），时间复杂度会退化到O(n²)，可以通过随机选择基准元素的方式降低最坏情况出现的概率。另外，该算法会修改原数组的顺序，如果要求不能修改原数组，需要先拷贝一份数组再进行处理。同时要注意k的取值范围，需要保证1 ≤ k ≤ 数组长度，避免数组越界的问题。