快速选择算法默认返回第K小/大元素的值，但要原始下标需绑定值与索引为pair，按值partition、返索引；第K大需转为找第n−K小；必须随机化pivot并正确处理Hoare分区边界。
快速选择算法为什么能找第 K 大值的位置而不是值本身
快速选择（QuickSelect）默认返回第 K 小/大元素的值，但你真正要的是它在原数组中的**原始下标位置**——这点容易被忽略。因为 partition 过程会重排元素，原始索引信息在交换中丢失，所以不能边选边记位置，必须提前绑定索引。
正确做法是：构造 std::vector<:pair int>></:pair>，把 value 和原始 index 一起存进去，后续所有比较、交换都基于 first（值），但最终返回 second（原始下标）。
- 别直接对原数组排序或用
std::nth_element后查值——它不保证返回首次出现位置，且无法反查原始下标 - 如果 K 是“第 K 大”，注意转换：实际找的是第
n - K小（0-indexed），例如 5 个数中第 1 大 = 第 0 小，第 2 大 = 第 1 小 - partition 时比较逻辑必须统一：按值比，但 swap 要同步交换 pair 的两个成员
手写 partition 时最容易崩的三个边界条件
标准 Lomuto 或 Hoare partition 在快速选择里一旦写错下标，就会越界或死循环。尤其当输入含重复值、K 落在重复段中间时，left == right 或 l > r 判断漏掉，递归就停不下来。
推荐用 Hoare 风格 + 闭区间迭代，关键检查点：
立即学习“C++免费学习笔记（深入）”；
- 初始
l = 0, r = n - 1，递归调用时传入[l, p - 1]和[p + 1, r]，不是[l, p]或[p, r] - while 循环内必须先
++i/--j再判断，否则可能卡在 pivot 上不动 - 当
arr[i].first 才 <code>i++，>才j--；大小方向反了会导致 partition 偏斜，平均复杂度退化成 O(n²)
平均 O(n) 的前提是 pivot 随机化，否则最坏 O(n²)
用固定位置（如取 arr[l]）当 pivot，遇到已排序或逆序数组，每次 partition 只减少一个元素，递归深度 n 层，每层扫描剩余元素，总耗时 ≈ n + (n−1) + … + 1 = O(n²)。
必须加随机化：
- 在 partition 前，用
std::uniform_int_distribution生成[l, r]内随机索引rnd - swap
arr[rnd]和arr[r]，再以arr[r]为 pivot —— 这样 pivot 分布均匀，数学期望递归深度为 O(log n)，每层处理元素总数 O(n)，均摊 O(n) - 别用
rand() % (r - l + 1) + l：低比特周期短，小数组上容易重复选同一位置
C++ 完整可运行源码（带原始位置追踪）
#include <vector>
#include <random>
#include <utility>
<p>int quickSelectIndex(std::vector<std::pair<int, int>>& arr, int l, int r, int k) {
if (l == r) return arr[l].second;</p><pre class='brush:php;toolbar:false;'>// 随机 pivot
std::random_device rd;
std::mt19937 g(rd());
std::uniform_int_distribution<int> dist(l, r);
int rnd = dist(g);
std::swap(arr[rnd], arr[r]);
int pivot = arr[r].first;
int i = l, j = r - 1;
while (i <= j) {
while (i <= j && arr[i].first < pivot) i++;
while (i <= j && arr[j].first > pivot) j--;
if (i <= j) {
std::swap(arr[i], arr[j]);
i++; j--;
}
}
std::swap(arr[i], arr[r]);
if (i == k) return arr[i].second;
else if (k < i) return quickSelectIndex(arr, l, i - 1, k);
else return quickSelectIndex(arr, i + 1, r, k);}
// 调用示例：找 nums 中第 k 大元素的原始下标（k 从 1 开始）
int findKthLargestIndex(const std::vector 注意 quickSelectIndex 返回的是原始下标，不是值；n - k 这一转换在调用处完成，避免在递归内部反复算；std::mt19937 初始化开销略高，若高频调用，应把引擎提到外部作用域复用。
