快速选择算法平均时间复杂度为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。
立即学习“C++免费学习笔记（深入）”；
示例片段（找第 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 < pivotIdx) return quickSelectIndex(arr, indices, left, pivotIdx - 1, k);
else return quickSelectIndex(arr, indices, pivotIdx + 1, right, k);
}
其中 partition 必须同步交换 arr 和 indices，否则索引就脱钩了。漏掉 indices 同步是高频 bug。
第 K 大 vs 第 K 小的逻辑翻转陷阱
很多实现把第 K 大转成「第 (n−k+1) 小」再调用升序版快速选择，看似省事，但极易在边界上出错：比如 k=1（最大值）对应小标 n−1，而数组下标从 0 开始，一不留神就访问 arr[n]。
- 更安全的做法是统一用降序逻辑：partition 时让左边 ≥ pivot，右边 ≤ pivot
- 调用时直接传 k−1（因 k 从 1 计数），目标位置就是
k-1 - 如果坚持用升序版，务必检查
n-k是否在 [0, n) 范围内，且所有递归分支都用同一套偏移规则
真正麻烦的不是算法本身，而是原始位置追踪 + 大小序选择 + 索引边界这三者的耦合。少盯住一个，segmentation fault 就在下一行。
