partial_sort 不是“半吊子排序”：一次被低估的 C++ 性能杠杆

上周帮同事调一个日志分析工具，它要从百万级事件中快速挑出“最耗时的前 100 个请求”。他用 std::sort 全排完再取前 100，单次耗时 380ms。我改了一行：把 sort(v.begin(), v.end()) 换成 partial_sort(v.begin(), v.begin() + 100, v.end())，耗时直接掉到 12ms —— 缩短了 31 倍。

这不是玄学，是 partial_sort 在背后默默建了一棵“迷你堆”，只维护你真正关心的那块数据。

很多人第一次见 partial_sort，下意识觉得它是 sort 的“缩水版”——好像功能打折、性能也打折。其实恰恰相反：当你只需要序列前端（或后端）的有序片段时，partial_sort 是标准库里最务实的“精准打击”工具。

它的签名很直白：

partial_sort(first, middle, last, comp);

意思是：让 [first, middle) 成为整个 [first, last) 中最小（或按 comp 定义的“最小”）的 middle - first 个元素，且内部升序排列；其余元素位置不定，也不保证有序。

关键点来了：它不排序全部，也不只做 top-K 的粗筛——它确保前 K 个不仅是最小的 K 个，还彼此排好序。这点常被忽略，却决定了它和 nth_element 的根本分工。

比如你要生成排行榜首页：既要“前 10 名是谁”，也要“第 1 名 > 第 2 名 > … > 第 10 名”。这时 nth_element 只能保证第 10 名的值正确，前面乱序；而 partial_sort 一步到位——它干的是“选人+排座次”两件事，不是只发工牌。

实际用的时候，三个细节决定效果：

第一，K 值别太小，也别太接近 N
当 K = 1，partial_sort 内部仍走堆逻辑，不如手写一次遍历找最小值来得轻量；当 K > N/2，它渐近复杂度逼近全排序 O(N log N)，此时直接 sort 反而更稳。经验法则是：K < N/4 时优势最明显，尤其 K 在几十到几千量级——这恰好覆盖了绝大多数监控告警、Top-N 推荐、采样分析场景。

第二，自定义比较函数别写错方向
想拿“最大的前 10 个”？别急着翻转容器，直接传 std::greater<>{}：

partial_sort(events.begin(), events.begin() + 10, events.end(), 
             [](const auto& a, const auto& b) { return a.duration > b.duration; });

注意：comp(a,b) 返回 true 表示 a 应该排在 b 前面。这个语义必须和你的业务目标严格对齐，否则前 10 个可能是“最小的 10 个”还浑然不觉。

第三，考虑是否真需要“前 K 有序”
如果只要知道“哪些在 Top-10”，不要求它们之间顺序（比如用于去重或聚合），nth_element + partial_sort 组合更省：先 nth_element 定界，再对前 K 单独 sort。但多数业务代码里，少写一行比省几微秒更值得——partial_sort 本身足够健壮，别过早拆解。

还有个隐形陷阱：迭代器类型。
partial_sort 要求随机访问迭代器（vector、deque、原生数组没问题；list、forward_list 直接编译失败）。有人试过用 list 调用，报错信息晦涩，最后发现是误以为“STL 都支持”。不是所有容器都配得上 partial_sort——它天生为内存连续、支持 O(1) 跳转的数据而生。

另外，它不保证稳定性（相同值的相对顺序可能变）。如果你依赖原始输入顺序（比如日志时间戳相同时要保持先来后到），得自己加索引字段或换稳定版本——但标准库没提供 stable_partial_sort，这时候要么手写堆，要么接受妥协。

回到开头那个日志工具。后来我们发现，真正瓶颈其实在 IO 解析阶段，排序只占 3%。但把 sort 换成 partial_sort 后，CPU 火焰图里那根刺眼的长条消失了，监控曲线也平滑了。性能优化有时不是狂啃大块骨头，而是拧紧一颗松动的螺丝——partial_sort 就是那颗常被漏看的六角螺栓。

它不炫技，不造概念，就老老实实建个 size-K 的最大堆（对升序而言是最大堆，维持前 K 最小），一边扫剩余元素，一边动态替换堆顶。没有魔法，只有清晰的算法意图：我要的不是世界地图，只是你家楼下的便利店清单——而且得按开门早晚排好。

下次看到“取前 N”需求，别条件反射写 sort。停半秒，问自己：我真需要全部有序吗？前 N 个之间要不要顺序？N 相比总量有多大？
答案若是否定的，partial_sort 就在那里，不声不响，等你把它从 <algorithm> 里请出来。