std::partial_sort 比 sort+取前N快，因其仅保证前N个元素有序且为全局最小N个，时间复杂度为O(N log N + (last−first)×log N)，远优于sort的O((last−first) log (last−first))。
std::partial_sort 为什么比 sort + 取前 N 快
因为 std::partial_sort 不会对整个容器排序，它只保证前 N 个元素有序且是全局最小的 N 个，其余部分不保证顺序也不参与完整堆化或快排递归。时间复杂度是 O(N log N + (last - first) × log N)，而先 std::sort 再取前 N 是 O((last - first) log (last - first)) —— 当 N 远小于容器大小时，前者优势明显。
常见错误现象：std::partial_sort(v.begin(), v.begin() + 3, v.end()) 后发现第 4 个元素比第 3 个还小？那说明你没理解“前 N 个是全局最小”这个前提：它只保证 [first, middle) 有序且每个都 ≤ [middle, last) 中任意元素，但 [middle, last) 内部完全无序，不能假设“第 N+1 个就是第 N+1 小”。
- 使用场景：Top-K 查询、排行榜截取、快速找最小/最大 K 个数（不要求剩余数据有序）
- 参数差异：
partial_sort(first, middle, last)中middle是“前 N 个”的结束迭代器，即你要提取 N 个就写v.begin() + N - 如果只需要值、不关心原容器顺序，考虑用
std::nth_element+ 手动收集（更快但不排序前 N）
std::partial_sort 的边界和常见崩溃点
最常踩的坑是迭代器越界 —— 特别是当容器 size v.begin() + N 直接非法。它不会自动截断，也不会抛异常，而是触发未定义行为（可能 crash，也可能看似正常但结果错乱）。
另一个隐形陷阱：对 std::list 或其他仅支持双向迭代器的容器，std::partial_sort 编译失败，因为它要求随机访问迭代器（RandomAccessIterator）。此时得换 std::partial_sort_copy 或改用 std::vector 中转。
立即学习“C++免费学习笔记（深入）”；
- 务必检查：
if (N > static_cast<size_t>(v.size())) N = v.size();</size_t> - 不要对
std::deque轻易用 —— 虽然满足随机访问，但 cache 局部性差，性能可能不如 vector - 自定义类型必须提供可比较的
operator<或传入比较函数对象，否则编译报错invalid operands to binary expression
partial_sort_copy 更安全的替代方案
当你不想修改原容器，或者原容器迭代器不满足随机访问（比如 std::list），std::partial_sort_copy 是更稳妥的选择。它把结果写进另一个已分配好空间的容器，不碰源数据，也不挑迭代器类型（只要源支持输入迭代器、目标支持随机访问即可）。
性能上它多一次拷贝，但避免了原地操作的风险；兼容性上它能处理 std::list、std::set（需注意 set 已有序，用它反而浪费）甚至 C 数组。
- 示例：
std::partial_sort_copy(lst.begin(), lst.end(), out.begin(), out.end());—— 注意out容量至少为 N 或源大小，否则只填满out.end() - 如果只想要前 N 个，记得传
out.begin() + N作为第三参数，否则会尝试填满整个out - 对比
std::copy_n+std::sort：后者代码更直白，但多一次完整拷贝 + 全局排序，纯属画蛇添足
提取前 N 个时，std::nth_element + 手动遍历更轻量
如果你只要前 N 个的值，不要求它们之间有序（比如只统计 Top-10 的 sum 或 max），std::nth_element 是最快选择。它只做一次分区，把第 N 小的元素放到正确位置，左边全是 ≤ 它的，右边全是 ≥ 它的 —— 时间复杂度 O(last - first)。
但注意：它不保证左边 N 个有序，所以后续若要 std::max_element 或打印时按顺序看，还得单独对前 N 排序。很多人误以为 nth_element 就是“partial_sort 的加速版”，其实语义不同。
- 典型误用：
nth_element(v.begin(), v.begin() + N, v.end()); auto top = std::vector(v.begin(), v.begin() + N);—— 此时top里是“最小的 N 个”，但顺序随机 - 正确组合：
nth_element(v.begin(), v.begin() + N, v.end()); sort(v.begin(), v.begin() + N); - 对
std::vector<int>提取前 5 个，nth_element比partial_sort快 30%~50%，N 越小优势越明显
实际用哪个，取决于你到底要什么：要有序的 Top-N 就用 partial_sort；要最快的 Top-N 值集合（不要求顺序）就用 nth_element；要不改原数据、兼容性高就用 partial_sort_copy。三者底层策略不同，不是简单替换关系。
