可采用快速选择算法，基于Lomuto或Hoare分区方案，通过递归缩小搜索范围，在平均O(n)时间内找到第K大数。
如果需要在未排序的数组中查找第 K 大的数值，且要求平均时间复杂度为 O(n)，可采用快速选择算法。该算法基于快速排序的分区思想，通过递归缩小搜索范围，避免完全排序。以下是实现该算法的具体步骤：
一、基于 Lomuto 分区方案的快速选择
该方法每次选取末尾元素作为基准，将数组划分为小于等于和大于基准的两部分，并根据分区后基准的最终位置决定下一步递归方向。其空间复杂度为 O(1)（迭代优化后），平均时间复杂度为 O(n)。
1、定义函数 int quickSelect(vector
2、调用分区函数 partition(nums, left, right)，返回基准元素的最终下标 pos。
立即学习“C++免费学习笔记（深入）”；
3、若 pos 等于 k，则直接返回 nums[pos]。
4、若 pos 小于 k，则在右子区间 [pos + 1, right] 中递归查找。
5、若 pos 大于 k，则在左子区间 [left, pos - 1] 中递归查找。
二、基于 Hoare 分区方案的快速选择
该方法使用双向扫描，左右指针向中间移动并交换不满足条件的元素，减少交换次数，提升常数因子性能。适用于对运行效率敏感的场景。
1、定义分区函数 int hoarePartition(vector
2、内层循环中，i 向右移动直到 nums[i] >= nums[left]，j 向左移动直到 nums[j] 。
3、当 i nums[i] 和 nums[j]；否则返回 j。
4、主函数中依据返回值 j 调整搜索区间，逻辑与 Lomuto 方案一致。
三、随机化基准的快速选择
为避免最坏情况（如已排序数组）导致 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。
