快速选择算法是快速排序的变种，核心思路是通过划分操作将数组分为两部分，根据划分后基准元素的位置判断目标第K大数所在的区间，从而只对目标区间进行递归处理，避免全量排序，最终实现平均O(n)的时间复杂度。该算法不需要额外开辟大量存储空间，空间复杂度为O(1)（不考虑递归栈的情况下），在处理大规模数据选择场景时优势明显。
快速选择算法核心原理
快速选择算法的执行流程和快速排序类似，但不需要对所有子区间都进行排序：
- 首先选择一个基准元素，通过划分操作将数组分为两部分，左边部分的元素都大于等于基准，右边部分的元素都小于等于基准
- 划分完成后，基准元素的位置就是它在排序后数组中的最终位置
- 如果基准位置正好是第K大数对应的位置（数组从0开始索引时，第K大数的位置为K-1），则直接返回基准元素
- 如果基准位置大于K-1，说明第K大数在左边区间，递归处理左边区间
- 如果基准位置小于K-1，说明第K大数在右边区间，递归处理右边区间
C++实现完整源码
以下是查找第K大数的快速选择算法完整C++实现，包含划分函数和主选择函数：
#include <iostream>
#include <vector>
#include <stdexcept>
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;
}
// 快速选择主函数，查找nums中第k大的元素，k从1开始计数
int quickSelect(vector<int>& nums, int left, int right, int k) {
if (left == right) {
return nums[left];
}
// 进行划分
int pos = partition(nums, left, right);
// 第k大数对应的索引是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) {
int n = nums.size();
if (k < 1 || k > n) {
throw invalid_argument("k值超出数组范围");
}
return quickSelect(nums, 0, n - 1, k);
}
int main() {
vector<int> testNums = {3, 2, 1, 5, 6, 4};
int k = 2;
try {
int result = findKthLargest(testNums, k);
cout << "第" << k << "大的数是：" << result << endl;
} catch (const invalid_argument& e) {
cout << "错误：" << e.what() << endl;
}
return 0;
}
代码说明与边界处理
上述实现中需要注意几个关键点：
- 划分函数选择最右侧元素作为基准，也可以根据需求选择随机位置作为基准，避免有序数组下的性能退化
- 第K大数的索引计算：数组从0开始，第1大数对应索引0，第K大数对应索引K-1，这个对应关系不能出错
- 对外接口
findKthLargest做了k值的合法性校验，避免传入超出数组范围的k值导致运行时错误 - 递归终止条件是
left == right，此时区间内只有一个元素，直接返回即可
算法性能分析
快速选择算法的平均时间复杂度为O(n)，最坏情况下（每次划分都选到最小或最大元素）时间复杂度为O(n²)，但通过随机选择基准的方式可以将最坏情况的概率降到极低。空间复杂度方面，不考虑递归调用栈的话是O(1)，递归调用栈的深度平均为O(logn)，最坏为O(n)。
和先排序再取第K个元素的方法相比，快速选择不需要全量排序，在n较大、k较小或较大的场景下性能优势非常明显，是处理第K大/第K小问题的最优解之一。