如何用C++实现快速选择算法查找第K大数且保证平均时间复杂度为O(n)

快速选择算法的核心思路是借鉴快速排序的分区操作，每次选择一个基准元素将数组分为两部分，根据基准元素的位置判断第K大数所在的区间，只递归处理目标区间，从而减少不必要的排序操作，实现平均O(n)的时间复杂度。该算法不需要对整个数组完成排序，仅需要定位到第K大元素的位置即可，在处理大规模数据查找第K大、第K小元素的场景中非常实用。

快速选择算法原理

快速选择算法的执行流程可以分为以下几个核心步骤：

• 从数组中选择一个基准元素，通常可以选择数组的第一个元素、最后一个元素或者随机位置的元素
• 对数组进行分区操作，将小于基准的元素放到基准左侧，大于基准的元素放到基准右侧，完成后基准元素会处于其最终排序位置
• 假设数组长度为n，基准元素的最终位置为pos，那么基准元素就是数组的第(n-pos)大元素（如果按升序分区的话）
• 如果(n-pos)等于K，说明当前基准元素就是目标第K大数，直接返回即可
• 如果(n-pos)大于K，说明第K大数在基准元素的右侧区间，递归处理右侧区间
• 如果(n-pos)小于K，说明第K大数在基准元素的左侧区间，递归处理左侧区间，同时更新K的值为K - (n-pos)

C++实现完整源码

以下是基于上述原理实现的C++查找第K大数的完整代码，包含分区函数和快速选择主函数，同时提供了测试示例：

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

// 分区函数，选择最右侧元素作为基准，返回基准的最终位置
int partition(std::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++;
            std::swap(nums[i], nums[j]);
        }
    }
    // 将基准元素放到正确位置
    std::swap(nums[i + 1], nums[right]);
    return i + 1;
}

// 快速选择递归函数，查找第K大数
int quickSelect(std::vector<int>& nums, int left, int right, int k) {
    if (left == right) {
        return nums[left]; // 区间只有一个元素，直接返回
    }
    // 随机选择一个基准位置，避免最坏情况
    int randomIdx = left + rand() % (right - left + 1);
    std::swap(nums[randomIdx], nums[right]);
    
    int pos = partition(nums, left, right); // 基准的最终位置
    // 计算当前基准是第几大元素（升序分区下，位置越靠后元素越大）
    int bigCount = right - pos + 1;
    
    if (bigCount == k) {
        return nums[pos]; // 找到目标第K大数
    } else if (bigCount > k) {
        // 第K大数在基准右侧
        return quickSelect(nums, pos + 1, right, k);
    } else {
        // 第K大数在基准左侧，更新K值
        return quickSelect(nums, left, pos - 1, k - bigCount);
    }
}

// 对外暴露的查找第K大数接口
int findKthLargest(std::vector<int>& nums, int k) {
    srand(time(nullptr)); // 初始化随机种子
    return quickSelect(nums, 0, nums.size() - 1, k);
}

int main() {
    std::vector<int> testNums = {3, 2, 1, 5, 6, 4};
    int k = 2;
    int result = findKthLargest(testNums, k);
    std::cout << "数组中的第" << k << "大数是：" << result << std::endl;
    
    std::vector<int> testNums2 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    k = 5;
    result = findKthLargest(testNums2, k);
    std::cout << "数组中的第" << k << "大数是：" << result << std::endl;
    return 0;
}

代码说明与复杂度分析

关键细节说明

上述实现中加入了随机选择基准的逻辑，通过rand()函数随机选择一个位置的元素作为基准，避免数组本身有序时每次分区都只能减少一个元素，导致时间复杂度退化为O(n²)的最坏情况。分区函数采用常见的挖坑法变体，将小于基准的元素移动到左侧，最终将基准放到正确位置。

时间复杂度

快速选择算法的平均时间复杂度为O(n)，因为每次递归处理的区间长度大致为上一轮的一半，总操作次数近似为n + n/2 + n/4 + ... ≈ 2n，即O(n)级别。最坏情况下时间复杂度为O(n²)，但随机选择基准的方式可以让最坏情况出现的概率极低，实际使用中平均性能非常稳定。

空间复杂度

由于算法是递归实现，空间复杂度主要来自递归调用栈，平均情况下递归深度为O(logn)，最坏情况下为O(n)，如果改为迭代实现可以将空间复杂度优化到O(1)。

适用场景

快速选择算法适合需要在未排序数组中查找第K大、第K小元素的场景，尤其是数据规模较大、不需要完整排序结果的情况，相比先排序再取值的O(nlogn)方案性能优势明显。如果数组本身已经有序或者需要频繁查找不同K值的第K大数，建议先对数组进行一次排序，后续查找可以直接通过索引获取，效率更高。

快速选择算法C++第K大数O(n)_平均时间复杂度修改时间：2026-07-06 17:09:31