快速选择算法平均时间复杂度为O(n)，因其每轮期望排除一半元素，处理规模几何衰减，总比较次数期望约1.39n次；std::nth_element不返回原始索引，需额外保存位置映射。
快速选择算法的平均时间复杂度为什么是 O(n)
因为每次划分后，我们只递归处理包含目标位置的那一侧子数组，而期望情况下每次能排除约一半元素。虽然最坏情况（如每次选到最小/最大元素作 pivot）会退化到 O(n²)，但用随机化 pivot 或三数取中后，数学期望下比较总次数收敛于约 1.39n 次 —— 这就是 O(n) 的由来。
注意：这不是「每次都刚好砍掉一半」，而是「每轮处理规模按几何级数衰减」，累加后仍是线性。常见误解是把它和快排的平均 O(n log n) 类比，但快排要处理两边，快速选择只进一边。
std::nth_element 能直接用，但不返回索引位置
std::nth_element 是标准库对快速选择的实现，但它只保证第 k 个位置放好目标值，不保证返回该值在原数组中的原始下标。如果你需要的是「第 K 大数值在原数组里的原始位置（而非排序后位置）」，就不能直接用它完事。
- 它会重排原容器，原始索引信息丢失
- 若需原始位置，得提前保存索引映射，比如用
vector<pair int>></pair>存{value, original_index} - 自定义比较函数时，注意第 K 大对应的是
nth_element(..., greater)下的第 k-1 位
手写 partition + 随机 pivot 的关键细节
核心是 partition 函数必须返回 pivot 最终落点，并确保左侧 ≥ pivot、右侧 ≤ pivot（对第 K 大而言）。别写成升序 partition 后再反向算位置，容易越界或 off-by-one。
示例片段（找第 k 大，k 从 1 开始）：
int quickSelectIndex(vector<int>& arr, vector<int>& indices, int left, int right, int k) {
if (left == right) return indices[left];
int pivotIdx = left + rand() % (right - left + 1);
pivotIdx = partition(arr, indices, left, right, pivotIdx);
if (k == pivotIdx) return indices[k];
else if (k <p>其中 <code>partition</code> 必须同步交换 <code>arr</code> 和 <code>indices</code>，否则索引就脱钩了。漏掉 <code>indices</code> 同步是高频 bug。</p>
<h3>第 K 大 vs 第 K 小的逻辑翻转陷阱</h3>
<p>很多实现把第 K 大转成「第 (n−k+1) 小」再调用升序版快速选择，看似省事，但极易在边界上出错：比如 k=1（最大值）对应小标 n−1，而数组下标从 0 开始，一不留神就访问 <code>arr[n]</code>。</p>
<ul>
<li>更安全的做法是统一用降序逻辑：partition 时让左边 ≥ pivot，右边 ≤ pivot</li>
<li>调用时直接传 k−1（因 k 从 1 计数），目标位置就是 <code>k-1</code>
</li>
<li>如果坚持用升序版，务必检查 <code>n-k</code> 是否在 [0, n) 范围内，且所有递归分支都用同一套偏移规则</li>
</ul>
<p>真正麻烦的不是算法本身，而是原始位置追踪 + 大小序选择 + 索引边界这三者的耦合。少盯住一个，<code>segmentation fault</code> 就在下一行。</p></int></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
