快速选择算法能定位第K大值的下标，是因为它通过维护下标数组并按对应值比较，确保partition过程不改变原数组而只重排索引；当算法收敛时，下标数组中对应位置即为原始索引。
快速选择算法为什么能定位第K大值的下标，而不是只返回值
快速选择算法本质是快排的剪枝版，它不保证整个数组有序，但能确保某次划分后，轴点（pivot）的最终位置恰好是目标序号。要返回“位置”而非“值”，关键是在每次 partition 后不丢弃原始索引信息——不能对原数组做无痕排序，而应操作索引数组或携带下标元组。
常见错误是直接对数值数组调用 std::nth_element 或手写快选，结果只能拿到第K大值，却不知道它原来在哪儿。正确做法是：维护一个下标数组 indices，按对应值排序该数组，即用 values[indices[i]] 比较大小。
- 初始化
indices为{0, 1, 2, ..., n-1} - 在
partition中比较逻辑改为values[indices[i]] > values[indices[pivot]] - 递归时只重排
indices的子区间，values始终不动 - 当分区收敛到单个下标时，
indices[left]就是原数组中第K大值的原始位置
std::nth_element 能不能直接用？要注意什么
可以，但必须配合自定义比较器和索引绑定，否则它只重排数值本身。标准库函数 std::nth_element 默认按值排序，若传入原始 vector<int></int>，原数组会被修改，原始位置彻底丢失。
安全用法是传入下标容器，并用 lambda 指定比较规则：
立即学习“C++免费学习笔记（深入）”；
vector<int> values = {3, 2, 1, 5, 6, 4};
vector<size_t> indices(values.size());
iota(indices.begin(), indices.end(), 0);
size_t k = 2; // 求第2大 → 实际是升序下标 n-k
nth_element(indices.begin(), indices.begin() + k - 1, indices.end(),
[&](size_t i, size_t j) { return values[i] > values[j]; });
// 此时 indices[k-1] 就是原数组中第K大值的下标
注意：std::nth_element 是部分排序，平均复杂度 O(n)，但最坏 O(n²)；它不保证前K个元素有序，只保证第K位正确、左边≤右边≥（依比较器而定）。
手写 partition 时最容易错的边界和循环条件
手写快选的 partition 函数，90% 的 bug 出在三处：轴点选择策略、双指针越界判断、递归区间闭合性。尤其当目标是“第K大”时，容易混淆升序/降序逻辑。
- 轴点别用
arr[left]硬编码——用arr[left + rand() % (right - left + 1)]随机交换到右端，避免已排序输入退化 - 双指针
i和j初始化为left和right - 1（若轴点放right），循环内先移动再比较，防止越界访问 - 比较条件必须与目标一致：求第K大 →
arr[i] > pivot才停，否则会把大数扫到右边去 - 递归调用时，若轴点最终位置是
p，则第K大对应升序下标n - k，需判断p == n-k、p > n-k、p 三种情况，区间传递用 <code>[left, p-1]和[p+1, right]，别漏掉=
平均时间复杂度 O(n) 是怎么算出来的，为什么实际可能比 sort 还慢
O(n) 是期望复杂度，基于每次划分都能淘汰常数比例（如 1/4）元素的假设。数学上可推得递推式 T(n) ≤ T(3n/4) + O(n)，解得 T(n) = O(n)。但这依赖随机轴点，且隐藏系数不小（约 3~4 倍于一次扫描）。
实际性能受数据分布影响极大：
- 小数组（
n ）用快选反而不如 <code>std::sort+ 直接取[n-k]，因为后者有优化汇编和缓存友好性 - 重复值多时，基础
partition退化为O(n²)，需改用三路划分（） - 内存局部性差：手写版本若操作索引数组，会引发大量非连续
values访问，L1 cache miss 率升高 - 调试模式下迭代器开销、边界检查也会吃掉优势
真正需要手写快选的场景，通常是嵌入式或高频交易里对同一数组反复查不同K值，且已知数据足够随机——否则优先信 std::nth_element，它内部做了不少工程优化。
