快速选择算法是基于快速排序分区思想改进的选择类算法，核心目标是在未排序的数组中快速定位第K大数值的位置，不需要对整个数组完成全排序，因此在实际应用中比先排序再取值的方案效率更高。该算法的核心逻辑是通过每次分区操作确定一个基准元素的最终位置，再根据基准元素的位置与目标K的关系，缩小查找范围，直到找到目标位置。
快速选择算法核心逻辑
快速选择算法的执行流程可以分为三个核心步骤：
- 选择数组中的一个元素作为基准元素，通常可以选择数组首元素、尾元素或者随机位置的元素。
- 执行分区操作，将数组中小于基准元素的元素移动到基准左侧，大于基准元素的元素移动到基准右侧，完成后基准元素的位置就是它在最终有序数组中的位置。
- 比较基准元素的位置与目标第K大数值的位置关系：如果基准位置刚好等于目标位置，直接返回该位置；如果基准位置大于目标位置，说明目标在基准左侧的子数组中，递归处理左子数组；如果基准位置小于目标位置，说明目标在基准右侧的子数组中，递归处理右子数组。
C++实现查找第K大数值位置
以下是完整的C++实现代码，包含分区函数和快速选择主函数，能够返回第K大数值在数组中的索引位置：
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
// 分区函数，返回基准元素的最终位置
int partition(std::vector<int>& arr, int left, int right) {
// 随机选择一个基准元素，避免最坏情况
int pivotIndex = left + rand() % (right - left + 1);
int pivot = arr[pivotIndex];
// 将基准元素交换到数组末尾
std::swap(arr[pivotIndex], arr[right]);
int storeIndex = left;
for (int i = left; i < right; i++) {
// 如果当前元素大于基准，说明属于第K大排序的左侧部分，放到storeIndex位置
if (arr[i] > pivot) {
std::swap(arr[storeIndex], arr[i]);
storeIndex++;
}
}
// 将基准元素放回最终位置
std::swap(arr[storeIndex], arr[right]);
return storeIndex;
}
// 快速选择主函数，返回第k大元素的索引，k从1开始计数
int quickSelect(std::vector<int>& arr, int left, int right, int k) {
if (left == right) {
return left;
}
int pivotPos = partition(arr, left, right);
// 目标位置是数组长度减去k，因为第k大对应升序排序的第len-k个位置（索引从0开始）
int targetPos = arr.size() - k;
if (pivotPos == targetPos) {
return pivotPos;
} else if (pivotPos > targetPos) {
return quickSelect(arr, left, pivotPos - 1, k);
} else {
return quickSelect(arr, pivotPos + 1, right, k);
}
}
int main() {
srand(time(nullptr));
std::vector<int> arr = {3, 2, 1, 5, 6, 4};
int k = 2;
int pos = quickSelect(arr, 0, arr.size() - 1, k);
std::cout << "第" << k << "大数值是：" << arr[pos] << "，位置索引是：" << pos << std::endl;
return 0;
}
上述代码中，分区函数采用随机选择基准的方式，避免数组本身有序时触发最坏时间复杂度。主函数通过递归不断缩小查找范围，直到基准位置与目标位置匹配，返回对应的索引。
平均复杂度分析
快速选择算法的平均时间复杂度远低于全排序方案，具体分析如下：
- 平均时间复杂度：每次分区操作会将数组划分为两个部分，平均情况下每次划分的规模会减半，第i次分区的时间复杂度是O(n/i)，累加后得到总平均时间复杂度为
O(n)，n为数组长度。相比快速排序的平均O(n log n)复杂度，快速选择不需要处理所有子数组，效率更高。 - 最坏时间复杂度：如果每次选择的基准都是数组的最小或最大元素，那么每次分区只能减少一个元素，此时时间复杂度会退化为
O(n²)，采用随机基准选择的方式可以极大概率避免这种情况。 - 空间复杂度：递归调用栈的深度平均情况下是O(log n)，最坏情况下是O(n)，如果采用迭代实现可以将空间复杂度优化到O(1)。
与常规方案对比
常见的查找第K大数值的方案有三种，各自的特性对比如下：
| 方案 | 平均时间复杂度 | 是否需要全排序 | 适用场景 |
|---|---|---|---|
| 全排序后取值 | O(n log n) | 是 | 需要同时获取有序数组全部元素的场景 |
| 堆排序维护大小为K的小顶堆 | O(n log K) | 否 | 数组规模极大，K远小于n的场景 |
| 快速选择算法 | O(n) | 否 | 单次查找第K大，不需要全有序的场景 |
可以看出，快速选择算法在单次查找第K大的场景下平均效率最优，是处理这类问题的首选方案。