std::nth_element是最稳妥的选择，平均时间复杂度o(n)，原地操作，仅保证第k个位置正确及左右分区有序；找第k大需索引n-k（升序）或配合greater()比较器；priority_queue适用于流式数据，空间o(k)；手写quickselect易出错，须注意pivot随机化与边界处理。
直接用 std::nth_element 是最稳妥的选择
绝大多数情况下，不需要手写堆或快排分区——std::nth_element 就是标准库为你准备的、专为“找第 K 大/小”设计的工具。它平均时间复杂度 O(n)，原地操作，不破坏整个有序性，比先 sort 再取索引快得多，也比自己维护堆更少出错。
注意：它不保证前 K 个元素有序，只保证第 K 个位置放好了目标值，且左边 ≤ 它、右边 ≥ 它（默认升序）。所以找“第 K 大”，实际是找升序排列下的第 n-K 个（0-indexed）。
- 若数组为
vector<int> nums = {3,2,1,5,6,4}</int>，找第 2 大 → 目标位置是nums.size() - 2 = 4（即升序下索引 4） - 调用写法：
nth_element(nums.begin(), nums.begin() + pos, nums.end()) - 想按降序找？可以传比较器：
nth_element(nums.begin(), nums.begin() + k-1, nums.end(), greater<int>())</int>，这时第 K 大就落在k-1位置
priority_queue 适合流式数据或内存受限场景
当数据不能一次性加载进内存（比如从文件/网络持续读入），或者你只需要维护“当前看到的 Top K”，priority_queue 是更自然的选择。用最小堆存 K 个最大元素，每次新数进来，比堆顶大就替换堆顶。
关键细节：
- 声明最小堆：
priority_queue<int vector>, greater<int>></int></int>，别漏掉第三个模板参数 - 初始化后检查堆大小是否达到 K：没满就直接 push；满了就比较
top()和新值，仅当新值更大时pop()再push() - 最终堆顶就是第 K 大——但注意，此时堆里 K 个数无序，只有堆顶有意义
- 空间复杂度稳定为
O(K)，而nth_element是O(1)额外空间
手写快速选择（QuickSelect）容易错在边界和 pivot 选取
如果你在面试中被要求“不依赖 STL 实现”，或想理解底层逻辑，快速选择是核心思路。但它比看上去脆弱：partition 写错一两个符号，left/right 越界、死循环、返回错误索引都很常见。
几个必须检查的点：
- pivot 建议用随机索引（
rand() % (r - l + 1) + l），避免退化成O(n²)（比如已排序数组选首尾作 pivot） - partition 后得到的是 pivot 的最终位置
p，要严格对比p和目标索引target：若p == target直接返回；p > target查左半段；p 查右半段（注意右半段新目标是 <code>target - p - 1） - 递归改迭代可避免栈溢出，但需手动维护区间栈，实操中除非明确要求，否则不值得
别忽略重复元素和 K 越界问题
真实数据常含重复值，比如 [2,2,2,2] 中找第 2 大，答案仍是 2——这没问题。nth_element 和 priority_queue 都能正确处理。但要注意：
- K 必须满足
1 ，否则行为未定义。务必在调用前校验，尤其 K 来自用户输入或计算结果时 - 空数组、单元素数组要单独判断，
nth_element对空范围调用会 UB - 如果题目语义是“去重后第 K 大”，那就得先
set或unordered_set去重，再转回 vector —— 这时复杂度变成O(n log n)，不能再指望nth_element的线性优势
真正麻烦的从来不是算法本身，而是边界条件和需求歧义。写完先跑 [1]、[1,2]、[2,1]、K=1 和 K=n 这几组，比盯着主逻辑更容易暴露问题。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
