快速选择算法能定位第K大值下标，是因为它原地重排使该值落在目标索引（如升序中arr.size()-K），需预存原始下标并连带划分；三路分区可稳定处理重复值，std::nth_element不返回下标，须封装pair实现O(n)平均复杂度。
快速选择算法为什么能定位第 K 大值的下标，而不是只返回值？
因为 std::nth_element 和手写快选都操作原始容器（如 vector），原地重排后，第 K 大对应的位置就固定了——关键不是“求出值”，而是“让该值落到目标索引上”。比如找第 1 大（即最大值），它最终会出现在 arr[0]；找第 K 大，等价于找升序排列中索引为 arr.size() - K 的位置（前提是 K 从 1 开始计数）。
注意：标准库不提供“返回下标”的接口，必须自己记录原始索引。常见做法是把值和原下标打包成 pair<int int></int> 或自定义结构体，再对这个数组做快选。
- 错误做法：直接对值数组调用
nth_element，然后用find搜索结果值——可能有重复值，find返回第一个匹配项，不一定是原始位置 - 正确做法：预处理时保存每个元素的原始下标，排序/划分时连带移动下标，最后取结果位置的 second 字段
- 若只需一个合法位置（而非所有出现位置），这种映射方式足够且稳定
手写快选时 partition 函数怎么写才不崩，尤其处理重复值？
标准 Lomuto 分区（以末尾为 pivot）在大量重复值时退化为 O(n²)，且容易因边界判断出错导致越界或死循环。推荐用三路分区（Dutch National Flag 风格），把数组划分为 < pivot、== pivot、> pivot 三段。
核心逻辑是维护三个指针：lt（小于区右边界）、gt（大于区左边界）、i（当前扫描位）。每次比较后决定交换并移动哪个指针。
立即学习“C++免费学习笔记（深入）”；
- 当
arr[i] < pivot：交换arr[i]和arr[++lt]，i++ - 当
arr[i] > pivot：交换arr[i]和arr[--gt]，i不增（因为换过来的值没检查过） - 当
arr[i] == pivot：i++跳过 - 最终
[lt+1, gt-1]是所有等于 pivot 的区间——如果目标 k 落在这个区间内，直接返回任意下标（如lt+1）即可
std::nth_element 能不能直接用？它返回的是下标吗？
std::nth_element 不返回任何值，也不提供下标信息；它只保证执行后，第 n 个位置（迭代器）上的元素是“排好序后该处应有的值”，且左侧都不大于它、右侧都不小于它（无序）。所以它本身不解决“原始位置在哪”的问题。
但它可以用来加速：先用它把第 K 大的值“拎出来”，再遍历原数组找第一次出现位置——这在无重复值时安全，但有重复时仍不可靠。更稳妥的是封装一层：
vector<pair<int, int>> indexed;
for (int i = 0; i < arr.size(); ++i)
indexed.emplace_back(arr[i], i);
nth_element(indexed.begin(), indexed.begin() + k - 1, indexed.end(),
greater<pair<int, int>>{});
int original_index = indexed[k - 1].second;
这里用 greater<> 实现降序，使 indexed[k-1] 对应第 K 大；k 从 1 开始，符合题意。
平均时间复杂度真的是 O(n) 吗？什么情况下会变慢？
是的，随机化 pivot 下的期望时间复杂度是 O(n)，数学推导基于每次划分至少淘汰常数比例元素。但实际性能受数据分布和 pivot 选取影响极大：
- 最好情况：每次 pivot 正好把数组二分 → T(n) = T(n/2) + O(n) → O(n)
- 最坏情况：每次 pivot 是极值（如已排序数组用末尾作 pivot）→ T(n) = T(n−1) + O(n) → O(n²)
- 实践中加一句
swap(arr[r], arr[rand() % (r - l + 1) + l]);就能规避恶意输入 - 注意：
std::nth_element内部通常用 introselect（快选 + 堆选兜底），最坏 O(n log n)，比纯快选更稳
真正容易被忽略的是：快选不稳定，相同值的相对顺序会变；如果你依赖原始顺序做二级判断（比如相同值时选下标小的），必须在比较函数里加入下标逻辑，不能只比值。
