std::nth_element 是最优解，平均时间复杂度 O(n)，原地修改、无需额外空间，将第 K 小元素置于索引 k-1 处，左右分区但无序；注意 K 从 1 开始而迭代器偏移从 0 开始，需确保 k 有效。
用 std::nth_element 最快且最安全
直接调用 std::nth_element 是 C++ 标准库提供的最优解，平均时间复杂度 O(n)，原地修改、无需额外空间，且不依赖数组是否已排序。
它把第 K 小的元素放到索引 k-1 的位置（0-indexed），左边元素 ≤ 它，右边 ≥ 它——但左右各自无序，所以不能误以为得到了前 K 个有序元素。
常见错误是传错索引：想查第 3 小，却写成 nth_element(..., begin+3)，实际应为 begin+2。K 从 1 开始计数，迭代器偏移从 0 开始。
- 确保
k在有效范围：1 ，否则行为未定义 - 输入必须是可随机访问的容器，如
std::vector或裸数组；std::list不支持 - 若需保持原数组不变，先拷贝一份再操作，因为该函数会重排部分元素
std::vector<int> arr = {7, 10, 4, 3, 20, 15};
int k = 3;
std::nth_element(arr.begin(), arr.begin() + k - 1, arr.end());
// 此时 arr[k-1] 就是第 k 小元素：arr[2] == 7
手写快速选择（QuickSelect）要小心分区逻辑
当不能用 STL（比如嵌入式环境或教学要求），或想控制 pivot 选取策略时，可实现 QuickSelect。它的核心和快排一样，但只递归处理含目标位置的那一侧，因此比完整快排快。
立即学习“C++免费学习笔记（深入）”；
最容易出错的是分区（partition）函数：返回的 pivot 索引必须严格对应“最终落位”，且要保证 left 到 pivot-1 全 ≤ pivot 值，pivot+1 到 right 全 ≥。用 std::swap 而非赋值移动，避免覆盖未读取值。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 最差情况 O(n²)，发生在每次 pivot 极端偏斜（如已排序数组选首/尾作 pivot），建议用三数取中或随机 pivot
- 递归调用时注意边界：若 pivot 索引等于
k，直接返回；若大于k，搜左半区；否则搜右半区（注意右半区起始是pivot+1，不是pivot） - 使用
int类型索引时，确保不会因left + right溢出；推荐写成left + (right - left) / 2
堆方法适合 K 很小或流式场景
当 k 远小于数组长度 n（例如找 Top 5），用最大堆维护当前遇到的最小的 k 个数，时间复杂度 O(n log k)，空间 O(k)。比 nth_element 多开销，但能增量处理数据（比如边读边算）。
别用 std::priority_queue<int> 默认构造——那是最大堆，而我们要保留“最大的那个”作为门槛，所以正好用默认；如果误用 greater<int> 变成最小堆，就完全反了。
- 初始化堆后，对每个新元素：若小于堆顶，弹出堆顶并插入新值；否则跳过
- 遍历完后，堆顶就是第 k 小元素（因为堆里始终是当前最小的 k 个，其中最大的那个即为第 k 小）
- 注意：堆无法在 O(1) 内获取第 k 小的“所有候选”，仅得结果值；也不能回溯原始下标
std::priority_queue<int> max_heap; // 默认最大堆
for (int x : arr) {
if (max_heap.size() < k) {
max_heap.push(x);
} else if (x < max_heap.top()) {
max_heap.pop();
max_heap.push(x);
}
}
// max_heap.top() 即为第 k 小
注意类型与边界：size_t 和有符号比较会静默出错
数组长度常是 size_t，而 k 若声明为 int，做 k > arr.size() 判断时，arr.size() 会被提升为无符号，导致 k 负数时变成极大正数，条件恒真——编译器通常不报警，但运行时崩溃或返回垃圾值。
更隐蔽的问题是：当用指针算术（如 arr + k - 1）时，若 k == 0，k - 1 是极大的正数，越界访问。
- 统一用有符号整型（如
ptrdiff_t或显式int）处理索引，或强制转换static_cast<int>(arr.size()) - 所有涉及
k-1的地方，先断言k >= 1 - 用
std::span（C++20）或封装类管理长度+索引，比裸指针+size_t更安全
实际选哪种方法，取决于你是否允许修改原数组、K 相对于 n 的大小、以及是否需要稳定性能。标准库的 nth_element 在绝大多数工程场景下就是答案——除非你正在调试它内部为什么卡在某个 pivot 上。
