快速选择算法通过三路分区和目标索引定位实现O(n)平均时间复杂度；它将第K大转换为升序下标n−k，每次仅递归含目标的一段，并返回原数组中第K大元素的任意合法下标。
快速选择算法为什么能定位第K大元素的索引
快速选择不是先排序再取值，而是通过类似快排的分区（partition）过程，每次把数组划分为“大于 pivot”“等于 pivot”“小于 pivot”三段，并根据目标位置 k 落在哪一段，只递归处理其中一段。这样避免了完整排序的开销，平均时间复杂度稳定在 O(n)。
注意：第K大 ≠ 第K小。若数组下标从 0 开始，第K大对应的是升序排列后索引为 n - k 的位置（例如 k=1 表示最大值，其升序索引是 n-1）。所以调用时需将原始 k 转换为升序下的目标索引 target = n - k。
partition 函数必须返回 pivot 的最终位置，且要支持三路划分
标准二路 partition（仅分“≥pivot”和“[>pivot][==pivot][<pivot> 三段，这样能跳过重复值，保障平均性能。</pivot>
关键点：
立即学习“C++免费学习笔记（深入）”；
-
partition返回的是 pivot 值所在区间的左边界和右边界（两个索引），而不仅是单个位置 - 后续递归时，若
target落在==pivot区间内，直接返回任意一个该区间内的索引（如lt）即可——因为题目只要“所在位置”，不要求唯一解 - 必须用随机化 pivot（如
std::uniform_int_distribution或rand() % (r - l + 1) + l），否则已排序数组会触发最坏情况
递归实现 vs 迭代实现：推荐迭代以避免栈溢出
递归写法简洁，但当 n 达到 10⁶ 级别、且数据刻意构造时，深度可能接近 n，引发栈溢出。生产代码建议改用 while 循环 + 维护 [l, r] 区间。
迭代逻辑要点：
- 每次
partition后拿到[lt, gt]（即 pivot 值所在闭区间） - 若
target ∈ [lt, gt]，直接返回lt（或任一中间索引） - 若
target ，更新 <code>r = lt - 1 - 若
target > gt，更新l = gt + 1
这样空间复杂度压到 O(1)，且无函数调用开销。
完整可运行的 C++ 源码（含测试用例）
以下代码实现了带随机 pivot 和三路 partition 的快速选择，返回第K大元素在原数组中的**任意一个合法下标**（非排序后位置）：
#include <vector>
#include <random>
#include <algorithm>
<p>int quickSelectIndex(std::vector<int>& nums, int k) {
int n = nums.size();
int target = n - k; // 升序下第 target 小的元素，即原义第 k 大
int l = 0, r = n - 1;</p><pre class='brush:php;toolbar:false;'>std::random_device rd;
std::mt19937 gen(rd());
while (l <= r) {
// 随机选 pivot 并移到末尾
std::uniform_int_distribution<> dis(l, r);
int p_idx = dis(gen);
std::swap(nums[p_idx], nums[r]);
// 三路 partition: [>p][=p][<p]
int pivot = nums[r];
int lt = l, gt = r;
int i = l;
while (i <= gt) {
if (nums[i] > pivot) {
std::swap(nums[lt++], nums[i++]);
} else if (nums[i] < pivot) {
std::swap(nums[i], nums[gt--]);
} else {
i++;
}
}
// 此时 [l, lt-1] > pivot, [lt, gt] == pivot, [gt+1, r] < pivot
if (target <= lt - 1) {
r = lt - 1;
} else if (target >= gt) {
l = gt + 1;
} else {
return lt; // 第 k 大元素在原数组中的一个有效下标
}
}
return l;}
调用示例：quickSelectIndex(nums, 2) 返回数组中第二大的数在 nums 中的某个原始下标（比如 nums[5] 就是第二大的值）。
容易被忽略的一点：该算法会**原地修改输入数组**。如果业务不允许破坏原数据，务必先拷贝 —— 这步不能省，否则线上查到的“位置”可能对应错误的值。
