STL排序与堆算法解析：从sort到nth

这轮 STL 笔记写到第11篇，我想集中把排序和堆相关的内容整理一遍。起因是在好几个项目里见到同一种代码习惯：要排行榜，就把 100 万条数据全部std::sort，再切片取前 100；要算中位数，也是先 sort 再取中间值。需求当然都能满足，但排序本身不是目的，很多时候我们需要的只是“某个位置上的答案”或者“前面的 K 个元素”。

STL 给开发者准备了一整套与排序相关的工具，除了最常见的std::sort，还有std::stable_sort、std::partial_sort、std::nth_element，以及以std::make_heap、std::push_heap、std::pop_heap、std::sort_heap为核心的堆操作族。这篇笔记就是把这些工具放到同一张工作台上，讲清楚每个算法解决什么问题、时间代价大概是多少、什么时候该选哪个。内容适合已经会操作vector、deque、list等容器，但对 STL 算法还停留在“会用 sort”这个阶段的读者。读完你至少能回答下面这个常见问题：为什么处理 TopK 时partial_sort比sort更合适，为什么nth_element可以在线性时间里找出中位数。

如果有人问我排序的黄金规则，我的答案是：先搞清楚你需要的到底是“完整顺序”还是“部分答案”。大多数实际需求属于后者，但很多代码默认使用了前者，性能和内存就是这样一点一点被浪费掉的。

1. std::sort 背后的内省排序：为什么又快又不容易爆栈

std::sort是绝大多数 C++ 开发者接触的第一个 STL 算法。接口很简洁：两个迭代器，加一个可选比较器，完事。但越是这样简洁的工具，越容易让人忽略它内部到底承诺了哪些行为。

1.1 标准承诺了什么，没承诺什么

先看标准层面对std::sort的约束。它要求随机访问迭代器，也就是说只能用于vector、deque、C 数组这类支持随机跳跃的容器，不能直接用在list上。复杂度方面，标准要求平均情况下的比较次数为 O(N log N)，默认比较行为是operator<。

标准刻意没有规定底层必须采用哪一种排序算法，这给了标准库实现足够的自由空间。所以不同环境下的内部细节可能会有差异，但主流实现基本都收敛到了同一套策略：内省排序。

这里要记住一件非常关键的事：std::sort不保证稳定性。所谓稳定性，指两个排序键相等的元素，排序后是否仍然保持原来的相对先后。sort的文档语义就是“不保证”，如果你在写涉及多字段排序的程序，比如先按成绩主键排，同成绩下还指望按原始录入顺序保留，sort是帮不了你的。

1.2 纯快排不够可靠，内省排序做了什么

传统教科书排序无外乎快排、归并、堆排这三种路线。纯快速排序平均复杂度是 O(N log N)，但最坏情况会退化到 O(N^2)，递归深度也可能到 O(N)，数据量大时连调用栈都有压力。堆排序能在最坏情况下稳定在 O(N log N)，但它常数偏大，对 CPU 缓存不友好。归并排序稳定且行为可预测，可它需要额外内存，这与sort这种“原地进行、不想额外分配”的定位不符。

内省排序的思路是组合拳：先用快速排序框架获得平均情况下的速度；同时记录当前的递归深度，一旦深度超过约2 * floor(log2 N)，就认为快排的划分已经失衡，立刻转入堆排序，从根上掐断退化到 O(N^2) 的可能。当递归划分出的区间长度缩小到阈值以内，比如小于 16 个元素，再改用插入排序。插入排序在接近有序的小片段上常数极小，直接手写一段简单循环，比继续递归拆分区间的开销还低。

你可以把内省排序理解成一个会自我纠错的流程：平时用快排跑得飞快，一旦感觉情况不对，立刻换用保守但稳定的策略。这样既保持了平均性能，又避免了最坏情况下的一崩到底。

1.3 “不稳定”在实际代码里会造成什么问题

假设一个记录数组保存了(成绩, 姓名)两项，现在要按成绩降序排列。不稳定的sort在执行后，相同成绩的不同姓名之间，顺序是随机的，两次运行的输出可能不一样。如果是展示型页面，用户可能根本注意不到；但如果这是计费、审核或者对顺序有隐性依赖的业务逻辑，不稳定就很容易埋下隐患。

我一般会在两种情况下果断放弃sort改用stable_sort：第一种是数据本身存在“主键相等，次键需保持原序”的约束；第二种是后续处理依赖稳定的顺序，例如你需要把相同权重的任务按入队先后处理。其余绝大多数纯数值排序，sort就是合适的选择。

2. stable_sort：稳定性的价格到底贵在哪

stable_sort的接口长得和sort几乎一模一样，但语义上多了一条硬保证：等价元素的相对顺序保持不变。听起来只是多了一个属性，实际实现代价却不小。

2.1 归并排序是稳定性的来源

要实现稳定排序，经典的方案就是归并排序。归并排序先把序列拆成越来越小的片段，然后逐一合并两个已经有序的片段。合并时，如果两个元素相等，必须保证左侧片段中的那个先进入结果，这样稳定性才能成立。

问题在于，稳定合并几乎不太可能全程都在原地完成，主流实现普遍需要一定量的额外内存。因此stable_sort在运行时可能执行额外的内存分配。如果系统内存不足，标准允许它的复杂度退化为 O(N log N log N)，也就是额外多一个对数因子，数据量大时差距会非常明显。这也是为什么很多性能敏感项目不会默认使用stable_sort，哪怕他们嘴上说着“希望稳定一点”。

这里我还想纠正一个直觉误区：稳定并不意味着慢很多倍。如果额外内存充足，stable_sort的总复杂度仍然是 O(N log N)，只是常数项比sort大一些。真正需要警惕的是内存不足时的降级路径，那才是性能崩掉的重灾区。

2.2 一个需要稳定顺序的场景

举个例子。假设你的程序已经维护了一个学生评分列表，初始顺序是学号从小到大。现在需要把成绩按从高到低排名，并且希望成绩相同的两个人依然按照学号升序显示。直接用sort无法保证这一点，但这是stable_sort的天然主场：

#include <algorithm> #include <vector> #include <string> struct Student { int score; int id; }; std::vector<Student> students; // 初始顺序已经是按 id 升序 std::stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) { return a.score > b.score; });

这段代码执行完毕后，相同score的元素之间的原始id顺序会原样保留。注意比较器里只写a.score > b.score，不要在 score 相等时返回true，这是严格弱序的基本要求，后面第 5 章还会专门展开。

2.3 什么时候别用 stable_sort

纯数值数组基本不需要稳定排序。比如一堆int排序，两个 42 完全等值，谁前谁后压根没意义，这时用sort就好。另外，如果你的代码已经知道数据里不存在重复键，稳定属性并不会带来额外收益，反而白白承担了归并排序可能的内存开销。

我见过不少团队为了保险把所有排序都写成stable_sort，理由是“万一以后有稳定需求呢”。这个习惯我不是很赞成。排序算法选型应该基于当前明确的需求，而不是给未来的可能性预付费。等需求真正出现时再换成stable_sort，成本低得很，远没有想象中那么麻烦。

3. partial_sort 和 nth_element：处理 TopK 的两把刀

很多开发者不知道partial_sort和nth_element的存在，所以才会出现“全量 sort 再取前 K 个”的写法。这两个算法才是专门为“部分答案”设计的，你需要先分清楚它们解决了不同的问题。

3.1 partial_sort 的内部实现思路

partial_sort(first, first + k, last)的作用是：整个范围里最小的 K 个元素会被放在区间[first, first + k)，而且这个区间内部是有序的。标准复杂度是 O(N log K)，很明显比 O(N log N) 有优势，尤其当 K 远小于 N 时。

它是怎么做到的？常见实现是先取出前 K 个元素，建立一个最大堆。因为目标是找出最小的 K 个，所以这个堆要快速淘汰掉“当前最大的那个候选”。接着遍历剩余元素，每遇到一个元素，就和堆顶比较：如果比堆顶小，就替换堆顶并调整堆；如果比堆顶大，直接跳过。遍历结束后，前 K 个元素就是整个数组中最小的 K 个，但此时它们在堆里还不是有序的，最后再做一次堆排序收尾。

这个思路非常优雅。每个剩余元素只需和堆顶比较一次，遇到“更小”的情况才做一次 O(log K) 的堆调整，所以整体复杂度基本被压在 O(N log K)。K 越接近 N，它就越接近完全排序；K 很小的时候，性能优势几乎是压倒性的。

3.2 nth_element：只要第 K 个，不要求前 K 个有序

nth_element比partial_sort更进一步。执行完nth_element(begin, begin + k, end)后，位置begin + k上的元素一定位于它最终排序后的正确位置，它之前的元素都小于等于它，之后的元素都大于等于它。但左右两侧内部是否有序，标准并不保证。

它在典型实现里采用快速选择，平均复杂度是 O(N)。这就意味着，找第 100 名成绩这种需求，理论上可以做到接近线性的时间，比先全量排序再取值快上一个数量级。

有的人会问：那直接用nth_element取完 TopK，不就能替代partial_sort了吗？不完全对。nth_element只保证边界点正确，前 K 个元素是“无序集合”，如果你需要它们再按顺序展示，就得额外再排一次序。

实际操作里常用的组合拳是这样的：

#include <algorithm> #include <vector> std::vector<int> scores; // 先放入大量数据 std::nth_element(scores.begin(), scores.begin() + 99, scores.end()); std::sort(scores.begin(), scores.begin() + 100);

第一步利用线性时间把第 100 名放到正确边界，第二步只需要对前 100 个元素做一次小规模排序。整体代价是 O(N) 加 O(K log K)，把全量排序彻底绕开了。

3.3 四个排序类函数的横向对比

为了更直观，我把四个函数的定位放在一张表里。

函数	得到的结果	比较复杂度	稳定性	额外内存
`std::sort`	完整有序序列	O(N log N)	不稳定	通常不需要
`std::stable_sort`	完整有序序列，等价元素保序	O(N log N)	稳定	可能需要
`std::partial_sort`	前 K 个元素有序，其余未定义	O(N log K)	不稳定	通常不需要
`std::nth_element`	第 K 个元素就位，左右未排序	平均 O(N)	不稳定	通常不需要

选型第一条依据就是“你是否真的需要完整序列”。需要完整序列，从sort和stable_sort里二选一；不需要完整序列，从partial_sort和nth_element里做选择。如果前 K 个元素的先后顺序也要展示，选partial_sort；只要一个边界值或者之后还有能力再排一次，选nth_element。

4. 堆操作四函数和 priority_queue：动态场景下的排序替代方案

排序的前提往往是“数据已经全部到位”。但真实程序里还有一种更高频的形态：数据在不断涌入，系统随时需要知道当前的最大、最小或者中位数。这种情况下，每次插入都排序显然是灾难，正确解法是维护一个动态堆。

4.1 堆在数组里的形态

很多人在数据结构课上学过堆，但一到 C++ 代码里就发懵，因为 STL 里的“堆”并不是一棵物理的二叉树，而是存储在数组里的一种逻辑结构。

如果数据存储在vector里，那么vector[i]的父节点是vector[(i - 1) / 2]，左孩子是vector[2 * i + 1]，右孩子是vector[2 * i + 2]。只要每个父节点都不小于它的两个孩子，整个结构就是最大堆；反过来就是最小堆。所有堆操作的复杂度都建立在索引跳转之上，不需要真正的指针或者树节点，所以内存非常紧凑，对缓存友好。

4.2 STL 提供的四个原始堆函数

C++ STL 在<algorithm>里提供了四个函数：

std::make_heap(first, last)：线性时间内把一段范围内元素原地堆化。
std::push_heap(first, last)：把容器尾部新增的元素重新调整到正确位置。
std::pop_heap(first, last)：把堆顶元素移动到容器末尾，并让剩余元素重新满足堆性质。
std::sort_heap(first, last)：将已经堆化的范围排序成普通有序序列。

这四个函数配合vector使用，典型模式如下：

#include <algorithm> #include <vector> std::vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6}; std::make_heap(data.begin(), data.end()); // 此时 data 是一个最大堆，最大值在 data[0] std::pop_heap(data.begin(), data.end()); int maxValue = data.back(); // 取出最大值 data.pop_back(); // 从容器中移除 data.push_back(10); // 先插入到末尾 std::push_heap(data.begin(), data.end()); // 调整后，最大值 10 会浮到 data[0]

注意push_heap的前提是元素已经push_back到容器尾部，再调用push_heap做调整。如果忘记这一步，结果是不符合堆性质的。

4.3 priority_queue 只是给堆套了一层壳

每次写make_heap、push_heap、pop_heap确实有点繁琐，所以 STL 提供了std::priority_queue这个容器适配器。它内部封装了底层容器、比较器和堆操作，只对外暴露push、pop、top这几个接口，把“用户堆积木”变成“用户按开关”。

默认构造的是最大堆：

#include <queue> #include <vector> std::priority_queue<int> maxHeap; maxHeap.push(5); maxHeap.push(10); int top = maxHeap.top(); // 10 maxHeap.pop();

如果需要最小堆，必须指定底层容器和比较器：

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

priority_queue因为不提供迭代器，所以不能遍历，也不能直接访问内部元素。这个限制其实是故意设计的，它把堆的语义收窄成“只能取极值”，从而避免用户破坏堆性质。

4.4 双堆求中位数的经典做法

动态中位数是堆应用的经典场景。思路是维护两个堆：最大堆存较小的一半，最小堆存较大的一半。新元素到达时，根据其与两个堆顶的关系插入合适的一侧，然后通过调整两侧规模，确保最大堆要么比最小堆多一个，要么两边一样多。这样中位数永远可以从最大堆顶，或者两个堆顶的平均数中得到。

#include <queue> #include <vector> std::priority_queue<int> low; // 最大堆，存较小的一半 std::priority_queue<int, std::vector<int>, std::greater<int>> high; // 最小堆，存较大的一半 void addNumber(int value) { if (low.empty() || value <= low.top()) { low.push(value); } else { high.push(value); } if (low.size() > high.size() + 1) { high.push(low.top()); low.pop(); } else if (high.size() > low.size()) { low.push(high.top()); high.pop(); } } double getMedian() { if (low.size() == high.size()) { return (low.top() + high.top()) / 2.0; } return low.top(); }

这段代码的值在于每次插入都是 O(log N)，查询中位数是 O(1)。如果数据量很大且持续进入，双堆方案远比“每次插入后排序”更合理。

5. 排序与堆的实战坑：比较器、迭代器和性能验证

算法选对了，还不意味着代码就安全了。下面这些坑我在实际项目里见过不止一次，写出来给读者排个雷。

5.1 比较器必须满足严格弱序

排序比较器的第一条铁律是：必须定义严格弱序。用大白话说，comp(a, b)为真，意味着a严格排在b前面；如果a和b“等价”，那么comp(a, b)和comp(b, a)都应该为假。

一个常见的错误写法是：

// 错误示例 [](const Student& a, const Student& b) { if (a.score == b.score) return true; // 相同也返回 true，直接寄了 return a.score > b.score; }

一旦出现了“两个方向都返回真”的比较器，排序算法的内部假设就会崩塌，轻则顺序错乱，重则越界崩溃。正确的做法是只在“严格大于”时返回真，其他情况一律返回假：

[](const Student& a, const Student& b) { return a.score > b.score; }

另外要注意，比较器不应该在单次排序过程中修改被比较对象，也不要依赖会变化的外部状态。很多实现会把比较器拷贝多份，如果你把内部计数值塞进比较器，得到的统计结果多半不是你想要的。

5.2 迭代器失效问题

排序本身不会引起像push_back那样的迭代器失效，因为整个排序过程中元素并未移出容器，只是原地调整位置。但真正的问题是逻辑上的失效：排序前某个迭代器指向的位置，排序后留在那个位置的元素已经变了。如果你在排序之前保存了一个指向某个元素的迭代器，希望排序后还能通过它找到原先那个对象，这行不通。

解决方式很简单：需要跟踪元素，就存下标或者存对象值，必要时先备份索引关系。尤其是配合stable_sort的场景，别以为稳定的只是排序，迭代器的位置还是会变化的。

5.3 性能测试别靠直觉

有人抱怨std::sort慢，结果发现是在 Debug 模式下跑的。STL 算法在未开启优化时会伴随大量检查逻辑，性能和 Release 差出几倍甚至几十倍都很常见。所以做任何算法对比，第一步都是在开启优化之后测。

我建议准备一个简单的对比程序，生成 100 万个随机整数，分别用sort、partial_sort、nth_element处理同一个任务，但注意每次都要用一份独立拷贝。这是因为算法会把原容器打乱，如果在同一份数据上连续调用，得到的结果毫无意义。

std::vector<int> base(1000000); // 填充随机数 for (int i = 0; i < 3; ++i) { std::vector<int> data = base; // 分别调用 sort / partial_sort / nth_element // 记录耗时 }

实测下来，在 K 远小于 N 的场景里，sort通常比partial_sort慢不少，而nth_element比partial_sort可能再快一个数量级以上，因为它只做边界切分，不需要把前 K 个排成有序。这里的差距正是算法复杂度从 O(N log N) 降到 O(N log K) 再到 O(N) 的直观体现。