快速选择算法通过分区操作将第K大元素置于目标下标（升序下标n−k），而非直接返回值；若需原始位置，须用索引数组代替数值数组进行partition，确保swap仅移动索引，最终idx[k]即为原数组中第K大值的首次出现下标。
快速选择算法为什么能定位第K大值的下标而不是值本身
因为标准的 std::nth_element 或手写 partition 逻辑，默认按升序排列后取第 k 个位置，而“第K大”对应的是降序下的第 k 个——等价于升序下的第 n−k 个（0-indexed）。但注意：std::nth_element 不保证其余元素有序，只保证目标位置放对了数，且左边 ≤ 它、右边 ≥ 它（升序语义）。所以若要返回“原始数组中第K大值的**首次出现位置**”，不能直接调 std::nth_element 后遍历原数组找值——它可能已移动；必须在 partition 过程中记录原始索引。
手写 partition 时如何保留原始下标信息
核心是不直接操作数值数组，而是操作索引数组。例如：vector<int> idx(n); iota(idx.begin(), idx.end(), 0);</int>，然后对 idx 排序，比较逻辑用 arr[idx[i]]。这样每次 swap 的是索引，最终 idx[k] 就是原数组中第K大值所在的原始下标（升序下第 k 位对应第 n−1−k 大，需换算）。
- 若求第1大（最大值），对应升序下标
n−1；第K大 → 升序下标n−k（1-indexed K）或n−k（0-indexed K）需看题设，常见为1-indexed - partition 函数里比较必须用
arr[idx[l]] ，不能漏掉 <code>arr[...]层级 - 递归调用时传的是
idx的子区间迭代器，不是arr
平均 O(n) 成立的前提和实际性能陷阱
理论平均复杂度 O(n) 要求每次 pivot 能把数组大致二分，即 partition 后左右规模都接近 n/2。但若每次选最值当 pivot（如固定选首/尾），退化为 O(n²)，尤其在已排序或逆序数组上。实践中建议：
- 用
rand() % (r - l + 1)随机选 pivot 索引，再与右端交换 —— 简单有效 - 避免用
std::random_shuffle全局打乱，它 O(n)，破坏“仅需部分有序”的初衷 - 小数组（如 size
- g++ 的
std::nth_element内部用 introselect（堆+快选混合），一般比手写更稳，但不返回下标
一个可直接跑的下标版快速选择示例
int quickSelectIndex(vector<int>& arr, int k) {
int n = arr.size();
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
// k 是 1-indexed 第K大 → 升序下标 pos = n - k
int pos = n - k;
int l = 0, r = n - 1;
while (l < r) {
int pivotIdx = l + rand() % (r - l + 1);
swap(idx[pivotIdx], idx[r]);
int i = l, j = r - 1;
while (i <= j) {
while (i <= j && arr[idx[i]] <= arr[idx[r]]) i++;
while (i <= j && arr[idx[j]] >= arr[idx[r]]) j--;
if (i < j) swap(idx[i++], idx[j--]);
}
swap(idx[i], idx[r]);
if (i == pos) return idx[i];
else if (i > pos) r = i - 1;
else l = i + 1;
}
return idx[l];
}
注意：这里 arr[idx[i]] <= arr[idx[r]] 是升序 partition，确保最终 idx[pos] 存放的是升序第 pos 小的元素，即原数组第K大值的原始下标。边界判断和 swap 位置稍有不慎就会越界或逻辑翻转，尤其是 i 和 r 的最终交换那步——这是最容易写错的地方。
立即学习“C++免费学习笔记（深入）”；
