：从TopK场景理解STL部分排序与堆排序原理)
不知道你有没有遇到过这种需求界面上要展示一份榜单只显示前 10 名剩下的几千名观众根本不会去翻。我最早写这类代码时第一反应永远是std::sort()把整个数组全排一遍再取前 10 个。数据量小的时候倒也没人说什么可等数据从一万涨到一百万sort()那段耗时就开始让人坐不住了。也正是因为这个契机我才认认真真把std::partial_sort()翻出来研究了一遍结果发现它才是这种场景下的“正主”。这篇文章想聊的就是std::partial_sort()以及和它强相关的一家人partial_sort_copy()、nth_element()、stable_sort()。我会先讲清楚它到底解决什么问题再把底层的堆排序原理拆开看最后分享几个我在实际项目里踩过的坑和选型建议。无论你是刚接触 STL 的初学者还是已经写了好几年 C 想优化业务代码的老手这篇内容应该都能给你一点可落地的参考。1. 从排行榜 Top10 开始为什么 std::sort() 不是首选1.1 你真正需要的不是“全部有序”先描述一个非常典型的场景。某个电商活动页面要展示“销量榜 Top10”后台接口一次返回了 50 万条商品记录展示层只需要取销量最高的 10 条而且这 10 条内部要有明确的先后顺序从第 1 名排到第 10 名。至于第 11 名到第 50 万名它们是按什么顺序排列的没有任何人在意。如果按我最初的习惯直接std::sort()一把梭那就意味着我要把 50 万条记录全部排成严格递增序列。但最终页面只用到前 10 个元素剩余 49 万 9990 个元素的顺序工作全是白做。更麻烦的是很多排序操作会原地修改数据而原始数据可能是从缓存里读出来、后面还有别的业务要用原顺序的这时sort()带来的副作用还得靠额外拷贝去抵消。举一个更生活化的例子老师要公布全班前三名但其实根本没必要把全班 50 个人的成绩都排一遍名次。只需要“找出分数最高的三个人并排出第 1、第 2、第 3”其余 47 个人谁高谁低没人关心。std::partial_sort()就是帮老师做这件事的算法。1.2 sort() 的浪费到底有多大理论上std::sort()的时间复杂度是 O(N log N)。std::partial_sort()的时间复杂度是 O(N log K)其中 K 是你要保留并排序的前多少个元素。这里 N 是数据总量K 是“真正关心的元素个数”。当 N 1,000,000、K 10 时std::sort()的比较次数大约在 N log N 量级也就是 100 万 × 20 ≈ 2000 万次左右std::partial_sort()的比较次数大约在 N log K 量级也就是 100 万 × log2(10) ≈ 430 万次左右。比较次数差了将近 5 倍而且这种差异会随着 N 变大而越来越明显。当然真实工程的耗时并不是只由比较次数决定后面我会专门聊实测量级和缓存、元素大小这些隐藏因素。但至少在复杂度这个维度上结论已经很清晰只排前 K 个元素的场景partial_sort()比sort()更对路。1.3 partial_sort() 一句话定位std::partial_sort()的语义可以概括成一句话执行完partial_sort(first, middle, last)之后区间[first, middle)内的元素是全局最小的 K 个K middle - first并且它们已经按升序排好区间[middle, last)内的元素不保证任何顺序甚至可能很乱。这里要注意“全局最小”这四个字它是理解这个算法的关键。partial_sort()不是简单地把数组前 K 个元素挑出来排个序而是会遍历整个区间把全区间里真正最小的 K 个元素挑选出来放到前面并排好。这个区别很大我在后文讲原理和避坑时会反复提到。2. 函数签名与调用姿势不只是传三个迭代器2.1 签名与边界条件std::partial_sort()在algorithm头文件中最常用的两个重载是templateclass RandomIt void partial_sort(RandomIt first, RandomIt middle, RandomIt last); templateclass RandomIt, class Compare void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp);注意这里的迭代器类型必须是随机访问迭代器也就是说它适用于std::vector、std::array、std::deque不能用std::list因为list只有双向迭代器不支持随机跳转。三个迭代器参数的含义比较特殊很多新手第一次接触时容易懵。middle不是一个结束标记而是“排序与不排序的分界线”。执行后[first, middle)是排序完成的最小 K 个元素[middle, last)不保证顺序。边界条件也要心里有数如果middle first那么什么都不用排算法直接返回如果middle last那就相当于对整个区间做一次完整排序只是底层实现走的是堆排序路线而不是std::sort()的内省排序路线。2.2 默认升序的用法示例先写一个最简单、可以直接编译运行的例子#include algorithm #include iostream #include vector int main() { std::vectorint v{12, 5, 9, 4, 1, 7, 8, 2, 3, 11, 10, 6}; // 只对前 4 个位置做“全局最小”的排序 std::partial_sort(v.begin(), v.begin() 4, v.end()); for (int x : v) { std::cout x ; } std::cout \n; }一种可能的输出如下1 2 3 4 12 7 8 9 5 11 10 6注意输出里前 4 个元素是1 2 3 4它们是整个序列中最小的 4 个并且升序。而后面的12 7 8 9 5 11 10 6是乱序的标准只保证它们“都不是前 4 小”不保证它们彼此之间的顺序。不同的标准库实现甚至可能得到不同的后半段序列不要把后半段的顺序写入业务逻辑。2.3 自定义比较器如何取最大的 K 个默认版本是升序所以它挑选的是“最小 K 个”。如果需求是“排行榜取最大的 10 个”那就需要提供自定义比较器通常直接传std::greaterint()#include algorithm #include functional #include iostream #include vector int main() { std::vectorint scores{78, 92, 45, 88, 99, 63, 71, 100, 87, 95, 58, 82}; const int topK 3; std::partial_sort(scores.begin(), scores.begin() topK, scores.end(), std::greaterint()); for (int i 0; i topK; i) { std::cout scores[i] ; // 输出最大的 3 个且降序 } std::cout \n; }比较器的语义可以这样理解comp(a, b)返回true表示a应该排在b前面。默认std::lessint()是小的在前所以得到升序改成std::greaterint()后大的在前于是前面 K 个位置就变成了“全局最大 K 个且降序”。如果你希望最大的 K 个以升序展示可以先取出来再手动reverse前三项或者用partial_sort_copy()输出到新数组后再局部反转。这里没有标准库的直接一键方案通常业务里怎么展示是另一层的问题。2.4 partial_sort_copy不修改原始数据std::partial_sort_copy()是partial_sort()的“不破坏原数据”版本它把排序结果复制到另一个容器中遍历的是输入区间写入的是输出区间templateclass InputIt, class RandomIt RandomIt partial_sort_copy(InputIt first, InputIt last, RandomIt d_first, RandomIt d_last);举个实际例子一个函数从配置中心拿到几千条待展示的公告记录希望在展示前挑出阅读量最高的 5 条但原数组后续还要按其他维度处理不能被移动和修改。这时可以直接用partial_sort_copy()#include algorithm #include iostream #include vector struct Item { int id; int views; }; int main() { std::vectorItem items{{1, 100}, {2, 999}, {3, 50}, {4, 300}, {5, 700}, {6, 800}}; std::vectorItem top(3); std::partial_sort_copy(items.begin(), items.end(), top.begin(), top.end(), [](const Item a, const Item b) { return a.views b.views; }); for (const auto it : top) { std::cout it.id : it.views ; } std::cout \n; // 输出类似2:999 6:800 5:700 }输出区间不需要和输入区间一样大算法只会复制min(输入长度, 输出长度)个元素。如果输出容量比输入小那它相当于“从输入里筛出最好的 M 个并升序/降序排好”如果输出容量比输入还大那它就相当于对输入做一个完整排序并拷贝到输出区剩余输出位置不会被写入。返回的迭代器指向输出区间里“已填充内容”的末尾后续代码可以通过这个返回值判断到底写了多少个元素。3. 源码级原理拆解它就是一辆踩了半脚刹车的堆排序3.1 常见实现思路虽然 C 标准没有规定库作者必须怎么实现partial_sort()但主流实现基本都走同一条路最大堆。以默认升序版本为例大致步骤是对[first, middle)这个长度为 K 的前缀区间构建一个最大堆。注意最大堆意味着堆顶元素是这一小段里最大的一个。从middle开始遍历[middle, last)中的每一个元素。如果当前元素比堆顶元素还要小说明当前元素更有资格进入前 K 小于是把堆顶元素“踢出局”把当前元素放进堆里并重新调整堆的结构。等整个区间都遍历完[first, middle)里留下的就是全局最小的 K 个元素但它们还处在最大堆的形态堆顶最大不是有序的。最后对[first, middle)做一次sort_heap()把堆形态变成严格升序排列。如果使用自定义比较器比如std::greater整个规则会对称地变成“最小堆筛掉小元素、保留大元素”核心思路一模一样。3.2 为什么最大堆能筛选出最小 K 个我当年看源码时最困惑的点就是这个我们要保留最小元素为什么构建的是一个“最大堆”其实逻辑非常巧妙。可以把最大堆想象成一个只装了 K 个球的桶但桶的开口在上方而且开口处永远躺着“桶内最大的那颗球”。现在从外面一个个往桶里送球如果新球比桶口那颗球小说明桶口那颗球没有资格留在“最小 K”里把它丢掉把新球放进去如果新球比桶口那颗球大或相等说明新球更不可能成为全局最小那一批直接忽略。这样一轮扫下来桶里剩下的必然就是全局最小的 K 个球。因为任何被丢掉的大球都输给了当时放进桶里的一个小球而那个小球之后可能又被更小的球淘汰最终桶里只会剩下“打遍全场的强者”也就是最小的 K 个。至于为什么要用堆而不是数组是因为每次替换后只需要 O(log K) 的时间就能重新找出“桶内最大”的那颗球如果用普通数组找最大值每次都要 O(K)整体复杂度就会退化成 O(NK)得不偿失。3.3 复杂度的完整推演把步骤细化到复杂度层面对 K 个元素建堆时间复杂度 O(K)遍历剩余 N - K 个元素最坏情况下每个元素都要替换堆顶并调整堆每次调整是 O(log K)所以这一步是 O((N - K) log K)最后对 K 个元素执行堆排序sort_heap()时间复杂度 O(K log K)。把三者加起来忽略低阶项最终是 O(N log K)。因为 K 通常远小于 N这个复杂度比std::sort()的 O(N log N) 漂亮得多。而且它的空间复杂度是 O(1)全程原地操作不需要额外开大数组。这里有一个需要注意的边界当 K 非常接近 N 时复杂度退化成 O(N log N)此时partial_sort()的理论优势消失。而且堆排序的常数通常比内省排序大所以 K 接近 N 时直接std::sort()反而更快。这个判断我后面单独讲。3.4 不稳定的根源std::partial_sort()不保证稳定性。所谓不稳定指的是如果两个元素比较结果相等它们的相对先后顺序在排序后可能发生改变。原因从实现上就能看出来堆的构建和调整过程中有大量的交换操作而且这个算法本质是“先筛选再排序”不是一个稳定选择排序的思路。比如原始序列里有两个分数相同的记录在堆调整的过程中它们的相对顺序完全可能被反转。如果业务上有“分数相同谁先录入谁排前面”这类需求partial_sort()不是你的选择。要么改用stable_sort()全量排序后截取要么在比较器里加一个序号字段做次级排序键例如比较pairscore, id强制让比较结果不完全相等从而把“稳定性”变成“确定性”。4. 选型对比sort、nth_element、stable_sort 和 partial_sort 怎么分工4.1 一张表看各算法的保证很多人都知道std::sort()和std::partial_sort()但遇到具体需求时还是会搞混。我先用一张表把这几个常用算法拉齐算法前 K 个是否有序后半段是否有序是否稳定时间复杂度sort()全部有序全部有序不保证稳定O(N log N)stable_sort()全部有序全部有序稳定O(N log N)partial_sort()前 K 个有序无序不保证稳定O(N log K)partial_sort_copy()输出区间有序不修改原区间不保证稳定O(N log M)M 为输出区间长度nth_element()只保证第 K 个在最终位置左侧 它右侧 它内部无序不保证稳定平均 O(N)这张表的价值在于几个算法都长得很像但它们对“结果”的承诺级别完全不同。排序承诺越强代价越高。你要多少就付多少。4.2 什么时候 nth_element 更好std::nth_element()是一个非常容易被低估的算法。执行完nth_element(first, nth, last)后只有第nth个元素处于“如果把整个区间排序它应该待的位置”它左边的所有元素都不大于它右边的所有元素都不小于它但两边内部都无序。这个特性决定了两类场景它比partial_sort()更合适第一类是只要中位数、分位数这类“单点值”的场景。比如统计一堆请求耗时的 P95 阈值我只需要知道第 95% 位置的值是多少不关心这个值前后长什么样。用nth_element()一次搞定平均 O(N)比partial_sort()的 O(N log K) 更快。第二类是“我只要 TopK 的集合但集合内部顺序完全不重要”的场景。比如从一批用户里筛出积分最高的 1000 人做运营活动活动入口展示时再随机洗牌那这 1000 人的内部顺序没有意义。这时nth_element()可以以更低的成本分离出“前 1000”和“其余部分”。如果你发现你的业务代码里用了partial_sort()但取出的 K 个元素其实只是被遍历、没有按序展示那大概率换成nth_element()更划算。4.3 什么时候直接 sort 反而更好工程上有个很反直觉的点partial_sort()不总是比sort()快。当 K 接近 N 的时候O(N log K) 和 O(N log N) 几乎没有差别而sort()实现的内省排序在工程常数上往往优于堆排序路线所以此时sort()可能更快代码也更简单。我自己的经验阈值是如果 K N / 2我会直接std::sort()全排一遍然后截取前 K 个。举一个具体例子假设你有 10000 条数据需求是取前 6000 条展示后面 4000 条都是辅助信息。此时用partial_sort()复杂度大约 10000 × log2(6000) ≈ 13 万次比较用sort()复杂度大约 10000 × log2(10000) ≈ 13.3 万次比较。两者几乎持平但sort()的常规直插/快排路径对缓存更友好实测往往不落下风。与其写一个带middle的三迭代器调用再解释给同事听不如一行sort()来得直白。4.4 容器适配list 怎么办std::list只有双向迭代器不能使用partial_sort()也无法使用std::sort()的迭代器版本。list自带成员函数list.sort()但那是全量归并排序并没有提供“只排前 K 个”的现成接口。如果业务确实要对list做局部排序我常用的迂回方案是把元素转移到std::vector在vector上做partial_sort()再把排好序的前 K 个拷回list或另建一个结构。虽然多了一次拷贝开销但胜在逻辑清晰、测试方便。另一种更贴合工程的做法是直接改变数据组织方式既然要做部分排序说明数据本身应该是连续内存更合适list不是局部排序的好载体该换容器时就换。5. 实测数据与性能直觉百万数据里挑 Top205.1 自己动手测一套可复用的计时骨架理论讲得再多不如自己跑一次。下面这段代码可以在你的机器上验证不同算法的量级差异。注意一定要用原始数据的拷贝去分别测试因为sort()、partial_sort()、nth_element()都会修改容器连续跑会让上一次的结果污染下一次的输入#include algorithm #include chrono #include iostream #include random #include vector template typename Func double run_ms(Func f) { auto t0 std::chrono::steady_clock::now(); f(); auto t1 std::chrono::steady_clock::now(); return std::chrono::durationdouble, std::milli(t1 - t0).count(); } int main() { const int N 1000000; const int K 20; std::vectorint data(N); std::mt19937 rng(12345); std::uniform_int_distributionint dist(0, 1000000); for (int x : data) { x dist(rng); } { std::vectorint tmp data; std::cout sort(): run_ms([] { std::sort(tmp.begin(), tmp.end()); }) ms\n; } { std::vectorint tmp data; std::cout partial_sort(): run_ms([] { std::partial_sort(tmp.begin(), tmp.begin() K, tmp.end()); }) ms\n; } { std::vectorint tmp data; std::cout nth_element(): run_ms([] { std::nth_element(tmp.begin(), tmp.begin() K, tmp.end()); }) ms\n; } }这段代码的核心逻辑是先准备好一份百万级随机整数然后复制三份分别调用三个算法并统计耗时。如果你把K从 20 改成 200、2000、20000还能看出partial_sort()的耗时随 K 增长的趋势。5.2 我实际跑过的量级参考我在自己的开发机上用随机int测试量级大致是百万数据全量sort()耗时大约百毫秒级partial_sort()取前 20 个明显比全量sort()快通常能快出数倍nth_element()取前 20 个又比partial_sort()再快一截。这只是一个非常粗糙的量级参考不同编译器、不同 CPU、不同标准库实现数字可能差出两倍到三倍所以我不建议你拿着某个具体数字去写技术方案自己动手跑一遍才是正道。更有参考价值的其实是两个趋势第一个趋势是K 越小partial_sort()相对sort()的优势越大。K 从 10 涨到 1000耗时曲线的上升非常平缓而如果 K 涨到 50 万它的耗时就会向sort()靠拢最终反超。第二个趋势是元素本身的移动成本对结果影响很大。上面测试用的是int拷贝成本极小。如果换成std::string或者带有复杂资源的结构体内存搬运的开销会显著放大排序差异。此时partial_sort()因为只对 K 个候选者反复做堆调整元素移动次数少相对优势会比int测试时更加明显。5.3 理论之外的三个隐藏变量只看复杂度很容易得出“partial_sort 一定快”的错误结论实际工程里还有三个隐藏变量第一个是缓存局部性。std::sort()在接近排序完成时会退化成插入排序对连续内存的访问非常友好而partial_sort()的堆调整是跳着访问数组的缓存命中率不如快速排序的路线。所以当 K 相对大时堆的常数劣势会抵消复杂度优势。第二个是元素体积。partial_sort()的空间优势体现在它不需要把整个序列搬进另一个容器但它内部仍会频繁交换元素。如果元素是大对象最好先把下标或指针抽出来做成一个索引数组对索引做部分排序再按排序结果去访问原始对象。这个技巧不专属partial_sort()但在处理 TopK 问题时尤其有用。第三个是数据来源。如果数据本身在数据库或远程接口里partial_sort()处理的是“已经全部在内存里”之后的部分。此时真正的耗时大头往往在数据组装和网络传输排序算法怎么选对整体体验的影响可能不到百分之一。先剖析瓶颈再去优化排序才是工程上正确的顺序。6. 实战避坑记录这些细节能让你少上一次当6.1 比较器必须严格弱序别在 sort 系算法里用 所有标准库排序算法要求比较器满足严格弱序strict weak ordering。简单理解就是对于任意元素 acomp(a, a)必须返回false如果comp(a, b)为真且comp(b, c)为真那么comp(a, c)必须为真。新手最容易犯的错是自定义比较器时写成return a.score b.score;。这个写法违反了“对相同元素必须返回 false”的规则可能导致排序行为未定义轻则结果不符合预期重则越界崩溃。正确的做法是写成return a.score b.score;相等的情况交给算法自己去处理。如果你需要“分数相等时id 小的排前面”那就把比较器写成if (a.score ! b.score) return a.score b.score; // 分数高的在前 return a.id b.id; // 分数相同时 id 小的在前这样任何两个不同元素都能分出先后比较器也满足严格弱序。6.2 partial_sort_copy 的“截断”不是截原数组前 M 个这个坑我见过不止一次。很多人看到partial_sort_copy()的输出区间小于输入区间就下意识以为是“取输入区间的前 M 个元素排好序放到输出里”。事实完全不是这样它取的是整个输入区间的“全局前 M 小/大元素”。举个例子输入是{9, 2, 8, 1, 7, 3}输出容量为 3。正确结果是输出{1, 2, 3}因为这是全区间最小的 3 个而不是{1, 8, 9}也不是{2, 8, 9}这种“取输入前三个再排序”的结果。这个区别影响很大。如果你在使用partial_sort_copy()时自以为它只处理前几个元素那么在大数据量下性能预期和业务逻辑都会出错。正确理解是它会完整遍历输入区间只是把有序结果截断到输出容量。这样反而让它很适合同步筛选数据流即使输入有上百万条只要输出数组开了很小的口子它就能在只读模式下挑出最值得保留的那批。6.3 稳定性问题相等元素的“伪随机”partial_sort()是不稳定排序这一点在官方文档里有明确说明。但实际开发中很少有人会为这个特性主动做测试直到某天运营反馈“排行榜里两个相同分数的用户刷新后前后顺序变了”这时候才想起来问为什么我用的是partial_sort()结果看起来像随机遇到这种问题简单把算法换成stable_sort()不一定划算因为你可能只是需要“分数相同就按注册时间排”。更好的做法是在比较器里引入并列次序把复合键比较写好。如果不想改比较器也可以用std::stable_sort()全排后截取但这是用更高复杂度换稳定性数据量大时要谨慎。6.4 从 C17 到 C20执行策略与 ranges 版本C17 开始partial_sort()增加了带执行策略的重载例如std::partial_sort(std::execution::par, first, middle, last);并行版本可以利用多核加速大数据量的排序但线程调度也有开销。小数据量比如几万元素开并行往往比串行更慢。我的建议是只有当数据量达到千万级、且 K 也较大时并行partial_sort()才值得尝试否则默认用串行版本代码也更好读。C20 还提供了std::ranges::partial_sort()支持直接传入范围对象写法更现代。如果你所在项目已经启用了 C20可以优先考虑 ranges 版本它和传统版本的核心语义完全一致只是参数形式更友好。6.5 动态数据流场景别反复调用 partial_sort最后一个工程经验如果数据不是“一次性全量到了”再做局部排序而是不断有新数据插入那每次插入都调用一次partial_sort()是非常低效的做法。每次调用都是 O(N log K)数据量大时很难看。这种场景应该自己维护一个固定容量 K 的std::priority_queue或者自己写一个 K 容量的小顶堆。新元素进来时只和堆顶比较决定进不进堆每次维护成本只有 O(log K)。partial_sort()更适合“已知完整容器只需要取一次前 K”的批量场景。两者互补并不冲突。实际项目里我会先问自己三个问题是全量排序还是只要前 K 个前 K 个内部是否需要有序原数据还能不能动问完之后选哪个算法基本就有答案了。partial_sort()是我这几年用得最频繁的排序算法之一因为它解决的问题足够具体复杂度上又能清晰看到“少排序一部分”带来的收益。最后再分享一个野路子如果你拿不准某个场景到底该用partial_sort()还是nth_element()就拷贝两份数据各跑一次用chrono计时看结果。排序这种代码用一小段测试定胜负比对着文档猜半天高效得多。方法论这东西最终还是落到“自己跑一遍、自己看数据”上最可靠。 
长河君 · 2026/10/17 5:01:11 · 阅读 1.2k std::partial_sort()：从TopK场景理解STL部分排序与堆排序原理
不知道你有没有遇到过这种需求界面上要展示一份榜单只显示前 10 名剩下的几千名观众根本不会去翻。我最早写这类代码时第一反应永远是std::sort()把整个数组全排一遍再取前 10 个。数据量小的时候倒也没人说什么可等数据从一万涨到一百万sort()那段耗时就开始让人坐不住了。也正是因为这个契机我才认认真真把std::partial_sort()翻出来研究了一遍结果发现它才是这种场景下的“正主”。这篇文章想聊的就是std::partial_sort()以及和它强相关的一家人partial_sort_copy()、nth_element()、stable_sort()。我会先讲清楚它到底解决什么问题再把底层的堆排序原理拆开看最后分享几个我在实际项目里踩过的坑和选型建议。无论你是刚接触 STL 的初学者还是已经写了好几年 C 想优化业务代码的老手这篇内容应该都能给你一点可落地的参考。1. 从排行榜 Top10 开始为什么 std::sort() 不是首选1.1 你真正需要的不是“全部有序”先描述一个非常典型的场景。某个电商活动页面要展示“销量榜 Top10”后台接口一次返回了 50 万条商品记录展示层只需要取销量最高的 10 条而且这 10 条内部要有明确的先后顺序从第 1 名排到第 10 名。至于第 11 名到第 50 万名它们是按什么顺序排列的没有任何人在意。如果按我最初的习惯直接std::sort()一把梭那就意味着我要把 50 万条记录全部排成严格递增序列。但最终页面只用到前 10 个元素剩余 49 万 9990 个元素的顺序工作全是白做。更麻烦的是很多排序操作会原地修改数据而原始数据可能是从缓存里读出来、后面还有别的业务要用原顺序的这时sort()带来的副作用还得靠额外拷贝去抵消。举一个更生活化的例子老师要公布全班前三名但其实根本没必要把全班 50 个人的成绩都排一遍名次。只需要“找出分数最高的三个人并排出第 1、第 2、第 3”其余 47 个人谁高谁低没人关心。std::partial_sort()就是帮老师做这件事的算法。1.2 sort() 的浪费到底有多大理论上std::sort()的时间复杂度是 O(N log N)。std::partial_sort()的时间复杂度是 O(N log K)其中 K 是你要保留并排序的前多少个元素。这里 N 是数据总量K 是“真正关心的元素个数”。当 N 1,000,000、K 10 时std::sort()的比较次数大约在 N log N 量级也就是 100 万 × 20 ≈ 2000 万次左右std::partial_sort()的比较次数大约在 N log K 量级也就是 100 万 × log2(10) ≈ 430 万次左右。比较次数差了将近 5 倍而且这种差异会随着 N 变大而越来越明显。当然真实工程的耗时并不是只由比较次数决定后面我会专门聊实测量级和缓存、元素大小这些隐藏因素。但至少在复杂度这个维度上结论已经很清晰只排前 K 个元素的场景partial_sort()比sort()更对路。1.3 partial_sort() 一句话定位std::partial_sort()的语义可以概括成一句话执行完partial_sort(first, middle, last)之后区间[first, middle)内的元素是全局最小的 K 个K middle - first并且它们已经按升序排好区间[middle, last)内的元素不保证任何顺序甚至可能很乱。这里要注意“全局最小”这四个字它是理解这个算法的关键。partial_sort()不是简单地把数组前 K 个元素挑出来排个序而是会遍历整个区间把全区间里真正最小的 K 个元素挑选出来放到前面并排好。这个区别很大我在后文讲原理和避坑时会反复提到。2. 函数签名与调用姿势不只是传三个迭代器2.1 签名与边界条件std::partial_sort()在algorithm头文件中最常用的两个重载是templateclass RandomIt void partial_sort(RandomIt first, RandomIt middle, RandomIt last); templateclass RandomIt, class Compare void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp);注意这里的迭代器类型必须是随机访问迭代器也就是说它适用于std::vector、std::array、std::deque不能用std::list因为list只有双向迭代器不支持随机跳转。三个迭代器参数的含义比较特殊很多新手第一次接触时容易懵。middle不是一个结束标记而是“排序与不排序的分界线”。执行后[first, middle)是排序完成的最小 K 个元素[middle, last)不保证顺序。边界条件也要心里有数如果middle first那么什么都不用排算法直接返回如果middle last那就相当于对整个区间做一次完整排序只是底层实现走的是堆排序路线而不是std::sort()的内省排序路线。2.2 默认升序的用法示例先写一个最简单、可以直接编译运行的例子#include algorithm #include iostream #include vector int main() { std::vectorint v{12, 5, 9, 4, 1, 7, 8, 2, 3, 11, 10, 6}; // 只对前 4 个位置做“全局最小”的排序 std::partial_sort(v.begin(), v.begin() 4, v.end()); for (int x : v) { std::cout x ; } std::cout \n; }一种可能的输出如下1 2 3 4 12 7 8 9 5 11 10 6注意输出里前 4 个元素是1 2 3 4它们是整个序列中最小的 4 个并且升序。而后面的12 7 8 9 5 11 10 6是乱序的标准只保证它们“都不是前 4 小”不保证它们彼此之间的顺序。不同的标准库实现甚至可能得到不同的后半段序列不要把后半段的顺序写入业务逻辑。2.3 自定义比较器如何取最大的 K 个默认版本是升序所以它挑选的是“最小 K 个”。如果需求是“排行榜取最大的 10 个”那就需要提供自定义比较器通常直接传std::greaterint()#include algorithm #include functional #include iostream #include vector int main() { std::vectorint scores{78, 92, 45, 88, 99, 63, 71, 100, 87, 95, 58, 82}; const int topK 3; std::partial_sort(scores.begin(), scores.begin() topK, scores.end(), std::greaterint()); for (int i 0; i topK; i) { std::cout scores[i] ; // 输出最大的 3 个且降序 } std::cout \n; }比较器的语义可以这样理解comp(a, b)返回true表示a应该排在b前面。默认std::lessint()是小的在前所以得到升序改成std::greaterint()后大的在前于是前面 K 个位置就变成了“全局最大 K 个且降序”。如果你希望最大的 K 个以升序展示可以先取出来再手动reverse前三项或者用partial_sort_copy()输出到新数组后再局部反转。这里没有标准库的直接一键方案通常业务里怎么展示是另一层的问题。2.4 partial_sort_copy不修改原始数据std::partial_sort_copy()是partial_sort()的“不破坏原数据”版本它把排序结果复制到另一个容器中遍历的是输入区间写入的是输出区间templateclass InputIt, class RandomIt RandomIt partial_sort_copy(InputIt first, InputIt last, RandomIt d_first, RandomIt d_last);举个实际例子一个函数从配置中心拿到几千条待展示的公告记录希望在展示前挑出阅读量最高的 5 条但原数组后续还要按其他维度处理不能被移动和修改。这时可以直接用partial_sort_copy()#include algorithm #include iostream #include vector struct Item { int id; int views; }; int main() { std::vectorItem items{{1, 100}, {2, 999}, {3, 50}, {4, 300}, {5, 700}, {6, 800}}; std::vectorItem top(3); std::partial_sort_copy(items.begin(), items.end(), top.begin(), top.end(), [](const Item a, const Item b) { return a.views b.views; }); for (const auto it : top) { std::cout it.id : it.views ; } std::cout \n; // 输出类似2:999 6:800 5:700 }输出区间不需要和输入区间一样大算法只会复制min(输入长度, 输出长度)个元素。如果输出容量比输入小那它相当于“从输入里筛出最好的 M 个并升序/降序排好”如果输出容量比输入还大那它就相当于对输入做一个完整排序并拷贝到输出区剩余输出位置不会被写入。返回的迭代器指向输出区间里“已填充内容”的末尾后续代码可以通过这个返回值判断到底写了多少个元素。3. 源码级原理拆解它就是一辆踩了半脚刹车的堆排序3.1 常见实现思路虽然 C 标准没有规定库作者必须怎么实现partial_sort()但主流实现基本都走同一条路最大堆。以默认升序版本为例大致步骤是对[first, middle)这个长度为 K 的前缀区间构建一个最大堆。注意最大堆意味着堆顶元素是这一小段里最大的一个。从middle开始遍历[middle, last)中的每一个元素。如果当前元素比堆顶元素还要小说明当前元素更有资格进入前 K 小于是把堆顶元素“踢出局”把当前元素放进堆里并重新调整堆的结构。等整个区间都遍历完[first, middle)里留下的就是全局最小的 K 个元素但它们还处在最大堆的形态堆顶最大不是有序的。最后对[first, middle)做一次sort_heap()把堆形态变成严格升序排列。如果使用自定义比较器比如std::greater整个规则会对称地变成“最小堆筛掉小元素、保留大元素”核心思路一模一样。3.2 为什么最大堆能筛选出最小 K 个我当年看源码时最困惑的点就是这个我们要保留最小元素为什么构建的是一个“最大堆”其实逻辑非常巧妙。可以把最大堆想象成一个只装了 K 个球的桶但桶的开口在上方而且开口处永远躺着“桶内最大的那颗球”。现在从外面一个个往桶里送球如果新球比桶口那颗球小说明桶口那颗球没有资格留在“最小 K”里把它丢掉把新球放进去如果新球比桶口那颗球大或相等说明新球更不可能成为全局最小那一批直接忽略。这样一轮扫下来桶里剩下的必然就是全局最小的 K 个球。因为任何被丢掉的大球都输给了当时放进桶里的一个小球而那个小球之后可能又被更小的球淘汰最终桶里只会剩下“打遍全场的强者”也就是最小的 K 个。至于为什么要用堆而不是数组是因为每次替换后只需要 O(log K) 的时间就能重新找出“桶内最大”的那颗球如果用普通数组找最大值每次都要 O(K)整体复杂度就会退化成 O(NK)得不偿失。3.3 复杂度的完整推演把步骤细化到复杂度层面对 K 个元素建堆时间复杂度 O(K)遍历剩余 N - K 个元素最坏情况下每个元素都要替换堆顶并调整堆每次调整是 O(log K)所以这一步是 O((N - K) log K)最后对 K 个元素执行堆排序sort_heap()时间复杂度 O(K log K)。把三者加起来忽略低阶项最终是 O(N log K)。因为 K 通常远小于 N这个复杂度比std::sort()的 O(N log N) 漂亮得多。而且它的空间复杂度是 O(1)全程原地操作不需要额外开大数组。这里有一个需要注意的边界当 K 非常接近 N 时复杂度退化成 O(N log N)此时partial_sort()的理论优势消失。而且堆排序的常数通常比内省排序大所以 K 接近 N 时直接std::sort()反而更快。这个判断我后面单独讲。3.4 不稳定的根源std::partial_sort()不保证稳定性。所谓不稳定指的是如果两个元素比较结果相等它们的相对先后顺序在排序后可能发生改变。原因从实现上就能看出来堆的构建和调整过程中有大量的交换操作而且这个算法本质是“先筛选再排序”不是一个稳定选择排序的思路。比如原始序列里有两个分数相同的记录在堆调整的过程中它们的相对顺序完全可能被反转。如果业务上有“分数相同谁先录入谁排前面”这类需求partial_sort()不是你的选择。要么改用stable_sort()全量排序后截取要么在比较器里加一个序号字段做次级排序键例如比较pairscore, id强制让比较结果不完全相等从而把“稳定性”变成“确定性”。4. 选型对比sort、nth_element、stable_sort 和 partial_sort 怎么分工4.1 一张表看各算法的保证很多人都知道std::sort()和std::partial_sort()但遇到具体需求时还是会搞混。我先用一张表把这几个常用算法拉齐算法前 K 个是否有序后半段是否有序是否稳定时间复杂度sort()全部有序全部有序不保证稳定O(N log N)stable_sort()全部有序全部有序稳定O(N log N)partial_sort()前 K 个有序无序不保证稳定O(N log K)partial_sort_copy()输出区间有序不修改原区间不保证稳定O(N log M)M 为输出区间长度nth_element()只保证第 K 个在最终位置左侧 它右侧 它内部无序不保证稳定平均 O(N)这张表的价值在于几个算法都长得很像但它们对“结果”的承诺级别完全不同。排序承诺越强代价越高。你要多少就付多少。4.2 什么时候 nth_element 更好std::nth_element()是一个非常容易被低估的算法。执行完nth_element(first, nth, last)后只有第nth个元素处于“如果把整个区间排序它应该待的位置”它左边的所有元素都不大于它右边的所有元素都不小于它但两边内部都无序。这个特性决定了两类场景它比partial_sort()更合适第一类是只要中位数、分位数这类“单点值”的场景。比如统计一堆请求耗时的 P95 阈值我只需要知道第 95% 位置的值是多少不关心这个值前后长什么样。用nth_element()一次搞定平均 O(N)比partial_sort()的 O(N log K) 更快。第二类是“我只要 TopK 的集合但集合内部顺序完全不重要”的场景。比如从一批用户里筛出积分最高的 1000 人做运营活动活动入口展示时再随机洗牌那这 1000 人的内部顺序没有意义。这时nth_element()可以以更低的成本分离出“前 1000”和“其余部分”。如果你发现你的业务代码里用了partial_sort()但取出的 K 个元素其实只是被遍历、没有按序展示那大概率换成nth_element()更划算。4.3 什么时候直接 sort 反而更好工程上有个很反直觉的点partial_sort()不总是比sort()快。当 K 接近 N 的时候O(N log K) 和 O(N log N) 几乎没有差别而sort()实现的内省排序在工程常数上往往优于堆排序路线所以此时sort()可能更快代码也更简单。我自己的经验阈值是如果 K N / 2我会直接std::sort()全排一遍然后截取前 K 个。举一个具体例子假设你有 10000 条数据需求是取前 6000 条展示后面 4000 条都是辅助信息。此时用partial_sort()复杂度大约 10000 × log2(6000) ≈ 13 万次比较用sort()复杂度大约 10000 × log2(10000) ≈ 13.3 万次比较。两者几乎持平但sort()的常规直插/快排路径对缓存更友好实测往往不落下风。与其写一个带middle的三迭代器调用再解释给同事听不如一行sort()来得直白。4.4 容器适配list 怎么办std::list只有双向迭代器不能使用partial_sort()也无法使用std::sort()的迭代器版本。list自带成员函数list.sort()但那是全量归并排序并没有提供“只排前 K 个”的现成接口。如果业务确实要对list做局部排序我常用的迂回方案是把元素转移到std::vector在vector上做partial_sort()再把排好序的前 K 个拷回list或另建一个结构。虽然多了一次拷贝开销但胜在逻辑清晰、测试方便。另一种更贴合工程的做法是直接改变数据组织方式既然要做部分排序说明数据本身应该是连续内存更合适list不是局部排序的好载体该换容器时就换。5. 实测数据与性能直觉百万数据里挑 Top205.1 自己动手测一套可复用的计时骨架理论讲得再多不如自己跑一次。下面这段代码可以在你的机器上验证不同算法的量级差异。注意一定要用原始数据的拷贝去分别测试因为sort()、partial_sort()、nth_element()都会修改容器连续跑会让上一次的结果污染下一次的输入#include algorithm #include chrono #include iostream #include random #include vector template typename Func double run_ms(Func f) { auto t0 std::chrono::steady_clock::now(); f(); auto t1 std::chrono::steady_clock::now(); return std::chrono::durationdouble, std::milli(t1 - t0).count(); } int main() { const int N 1000000; const int K 20; std::vectorint data(N); std::mt19937 rng(12345); std::uniform_int_distributionint dist(0, 1000000); for (int x : data) { x dist(rng); } { std::vectorint tmp data; std::cout sort(): run_ms([] { std::sort(tmp.begin(), tmp.end()); }) ms\n; } { std::vectorint tmp data; std::cout partial_sort(): run_ms([] { std::partial_sort(tmp.begin(), tmp.begin() K, tmp.end()); }) ms\n; } { std::vectorint tmp data; std::cout nth_element(): run_ms([] { std::nth_element(tmp.begin(), tmp.begin() K, tmp.end()); }) ms\n; } }这段代码的核心逻辑是先准备好一份百万级随机整数然后复制三份分别调用三个算法并统计耗时。如果你把K从 20 改成 200、2000、20000还能看出partial_sort()的耗时随 K 增长的趋势。5.2 我实际跑过的量级参考我在自己的开发机上用随机int测试量级大致是百万数据全量sort()耗时大约百毫秒级partial_sort()取前 20 个明显比全量sort()快通常能快出数倍nth_element()取前 20 个又比partial_sort()再快一截。这只是一个非常粗糙的量级参考不同编译器、不同 CPU、不同标准库实现数字可能差出两倍到三倍所以我不建议你拿着某个具体数字去写技术方案自己动手跑一遍才是正道。更有参考价值的其实是两个趋势第一个趋势是K 越小partial_sort()相对sort()的优势越大。K 从 10 涨到 1000耗时曲线的上升非常平缓而如果 K 涨到 50 万它的耗时就会向sort()靠拢最终反超。第二个趋势是元素本身的移动成本对结果影响很大。上面测试用的是int拷贝成本极小。如果换成std::string或者带有复杂资源的结构体内存搬运的开销会显著放大排序差异。此时partial_sort()因为只对 K 个候选者反复做堆调整元素移动次数少相对优势会比int测试时更加明显。5.3 理论之外的三个隐藏变量只看复杂度很容易得出“partial_sort 一定快”的错误结论实际工程里还有三个隐藏变量第一个是缓存局部性。std::sort()在接近排序完成时会退化成插入排序对连续内存的访问非常友好而partial_sort()的堆调整是跳着访问数组的缓存命中率不如快速排序的路线。所以当 K 相对大时堆的常数劣势会抵消复杂度优势。第二个是元素体积。partial_sort()的空间优势体现在它不需要把整个序列搬进另一个容器但它内部仍会频繁交换元素。如果元素是大对象最好先把下标或指针抽出来做成一个索引数组对索引做部分排序再按排序结果去访问原始对象。这个技巧不专属partial_sort()但在处理 TopK 问题时尤其有用。第三个是数据来源。如果数据本身在数据库或远程接口里partial_sort()处理的是“已经全部在内存里”之后的部分。此时真正的耗时大头往往在数据组装和网络传输排序算法怎么选对整体体验的影响可能不到百分之一。先剖析瓶颈再去优化排序才是工程上正确的顺序。6. 实战避坑记录这些细节能让你少上一次当6.1 比较器必须严格弱序别在 sort 系算法里用 所有标准库排序算法要求比较器满足严格弱序strict weak ordering。简单理解就是对于任意元素 acomp(a, a)必须返回false如果comp(a, b)为真且comp(b, c)为真那么comp(a, c)必须为真。新手最容易犯的错是自定义比较器时写成return a.score b.score;。这个写法违反了“对相同元素必须返回 false”的规则可能导致排序行为未定义轻则结果不符合预期重则越界崩溃。正确的做法是写成return a.score b.score;相等的情况交给算法自己去处理。如果你需要“分数相等时id 小的排前面”那就把比较器写成if (a.score ! b.score) return a.score b.score; // 分数高的在前 return a.id b.id; // 分数相同时 id 小的在前这样任何两个不同元素都能分出先后比较器也满足严格弱序。6.2 partial_sort_copy 的“截断”不是截原数组前 M 个这个坑我见过不止一次。很多人看到partial_sort_copy()的输出区间小于输入区间就下意识以为是“取输入区间的前 M 个元素排好序放到输出里”。事实完全不是这样它取的是整个输入区间的“全局前 M 小/大元素”。举个例子输入是{9, 2, 8, 1, 7, 3}输出容量为 3。正确结果是输出{1, 2, 3}因为这是全区间最小的 3 个而不是{1, 8, 9}也不是{2, 8, 9}这种“取输入前三个再排序”的结果。这个区别影响很大。如果你在使用partial_sort_copy()时自以为它只处理前几个元素那么在大数据量下性能预期和业务逻辑都会出错。正确理解是它会完整遍历输入区间只是把有序结果截断到输出容量。这样反而让它很适合同步筛选数据流即使输入有上百万条只要输出数组开了很小的口子它就能在只读模式下挑出最值得保留的那批。6.3 稳定性问题相等元素的“伪随机”partial_sort()是不稳定排序这一点在官方文档里有明确说明。但实际开发中很少有人会为这个特性主动做测试直到某天运营反馈“排行榜里两个相同分数的用户刷新后前后顺序变了”这时候才想起来问为什么我用的是partial_sort()结果看起来像随机遇到这种问题简单把算法换成stable_sort()不一定划算因为你可能只是需要“分数相同就按注册时间排”。更好的做法是在比较器里引入并列次序把复合键比较写好。如果不想改比较器也可以用std::stable_sort()全排后截取但这是用更高复杂度换稳定性数据量大时要谨慎。6.4 从 C17 到 C20执行策略与 ranges 版本C17 开始partial_sort()增加了带执行策略的重载例如std::partial_sort(std::execution::par, first, middle, last);并行版本可以利用多核加速大数据量的排序但线程调度也有开销。小数据量比如几万元素开并行往往比串行更慢。我的建议是只有当数据量达到千万级、且 K 也较大时并行partial_sort()才值得尝试否则默认用串行版本代码也更好读。C20 还提供了std::ranges::partial_sort()支持直接传入范围对象写法更现代。如果你所在项目已经启用了 C20可以优先考虑 ranges 版本它和传统版本的核心语义完全一致只是参数形式更友好。6.5 动态数据流场景别反复调用 partial_sort最后一个工程经验如果数据不是“一次性全量到了”再做局部排序而是不断有新数据插入那每次插入都调用一次partial_sort()是非常低效的做法。每次调用都是 O(N log K)数据量大时很难看。这种场景应该自己维护一个固定容量 K 的std::priority_queue或者自己写一个 K 容量的小顶堆。新元素进来时只和堆顶比较决定进不进堆每次维护成本只有 O(log K)。partial_sort()更适合“已知完整容器只需要取一次前 K”的批量场景。两者互补并不冲突。实际项目里我会先问自己三个问题是全量排序还是只要前 K 个前 K 个内部是否需要有序原数据还能不能动问完之后选哪个算法基本就有答案了。partial_sort()是我这几年用得最频繁的排序算法之一因为它解决的问题足够具体复杂度上又能清晰看到“少排序一部分”带来的收益。最后再分享一个野路子如果你拿不准某个场景到底该用partial_sort()还是nth_element()就拷贝两份数据各跑一次用chrono计时看结果。排序这种代码用一小段测试定胜负比对着文档猜半天高效得多。方法论这东西最终还是落到“自己跑一遍、自己看数据”上最可靠。