可采用快速选择算法，基于Lomuto或Hoare分区方案，通过递归缩小搜索范围，在平均O(n)时间内找到第K大数。

如果需要在未排序的数组中查找第 K 大的数值，且要求平均时间复杂度为 O(n)，可采用快速选择算法。该算法基于快速排序的分区思想，通过递归缩小搜索范围，避免完全排序。以下是实现该算法的具体步骤：

一、基于 Lomuto 分区方案的快速选择

该方法每次选取末尾元素作为基准，将数组划分为小于等于和大于基准的两部分，并根据分区后基准的最终位置决定下一步递归方向。其空间复杂度为 O(1)（迭代优化后），平均时间复杂度为 O(n)。

1、定义函数 int quickSelect(vector& nums, int left, int right, int k)，其中 k 表示目标索引（从 0 开始，对应第 (k+1) 大数）。

2、调用分区函数 partition(nums, left, right)，返回基准元素的最终下标 pos。

3、若 pos 等于 k，则直接返回 nums[pos]。

4、若 pos 小于 k，则在右子区间 [pos + 1, right] 中递归查找。

5、若 pos 大于 k，则在左子区间 [left, pos - 1] 中递归查找。

二、基于 Hoare 分区方案的快速选择

该方法使用双向扫描，左右指针向中间移动并交换不满足条件的元素，减少交换次数，提升常数因子性能。适用于对运行效率敏感的场景。

1、定义分区函数 int hoarePartition(vector& nums, int left, int right)，初始化 i = left - 1，j = right + 1。

2、内层循环中，i 向右移动直到 nums[i] >= nums[left]，j 向左移动直到 nums[j] 。

3、当 i nums[i] 和 nums[j]；否则返回 j。

4、主函数中依据返回值 j 调整搜索区间，逻辑与 Lomuto 方案一致。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

三、随机化基准的快速选择

为避免最坏情况（如已排序数组）导致 O(n²) 时间复杂度，每次递归前随机选择一个索引与右端点交换，使基准元素期望均匀分布。

1、在每次调用分区函数前，生成随机索引 randIdx = left + rand() % (right - left + 1)。

2、交换 nums[randIdx] 与 nums[right]。

3、随后执行标准 Lomuto 或 Hoare 分区流程。

4、确保程序开始时已调用 srand(time(nullptr)) 初始化随机数种子。

四、迭代版本的快速选择（避免递归栈开销）

使用 while 循环替代递归调用，手动维护待处理区间，显著降低函数调用开销与栈溢出风险，尤其适用于大规模数据。

1、初始化变量 left = 0, right = nums.size() - 1。

2、进入循环，执行分区操作获取 pos。

3、若 pos == k，则跳出循环并返回 nums[k]。

4、若 pos left = pos + 1。

5、若 pos > k，则令 right = pos - 1。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！