优先使用 std::nth_element，因其是工业级快速选择实现，平均 O(n)，内置 pivot 随机化、小数组优化及重复值鲁棒处理；手写易在边界、pivot 选择和语义映射（如第 K 大需转为索引 n−k）上出错。
为什么 std::nth_element 比手写快排划分更值得优先用
标准库的 std::nth_element 就是 C++ 对快速选择算法的工业级实现，平均 O(n)，最坏 O(n²) 但实际极难触发。它不排序整个数组，只保证第 k 个位置放对了数，左边 ≤ 它、右边 ≥ 它（默认升序），所以找“第 K 大”时要传入 begin + (n - k) 这个迭代器位置。
手写 partition 很容易在边界处理、pivot 选择、循环不变量上出错，尤其当数组含重复值或 k 越界时崩溃或返回错误结果。而 std::nth_element 已经处理了这些细节，还做了 pivot 随机化和小数组插入排序优化。
实操建议：
- 头文件必须包含
<algorithm></algorithm> - 确保
k在有效范围：1 ≤k≤nums.size()，否则行为未定义 - 若需第 K 大，别直接用
nth_element(nums.begin(), nums.begin() + k - 1, nums.end())—— 这是找第 K 小 - 如原数组不能修改，先拷贝一份，
std::nth_element会原地重排
手写快速选择时 pivot 怎么选才不容易退化
选第一个或最后一个元素作 pivot，在已排序或逆序数组上会直接退化成 O(n²)。实践中应避免硬编码 nums[l] 或 nums[r]。
立即学习“C++免费学习笔记（深入）”；
推荐做法是三数取中（median-of-three）或随机化：
- 三数取中：取
nums[l]、nums[(l+r)/2]、nums[r]的中位数，交换到末尾再做 partition - 更简单可靠的是随机化：用
std::uniform_int_distribution生成[l, r]内索引，swap 到r位置 - 不要用
rand() % (r - l + 1)，低比特周期短，分布不均 - partition 后，递归只进一边：若 pivot 索引 == k，直接返回；若 > k，只递归左半；否则递归右半
std::nth_element 和手写版在重复元素多时表现一样吗
不一样。标准库实现通常采用 introselect（introspective selection）：结合快速选择 + 堆选择 + 中位数的中位数，对重复值有更好鲁棒性。而朴素手写 partition 若没处理好相等情况（比如把等于 pivot 的全堆左边或右边），可能导致某侧始终不缩小，死循环或超时。
例如数组全是相同数字，手写代码若 partition 返回的 pivot 位置每次都不等于 k，且左右区间大小没变化，就会无限递归。正确做法是在 partition 中把等于 pivot 的元素均匀分到两侧，或用三路划分（low / mid / high 三段）。
实操注意点：
- 手写三路划分时，
lt指向小于区尾，gt指向大于区头，i扫描中间，遇到等于 pivot 就跳过，避免移动 -
std::nth_element不保证相等元素的相对顺序，也不保证左右两段内部有序 —— 这正是它比std::sort快的原因 - 如果业务要求稳定（相同值的相对位置不变），快速选择本身不满足，得换方案
查第 K 大时，传错迭代器位置导致结果为 0 或越界访问
这是最常踩的坑：std::nth_element 第二个参数是“要定位到第几个位置”的迭代器，不是“要找第几个大”。默认按升序排，所以第 1 大是最大值，位于 end - 1；第 K 大对应升序下标 n - k。
错误写法：nth_element(v.begin(), v.begin() + k, v.end()) → 实际拿到的是第 (k+1) 小（索引从 0 开始）。
正确写法示例：
vector<int> nums = {3,2,1,5,6,4};
int k = 2; // 要第 2 大 → 应是 5
nth_element(nums.begin(), nums.begin() + nums.size() - k, nums.end());
cout << nums[nums.size() - k]; // 输出 5
若 k 是 1-based 输入，别忘了检查 nums.size() - k 是否 >= 0，否则 begin() + negative 是未定义行为。
另外，空容器调用 nth_element 是未定义行为，务必提前判空。
快速选择真正的复杂点不在算法逻辑，而在边界控制、pivot 鲁棒性和语义对齐——尤其是“第 K 大”这个说法和底层升序索引之间的映射，一不留神就差一位或方向反了。
