快速选择算法定位第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]，原始顺序就被改写了，下标失效。
立即学习“C++免费学习笔记（深入）”；
实操建议：
- 只操作索引数组
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 < 1 || k > n) return -1;
int rank = n - k; // convert to 0-indexed "k-th smallest"</p><pre class='brush:php;toolbar:false;'>std::vector<int> indices(n);
for (int i = 0; i < n; ++i) indices[i] = i;
std::random_device rd;
std::mt19937 g(rd());
int left = 0, right = n - 1;
while (left < right) {
int pivot_idx = left + g() % (right - left + 1);
std::swap(indices[pivot_idx], indices[right]);
int pivot_val = arr[indices[right]];
int i = left, j = right - 1;
while (i <= j) {
while (i <= j && arr[indices[i]] < pivot_val) ++i;
while (i <= j && arr[indices[j]] > pivot_val) --j;
if (i <= j) {
std::swap(indices[i], indices[j]);
++i; --j;
}
}
std::swap(indices[i], indices[right]);
if (i == rank) break;
else if (i > rank) right = i - 1;
else left = i + 1;
}
return indices[rank];}
调用示例：std::vector<int> a = {3, 2, 1, 5, 4}; int pos = quickselect_index(a, 2); // 返回 3（a[3] == 5，是第2大）</int>
注意：该实现未做尾递归优化，深度最坏 O(n)，但平均栈深约 O(log n)；若数据量极大且栈受限，应改写为迭代版本。
