不知道你有没有遇到过这种需求：界面上要展示一份榜单，只显示前 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>头文件中，最常用的两个重载是：

template<class RandomIt> void partial_sort(RandomIt first, RandomIt middle, RandomIt last); template<class 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::vector<int> 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::greater<int>()：

#include <algorithm> #include <functional> #include <iostream> #include <vector> int main() { std::vector<int> 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::greater<int>()); for (int i = 0; i < topK; ++i) { std::cout << scores[i] << ' '; // 输出最大的 3 个，且降序 } std::cout << '\n'; }

比较器的语义可以这样理解：comp(a, b)返回true表示a应该排在b前面。默认std::less<int>()是小的在前，所以得到升序；改成std::greater<int>()后，大的在前，于是前面 K 个位置就变成了“全局最大 K 个且降序”。

如果你希望最大的 K 个以升序展示，可以先取出来再手动reverse前三项，或者用partial_sort_copy()输出到新数组后再局部反转。这里没有标准库的直接一键方案，通常业务里怎么展示是另一层的问题。

2.4 partial_sort_copy：不修改原始数据

std::partial_sort_copy()是partial_sort()的“不破坏原数据”版本，它把排序结果复制到另一个容器中，遍历的是输入区间，写入的是输出区间：

template<class 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::vector<Item> items{{1, 100}, {2, 999}, {3, 50}, {4, 300}, {5, 700}, {6, 800}}; std::vector<Item> 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()，但主流实现基本都走同一条路：最大堆。以默认升序版本为例，大致步骤是：

1. 对[first, middle)这个长度为 K 的前缀区间构建一个最大堆。注意最大堆意味着堆顶元素是这一小段里最大的一个。
2. 从middle开始遍历[middle, last)中的每一个元素。如果当前元素比堆顶元素还要小，说明当前元素更有资格进入前 K 小，于是把堆顶元素“踢出局”，把当前元素放进堆里，并重新调整堆的结构。
3. 等整个区间都遍历完，[first, middle)里留下的就是全局最小的 K 个元素，但它们还处在最大堆的形态，堆顶最大，不是有序的。
4. 最后对[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()全量排序后截取，要么在比较器里加一个序号字段做次级排序键，例如比较pair<score, id>，强制让比较结果不完全相等，从而把“稳定性”变成“确定性”。

4. 选型对比：sort、nth_element、stable_sort 和 partial_sort 怎么分工

4.1 一张表看各算法的保证

很多人都知道std::sort()和std::partial_sort()，但遇到具体需求时还是会搞混。我先用一张表把这几个常用算法拉齐：

这张表的价值在于：几个算法都长得很像，但它们对“结果”的承诺级别完全不同。排序承诺越强，代价越高。你要多少，就付多少。

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. 实测数据与性能直觉：百万数据里挑 Top20

5.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::duration<double, std::milli>(t1 - t0).count(); } int main() { const int N = 1'000'000; const int K = 20; std::vector<int> data(N); std::mt19937 rng(12345); std::uniform_int_distribution<int> dist(0, 1'000'000); for (int& x : data) { x = dist(rng); } { std::vector<int> tmp = data; std::cout << "sort(): " << run_ms([&] { std::sort(tmp.begin(), tmp.end()); }) << " ms\n"; } { std::vector<int> tmp = data; std::cout << "partial_sort(): " << run_ms([&] { std::partial_sort(tmp.begin(), tmp.begin() + K, tmp.end()); }) << " ms\n"; } { std::vector<int> 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）。简单理解就是：

• 对于任意元素 a，comp(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 从 C++17 到 C++20：执行策略与 ranges 版本

C++17 开始，partial_sort()增加了带执行策略的重载，例如：

std::partial_sort(std::execution::par, first, middle, last);

并行版本可以利用多核加速大数据量的排序，但线程调度也有开销。小数据量（比如几万元素）开并行，往往比串行更慢。我的建议是：只有当数据量达到千万级、且 K 也较大时，并行partial_sort()才值得尝试；否则默认用串行版本，代码也更好读。

C++20 还提供了std::ranges::partial_sort()，支持直接传入范围对象，写法更现代。如果你所在项目已经启用了 C++20，可以优先考虑 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计时看结果。排序这种代码用一小段测试定胜负，比对着文档猜半天高效得多。方法论这东西，最终还是落到“自己跑一遍、自己看数据”上最可靠。