partial_sort比全排序快，因其只保证前N个最小（或最大）元素有序，采用堆与排序混合策略，时间复杂度为O(M log N)；而全排序为O(M log M)。
partial_sort 为什么比全排序快
partial_sort 不对整个容器排序，只保证前 N 个元素有序且是全局最小（或最大）的 N 个。它底层用的是「堆 + 排序」混合策略：先建大小为 N 的最大堆（求最小 N 个）或最小堆（求最大 N 个），再遍历剩余元素，逐个比较替换堆顶。时间复杂度是 O(M log N)，其中 M 是容器总长度 —— 当 N 时，明显优于 sort 的 O(M log M)。
取前 N 个最大元素的正确写法
默认 partial_sort 求最小 N 个；要取最大 N 个，必须传自定义比较器。常见错误是直接写 greater 却没注意迭代器范围：
- 目标区间必须是前
N个位置：partial_sort(first, first + N, last, greater()) - 如果
N > distance(first, last)，行为未定义 —— 务必先检查N是否越界 - 若容器支持随机访问（如
vector），性能稳定；对list等仅双向迭代器的容器，partial_sort不可用，得换partial_sort_copy或手写堆
和 make\_heap + pop\_heap 对比哪个更快
手动维护堆（如 make_heap + pop_heap）理论上也能取 top N，但实际更慢、更易错：
-
partial_sort内部优化了堆操作与后续排序的衔接，避免重复调整 - 手动方式需循环
N次pop_heap，每次都是O(log M)，总成本O(N log M)，当N接近M时不如partial_sort - 还要额外分配空间存结果，而
partial_sort原地完成 - 示例对比：
vector—— 一行搞定，结果就在开头 10 个位置v = {...}; partial_sort(v.begin(), v.begin()+10, v.end(), greater ());
容易被忽略的性能陷阱
看似简单，但几个细节会悄悄拖慢速度：
立即学习“C++免费学习笔记（深入）”；
- 传入的比较器如果不是无捕获 lambda 或函数指针（比如带引用捕获的 lambda），可能阻止内联，影响堆操作效率
- 对
vector这类特化容器，partial_sort可能编译失败 —— 改用vector或显式转换 - 如果只是想“知道 top N 是哪些”，但不关心它们的顺序，用
nth_element更快（O(M)），哪怕之后再对前 N 个调用sort，也常优于单次partial_sort - 调试时用
std::cout打印中间结果？别在性能敏感路径上做流输出 —— IO 开销远超算法本身
partial_sort 的边界判断和比较器方向最容易出错，尤其在模板泛型代码里混用 less/greater 和自定义类型时。 
