快速选择算法定位第K大值的索引而非值本身，是因为原地分区后目标值落在局部子区间特定位置（如升序下索引n−k），该索引非原始下标；若需原始位置，须同步维护索引数组或值-下标对。
快速选择算法为什么能定位第 K 大值的索引而不是值本身
快速选择的目标是找到第 K 大（或第 K 小）元素的值，但“所在位置”取决于你是否在原数组上操作。如果你不复制数组、直接对 std::vector<int>&</int> 原地分区，那么算法结束时，第 K 大值必然落在索引 k-1（升序下第 K 小）或 n-k（升序下第 K 大）处——但这个索引是**当前递归子区间的局部偏移**，不是原始数组中的初始下标。
要返回原始位置，必须：保留原始索引映射，或用 std::vector<:pair int>></:pair> 存（值，原下标），并在分区时连带移动下标。否则，仅靠值无法反推原始位置。
- 常见错误：调用
quickSelect(nums, 0, n-1, k)后直接返回k-1，这错把目标值的排序序号当成了原始索引 - 正确做法：若需原始下标，初始化时构建索引数组
indices，所有swap操作同步作用于nums和indices - 若只关心值，无需记录位置；若题目要求“返回下标”，必须显式维护位置信息
partition 函数里用 nums[l] 还是随机选 pivot？
用固定首元素作 pivot（如 nums[l]）会导致最坏 O(n²) 复杂度，例如数组已升序且总选左端点——此时每次 partition 只减少一个元素。随机化 pivot 是简单有效的优化手段，平均复杂度稳定在 O(n)，且实现成本极低。
- 推荐写法：
int randIdx = l + rand() % (r - l + 1); std::swap(nums[randIdx], nums[l]);，再以nums[l]为 pivot 分区 - 注意：调用前需
srand(time(nullptr))（仅一次），否则rand()序列重复，退化风险仍高 - C++11 起更稳妥用
std::random_device+std::mt19937，但竞赛/面试中rand()随机化已足够 - 不随机化时，面对有序数据测试用例大概率超时
如何把“第 K 大”转成快速选择的标准参数（第 K 小语义）
快速选择标准实现都是找第 K 小（即升序排列后索引为 K−1 的元素）。所以“第 K 大”需转换：在大小为 n 的数组中，第 K 大 = 第 (n - K) 小（0-indexed 下目标索引是 n - K）。
立即学习“C++免费学习笔记（深入）”；
- 例如数组
[3,2,1,5,6,4]，n=6，求第 2 大 → 目标是升序后索引6-2 = 4处的元素（升序为[1,2,3,4,5,6]，索引 4 是 5，正确） - 传参时调用
quickSelect(nums, 0, n-1, n - k)，而非k-1或k - 边界检查别漏：确保
k >= 1 && k ，否则 <code>n-k可能越界
完整可运行的源码（带原始下标返回）
以下代码返回第 K 大元素在原数组中的任意一个合法下标（若有重复值，返回其中一个匹配位置）：
int quickSelectIndex(std::vector<int>& nums, std::vector<int>& indices, int l, int r, int k) {
if (l == r) return indices[l];
int randIdx = l + rand() % (r - l + 1);
std::swap(nums[randIdx], nums[l]);
std::swap(indices[randIdx], indices[l]);
int pivot = nums[l], i = l, j = r;
while (i < j) {
while (i < j && nums[j] >= pivot) j--;
while (i < j && nums[i] <= pivot) i++;
if (i < j) {
std::swap(nums[i], nums[j]);
std::swap(indices[i], indices[j]);
}
}
std::swap(nums[l], nums[i]);
std::swap(indices[l], indices[i]);
if (i == k) return indices[i];
else if (i > k) return quickSelectIndex(nums, indices, l, i - 1, k);
else return quickSelectIndex(nums, indices, i + 1, r, k);
}
<p>// 使用示例：
// std::vector<int> arr = {3,2,1,5,6,4};
// std::vector<int> idx(arr.size());
// std::iota(idx.begin(), idx.end(), 0);
// int origPos = quickSelectIndex(arr, idx, 0, arr.size()-1, arr.size() - k);
注意：quickSelectIndex 返回的是原始下标，但该下标对应元素值就是第 K 大值；分区过程会打乱 arr 和 idx 的顺序，如需保持原数组不变，应传入副本。
最容易被忽略的一点：很多人以为快速选择“一定比排序快”，但当 K 接近 n/2 且数据量很小时（比如 n std::nth_element 内部可能切分多次，而 std::sort 的常数反而更低——实际工程中，小数组建议直接用库函数。
