快速选择算法能定位第K大值下标而非仅返回值，因其通过partition将数组划分为大于、等于、小于pivot三段，目标位置n−k（升序下标）在pivot落点处即确定；每次比较pos与n−k决定递归方向，最终直接返回下标。
快速选择算法为什么能定位第 K 大值的下标，而不是只返回值？
因为 std::nth_element 或手写 partition 过程本身不改变元素相对顺序以外的结构——它把数组划分为三段：[大于pivot]、[等于pivot]、[小于pivot]（或反之），而目标位置（比如第 K 大对应索引 k-1 在降序排列中）在 partition 后就恰好落在 pivot 最终落点。只要每次 partition 后判断 pivot 下标是否等于目标索引，就能直接返回该位置，无需排序全部。
关键点在于：第 K 大 = 升序数组中索引为 n-k 的元素（0-indexed），所以你要找的是升序下的第 n-k 小值的位置。别硬套“第 K 大”去写降序逻辑，容易搞反边界。
- 输入数组
nums = {3,2,1,5,6,4}，求第 2 大 → 对应升序后索引6-2 = 4，即第 5 个元素（0-indexed 是 4） - partition 返回 pivot 最终下标
pos，若pos == n-k，直接返回pos - 若
pos > n-k，说明目标在左半区；若pos ，则在右半区
手写 partition 函数时最容易错的三个边界细节
用 Lomuto 分区方案（单指针）最简洁，但初学者常在循环条件、交换时机和返回值上出错。下面这段是稳定可用的版本：
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[right];
int i = left;
for (int j = left; j < right; ++j) {
if (nums[j] <= pivot) { // 注意：是 <=，否则相等元素会全挤到右边
swap(nums[i], nums[j]);
++i;
}
}
swap(nums[i], nums[right]);
return i; // 返回的是 pivot 最终下标，不是 i-1
}
- 循环范围必须是
j ，不能是 <code>，否则会越界访问或重复比较 pivot - 判断条件用
，确保等于 pivot 的元素也被归入左侧区域，避免死循环（尤其当大量重复值时） - 最后 swap 后返回
i，不是i-1——因为i此刻正指向 pivot 应在的位置
std::nth_element 能不能直接返回下标？它改的是原数组吗？
不能直接返回下标。std::nth_element 只保证第 n 个位置放好正确元素，其余部分不排序，但它会**实际修改原容器顺序**。如果你需要原始下标（比如原数组中第 K 大值最初在哪），必须提前记录索引映射。
立即学习“C++免费学习笔记（深入）”；
常见错误是这样写：
vector<int> nums = {3,2,1,5,6,4};
nth_element(nums.begin(), nums.begin()+4, nums.end()); // 想找升序第 5 个（即第 2 大）
// 此时 nums[4] 是目标值，但你不知道它原来在哪儿
- 若需原始位置，应先构造
vector<pair>></pair>存{value, original_index} - 然后对 pair 排序或用
nth_element比较first，最后取second -
nth_element平均复杂度是O(n)，但 worst-case 是O(n²)（和手写一样），不过标准库实现通常带随机化 pivot 优化
平均时间复杂度 O(n) 是怎么算出来的？为什么不是每次都要扫完整数组？
因为每轮 partition 后，只递归处理其中一侧子区间。假设每次 pivot 都把数组大致二分，那么总操作量是 n + n/2 + n/4 + ... ≈ 2n，即 O(n)。这不是大 O 的“上限”，而是数学期望意义上的平均。
- 实际性能高度依赖 pivot 选择：固定取末尾易退化（如已排序数组），建议用
rand() % (right-left+1) + left随机选，再 swap 到末尾 - 如果用中位数的中位数（BFPRT 算法），可严格保证
O(n)，但常数极大，工程中几乎不用 - 注意：
O(n)是比较次数，不是内存访问次数；缓存不友好，实测在小数组上可能比sort + []还慢
真正要注意的是：K 接近 1 或 N 时，用 std::max_element 或 std::min_element 反而更快；只有 K 居中且数据量大时，快速选择的优势才明显。
