c++oding="utf-8" ?>
std::nth_element更值得优先使用，因其是工业级快速选择实现，平均o(n)、抗退化强（三数取中、小数组切插入、尾递归优化），而手写易因pivot选择或边界处理不当退化至o(n²)。
为什么 std::nth_element 比手写快排划分更值得优先用
除非你在面试中被明确要求手写 partition，否则直接调标准库函数是更稳妥的选择。std::nth_element 就是 C++ 标准库对快速选择（QuickSelect）的封装，它保证第 k 个位置放好目标元素，左侧 ≤ 它、右侧 ≥ 它，但不保证左右子区间有序。它的平均时间复杂度确实是 O(n)，且常数远小于自己实现——因为 libstdc++ 和 libc++ 都做了多重优化：三数取中选 pivot、小数组切到插入排序、尾递归消除等。
常见错误是误以为它返回第 K 大值的迭代器——其实它按升序排列，所以找第 K 大得传入 begin() + (n - k)（假设 k 从 1 开始计数）：
vector<int> nums = {3, 2, 1, 5, 6, 4};
int k = 2;
nth_element(nums.begin(), nums.begin() + (nums.size() - k), nums.end());
// 此时 nums[nums.size() - k] 就是第 k 大值
</int>
手写快速选择时 pivot 选错会导致退化成 O(n²)
快速选择的核心是 partition 过程，而性能瓶颈几乎全在 pivot 选取策略上。如果每次都选首/尾元素作 pivot，面对已排序或逆序数组，每次划分只能减少一个元素，立刻退化为 O(n²)。
实操建议用以下方式之一避免最坏情况：
- 随机选 pivot：
swap(nums[l], nums[l + rand() % (r - l + 1)])，简单有效，平均性能稳定 - 三数中位数法：取
nums[l]、nums[r]、nums[(l+r)/2]的中位数，交换到右端作为 pivot - 绝对避免固定位置选取，尤其不要在循环里重复用
nums[0]或nums.back()
注意：rand() 在 C++17 后建议换用 std::random_device + std::mt19937，但竞赛或本地测试中 rand() 加 srand(time(0)) 足够。
第 K 大 vs 第 K 小：下标换算别绕晕
快速选择默认按升序语义工作，即 partition 后第 k 个位置（0-indexed）存放的是「第 k+1 小」的数。要找第 K 大，必须做一次坐标映射：
- 若数组大小为
n，第 1 大 → 索引n-1，第 K 大 → 索引n-K（K 从 1 开始） - 如果接口参数
k是 0-indexed（比如 LeetCode 215 题输入是k = 2表示“第 2 大”），那目标索引就是n - k - 1 - 手写递归函数时，建议函数签名明确写成
quickSelect(vector<int>& nums, int left, int right, int target_idx)</int>，其中target_idx是最终要定位的下标，不掺杂“第几大”的业务逻辑
容易踩的坑是混用两种语义：一边说“找第 K 大”，一边在递归调用里传 k-1 却没同步调整区间边界，导致越界或死循环。
partition 实现细节决定是否真的 O(n) 平均
标准 Hoare 分区（双向扫描）比 Lomuto（单向扫描）更高效，尤其对重复元素多的数组。Lomuto 版本在大量相等元素时可能每次只缩小区间 1 个，Hoare 则能跳过连续相等段。
一个健壮的 Hoare partition 应该：
- pivot 选好后立即放到右端（或左端），避免比较时额外判断
- 左右指针严格满足：左指针停在
>= pivot，右指针停在，然后才交换 - 循环结束时，确保
left > right，再把 pivot 放到right位置（若 pivot 原在右端） - 返回值必须是 pivot 最终落点，后续递归才能正确切分
漏掉边界检查（如 while (i 中少写 <code>i ）会导致数组越界；用 <code> 而非 <code> 控制指针移动，可能让相等元素堆积在一侧，破坏均匀划分。
真正影响平均复杂度的，不是算法骨架，而是这些看似琐碎的比较符号和边界处理。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
