快速选择算法定位第K大值下标而非值本身，是因为需维护原始索引映射：构造索引数组indices，按arr[indices[i]]比较并仅交换indices元素，最终indices[k]即为原数组中第K大值的原始下标；第K大对应第(n−k)小，故rank应设为n−k。
快速选择算法为什么能定位第 K 大值的下标而不是值本身
快速选择（quickselect）默认返回第 K 小/大元素的值，但你真正需要的是它在原数组中的**原始位置索引**——这要求你在分区过程中始终维护原始下标映射，不能只对值排序或拷贝。一旦你对数组做 std::sort 或用 std::nth_element 作用于副本，原始下标就丢失了。
正确做法是：构造一个索引数组 indices（如 {0,1,2,...,n-1}），然后对这个索引数组按对应值进行分区。每次比较都通过 arr[indices[i]] 取值，交换也只动 indices 中的下标。最终 indices[k] 就是原数组中第 K 大值所在的原始位置。
注意：第 K 大 = 第 (n - k) 小（0-indexed），所以调用时传入的 rank 应为 n - k，否则逻辑错位。
partition 函数必须支持自定义比较且不破坏原始数组
标准库的 std::partition 只能按值切分，无法绑定索引；手写 partition 时若直接 swap arr[i] 和 arr[j]，原始顺序就被改写了，下标失效。
实操建议：
- 只操作索引数组
indices，所有比较基于arr[indices[i]] - 使用三路划分（Lomuto 或 Hoare）均可，但 pivot 索引必须从
indices中选，比如indices[left + rand() % (right - left + 1)] - 避免用
std::swap(arr[i], arr[j])—— 这是常见错误，会导致原始数组被重排，后续无法回溯位置 - 若需多次查询不同 K，可预处理索引数组并保留，不必每次重建
平均时间复杂度 O(n) 的前提和实际波动原因
quickselect 平均 O(n) 成立的前提是：每次 partition 的 pivot 能把区间大致二分。一旦 pivot 总是最小或最大（如已排序数组+固定取首元素），就会退化到 O(n²)。
影响实际性能的关键点：
- 随机化 pivot 是必须的，否则特定输入下必慢；C++ 中用
std::random_device+std::mt19937初始化比rand()更可靠 - 小数组（如 size
- std::nth_element 是优化过的工业实现，单次查找推荐直接用它 + 索引数组配合，而非手写；但若需返回原始下标，仍要自己封装逻辑
- 内存局部性差：索引跳转访问
arr[indices[i]]可能导致 cache miss，大数据量时比纯值排序略慢，但这是换位置精度的必要代价
C++ 源码实现：返回第 K 大值原始下标
以下函数接受数组引用、K（1-indexed）、返回原始下标（int）。内部用 Hoare 分区 + 随机 pivot：
#include <vector>
#include <random>
#include <algorithm><p>int quickselect_index(const std::vector<int>& arr, int k) {
int n = arr.size();
if (k n) return -1;
int rank = n - k; // convert to 0-indexed "k-th smallest"</int></p>
<pre class="brush:php;toolbar:false;">std::vector<int> indices(n);
for (int i = 0; i pivot_val) --j;
if (i rank) right = i - 1;
else left = i + 1;
}
return indices[rank];</int>
}
调用示例：std::vector
注意：该实现未做尾递归优化，深度最坏 O(n)，但平均栈深约 O(log n)；若数据量极大且栈受限，应改写为迭代版本。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
