Chapter 28: Sorting Algorithms
核心问题与阅读主线
排序算法重排半开区间 [first, last) 内的元素,其结果可靠性取决于区间有效、元素可移动/交换或赋值,以及比较器满足严格弱序。本章围绕 std::sort、std::stable_sort、std::partial_sort、std::nth_element 与 std::is_sorted/std::is_sorted_until,给出按结果强度选型并验证比较器语义的工程判据。
全章共用代码样本(下文各节持续拆解)
贯穿全章的材料是一组 ScoreRecord 成绩记录(含姓名 name、分数 score 与录入序号 seq),用来对照观察全量排名、同分顺序保留、只取前 K 名与定位分位阈值四类问题。
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct ScoreRecord {
std::string name;
int score;
int seq;
};
bool higher_score(const ScoreRecord& left, const ScoreRecord& right) {
return left.score > right.score;
}
void print_records(const std::vector<ScoreRecord>& records) {
for (const auto& r : records) {
std::cout << r.name << ':' << r.score << "#" << r.seq << ' ';
}
std::cout << '\n';
}
higher_score 仅比较 score 降序,不处理姓名与 seq。对同分记录而言,comp(a, b) 与 comp(b, a) 均返回 false,构成同一等价类——四个重排算法的行为分歧正集中在这类等价元素、前 K 个位置与第 N 个位置上。
28.1 sort、stable_sort、partial_sort 与 nth_element
这四个算法都会原地重排输入区间,但交付的结果强度逐级递减;选型的首要依据是下游代码消费整个区间、前 K 个元素,还是单个分界位置。
std::sort 交付完整有序区间:排序后任意靠后元素都不会被比较器判定应排在靠前元素之前,适合完整排名遍历、全区间二分查找、集合算法或合并算法前序准备。
std::vector<ScoreRecord> records = {
{"Ada", 90, 0}, {"Bjarne", 95, 1}, {"Chloe", 90, 2},
{"Dennis", 80, 3}, {"Edsger", 95, 4}, {"Fay", 70, 5}
};
std::sort(records.begin(), records.end(), higher_score);
print_records(records);
该调用保证 95 分在 90 分之前、90 分在 80 分之前,但不承诺保留 Bjarne 与 Edsger(同为 95 分)或 Ada 与 Chloe(同为 90 分)的原相对顺序。
std::stable_sort 在完整有序之上保留等价元素的原相对顺序。对同一批 records 按 higher_score 稳定排序后,Bjarne(原 seq 为 1)仍在 Edsger(原 seq 为 4)前,Ada(原 seq 为 0)仍在 Chloe(原 seq 为 2)前:
std::stable_sort(records.begin(), records.end(), higher_score);
稳定性服务两类无法用实现习惯替代的结果语义:
- 多阶段排序:先按次键(如姓名)排,再按主键(如分数)稳定排序,组合出“主键分数、次键姓名”。
- 保留业务时间线:同分保持报名顺序、订单保持创建顺序、日志保持到达顺序。
std::partial_sort 交付前段有序,适合排行榜首页、最小 K 个延迟或最大 K 个订单金额。调用 std::partial_sort(first, middle, last, comp) 后,[first, middle) 包含整个区间最靠前的 middle - first 个元素且自身已按 comp 排序:
auto top3_end = records.begin() + 3;
std::partial_sort(records.begin(), top3_end, records.end(), higher_score);
for (auto it = records.begin(); it != top3_end; ++it) {
std::cout << it->name << ':' << it->score << ' ';
}
std::cout << '\n';
尾部 [middle, last) 顺序未指定,不能直接用于二分查找或有序展示。
std::nth_element 只保证第 N 个位置就位及其两侧分区,适合中位数、百分位阈值和 Top K 分界线:
*nth等于完整排序后该位置会出现的某个元素。[first, nth)中无元素应排在*nth后方,[nth, last)中无元素应排在*nth前方,但两侧内部均无有序承诺。
auto median = records.begin() + records.size() / 2;
std::nth_element(records.begin(), median, records.end(), higher_score);
std::cout << "threshold = " << median->score << '\n';
若随后需要按顺序输出 Top K,须对 [first, nth) 再调用 std::sort 或改用 std::partial_sort。
| 算法 | 交付结果保证 | 等价元素相对顺序 | 剩余区间状态 | 典型场景 |
|---|---|---|---|---|
std::sort | 全区间 [first, last) 有序 | 不保证保留 | 无剩余段 | 全量排名、全区间二分与集合运算 |
std::stable_sort | 全区间 [first, last) 有序 | 严格保留原顺序 | 无剩余段 | 多阶段排序、同键保留时间线 |
std::partial_sort | 前段 [first, middle) 为最前 K 个且有序 | 不保证保留 | [middle, last) 未指定 | 排行榜前 K 页、极值 Top K |
std::nth_element | *nth 就位且满足左右分区 | 不保证保留 | 两侧内部均无序 | 中位数、分位阈值、Top K 分界线 |
边界与误区
这四个算法都要求随机访问迭代器,适用于 std::vector、std::array、std::deque 和原生数组。std::list 与 std::forward_list 不满足该要求,应调用容器成员函数(如 list.sort(comp)),通过重连节点完成排序并保持链表迭代器语义。
28.2 is_sorted 与 is_sorted_until
std::is_sorted 与 std::is_sorted_until 不重排元素,仅通过扫描把“有序前提”转化为可验证证据,适用于二分查找、集合算法及增量管线的边界校验。
std::is_sorted(first, last, comp) 返回布尔值,用于边界或断言快速确认前提:
std::vector<ScoreRecord> records = {
{"Bjarne", 95, 1}, {"Edsger", 95, 4}, {"Ada", 90, 0},
{"Chloe", 90, 2}, {"Dennis", 80, 3}, {"Fay", 70, 5}
};
if (!std::is_sorted(records.begin(), records.end(), higher_score)) {
std::cerr << "score records are not sorted by descending score\n";
}
std::is_sorted_until(first, last, comp) 返回第一个破坏有序性的迭代器(全区间有序时返回 last):它沿区间检查相邻元素,一旦发现 comp(*current, *previous) 为 true,即以 current 作为第一个断点,前缀 [first, bad) 已满足 comp。
auto bad = std::is_sorted_until(records.begin(), records.end(), higher_score);
if (bad != records.end()) {
std::cout << "first broken record: " << bad->name
<< ", score=" << bad->score << '\n';
}
| 检测函数 | 返回值语义 | 最低迭代器要求 | 适用场景 |
|---|---|---|---|
std::is_sorted | bool(全区间是否有序) | 前向迭代器 | 生产入口断言或前置条件校验 |
std::is_sorted_until | 首个破序迭代器(全有序时返回 last) | 前向迭代器 | 调试定位乱序断点、截取有序前缀 |
边界与误区
有序性由“区间 + 比较器”共同定义,检查必须与排序及下游二分/集合算法复用同一比较器。两者仅需前向迭代器(支持 std::forward_list),且 size() == 0 与 size() == 1 按定义默认有序无需判空;因其为线性扫描,性能敏感路径应仅置于输入接入、批处理边界或 debug 构建。
28.3 introsort、稳定性与算法策略
关键事实
C++ 标准只规定接口效果、复杂度、迭代器与比较器要求,不规定内部算法名称;源码阅读时应区分“标准承诺(决定可移植语义)”与“常见实现形状(解释性能、临时内存与极端输入行为)”。
std::sort 的常见实现形状是 introsort(教学简化伪代码):
template <class RandomIt, class Compare>
void sort_shape(RandomIt first, RandomIt last, Compare comp) {
auto depth_limit = 2 * floor_log2(last - first);
introsort_loop(first, last, depth_limit, comp);
final_insertion_sort(first, last, comp);
}
这段形状直接对应三个设计要点:
last - first依赖随机访问迭代器的常数时间求距与跳转。depth_limit先走 quicksort 分区,并在递归超限时切到堆排序(heapsort)路径,限制最坏情况比较次数。final_insertion_sort用插入排序收尾小区间,属于常见常数优化,不能据此反推标准强制某一种实现。
std::stable_sort 的常见实现形状接近 merge sort,其稳定性来自合并规则:当左右子区间元素等价时,优先输出左侧元素。实现通常尝试申请临时缓冲区;缓冲充足时比较次数较低,缓冲不足时走额外比较次数更多的原地归并路径。
template <class RandomIt, class Compare>
void stable_sort_shape(RandomIt first, RandomIt last, Compare comp) {
if (last - first <= small_range_limit) {
insertion_sort_stable(first, last, comp);
return;
}
auto mid = first + (last - first) / 2;
stable_sort_shape(first, mid, comp);
stable_sort_shape(mid, last, comp);
stable_merge_preserving_left_equivalent(first, mid, last, comp);
}
std::partial_sort 通常在 [first, middle) 上建一个大小为 $K = middle - first$ 的堆,扫描后续元素并在应进入前 K 时替换堆顶并调堆,最后把堆展开为有序前缀,复杂度约为 $N \log K$。
std::nth_element 通常采用 introselect,围绕 pivot 分区并只递归包含 nth 的一侧,平均比较次数为线性级别。
| 算法 | 常见实现策略 | 临时内存与退化路径 | 稳定性来源/边界 | 源码识别线索 |
|---|---|---|---|---|
std::sort | introsort(快排 + 深度受限堆排 + 小区间插排) | 无需临时归并缓冲 | 不稳定 | 是否计算 last - first 与递归深度上限 |
std::stable_sort | 归并排序(等价时优先输出左侧) | 申请临时缓冲,不足时退化为高比较路径 | 稳定(来自归并取左) | 是否有缓冲申请与等价取左合并分支 |
std::partial_sort | 大小为 $K$ 的堆选择 + 堆展开 | 原地堆调整 | 不稳定;仅前 K 有序 | 是否先对 [first, middle) 建堆再扫尾部 |
std::nth_element | introselect(单侧分区收缩) | 无需临时归并缓冲 | 不稳定;仅第 N 位及分区 | 分区后是否仅保留包含 nth 的一侧子区间 |
28.4 comparator 与 strict weak ordering
对比较器 comp(a, b) 的工作定义是:返回 true 时表示 a 应排在 b 之前。标准库排序算法要求比较器满足严格弱序(strict weak ordering),使算法能把元素划分为有序等价类并在分区、交换与合并时维持一致结论。
严格弱序必须满足四条可检查条件:
- 非自反性:对任意元素
a,comp(a, a)必须为false。 - 互斥性:若
comp(a, b)为true,则comp(b, a)必须为false。 - 传递性:若
comp(a, b)与comp(b, c)均为true,则comp(a, c)必须为true。 - 等价传递性:由
!comp(a, b) && !comp(b, a)定义的等价关系本身具有传递性。
higher_score(left.score > right.score)天然满足以上四条:分数不大于自身,大小关系互斥且传递,同分构成的等价类同样具有传递性。
工程中最常见的破坏来自把 <= 或 >= 写进比较器。下面示例在相等时返回 true,直接破坏 comp(a, a) == false:
bool broken_higher_score(const ScoreRecord& left, const ScoreRecord& right) {
return left.score >= right.score;
}
它告诉算法“同分元素互相排在对方之前”,破坏严格弱序后结果不具备可移植语义,实践中可能出现顺序混乱、断言失败、死循环或跨实现偶发崩溃。
另一类错误是比较器依赖可变外部状态(例如把调用计数混入比较结果):
struct FlippingComparator {
mutable int calls = 0;
bool operator()(const ScoreRecord& left, const ScoreRecord& right) const {
++calls;
if (calls % 2 == 0) {
return left.score > right.score;
}
return left.name < right.name;
}
};
边界与误区
排序算法会以不固定顺序多次比较同一批元素,比较器必须是只读且稳定的关系。切忌依赖调用次数、系统时间、随机数或可变全局状态,也不要在比较时修改元素本身(缓存写入、日志统计或懒加载等副作用应放在排序调用前后)。
多字段排序应显式写成词典序,例如“分数降序,同分按 seq 升序”:
bool score_desc_seq_asc(const ScoreRecord& left, const ScoreRecord& right) {
if (left.score != right.score) {
return left.score > right.score;
}
return left.seq < right.seq;
}
| 同分处理方式 | 等价类边界 | 同分排序依据 | 适用语义 |
|---|---|---|---|
higher_score + std::stable_sort | 同分即等价 | 保留进入区间时的原相对顺序 | 需保留业务到达或报名时间线 |
score_desc_seq_asc + std::sort | 同分且同 seq 才等价 | 按显式次级字段确定顺序 | 需按数据字段打破同分并缩小等价类 |
排查顺序
针对涉及浮点数、空值、大小写折叠、区域排序或多字段条件的比较器,在单测中选取覆盖 <、==、> 的三样本 a、b、c,依次断言:comp(a, a) == false → 互斥性 → 传递性 → 等价关系传递性。
28.5 排序算法复杂度和工程选型
明确消费范围后,即可按复杂度、移动成本、额外内存与执行策略约束敲定最终方案。
| 算法 | 比较次数复杂度 | 额外内存与退化特征 | 选型定位 |
|---|---|---|---|
std::sort | $O(N \log N)$ | 无堆缓冲依赖 | 全有序且不需保留同键输入顺序 |
std::stable_sort | 缓冲充足时 $O(N \log N)$;不足时退化到 $O(N \log^2 N)$ | 尝试申请临时缓冲 | 必须保留等价元素原相对顺序 |
std::partial_sort | 约 $N \log K$($K = middle - first$) | 原地建堆调整 | 只需前 K 个元素有序 |
std::nth_element | 平均 $O(N)$ | 原地分区 | 只需中位数、分位阈值或 Top K 分界线 |
std::is_sorted / is_sorted_until | $O(N)$ | 前向单次扫描 | 验证排序前提或定位乱序断点 |
当元素包含大字符串、动态数组或外部资源句柄时,交换与移动成本会显著抬高;若同时存在多套排序视图或需保留原物理顺序,应改排下标、指针或 std::reference_wrapper:
std::vector<ScoreRecord> records = {
{"Ada", 90, 0}, {"Bjarne", 95, 1}, {"Chloe", 90, 2},
{"Dennis", 80, 3}, {"Edsger", 95, 4}, {"Fay", 70, 5}
};
std::vector<std::size_t> order(records.size());
for (std::size_t i = 0; i < order.size(); ++i) {
order[i] = i;
}
std::sort(order.begin(), order.end(), [&](std::size_t left, std::size_t right) {
return records[left].score > records[right].score;
});
for (std::size_t index : order) {
std::cout << records[index].name << ' ';
}
std::cout << '\n';
下标排序把“移动完整记录”变为“移动整数下标”,代价是比较时多一次间接访问且数据局部性下降;记录较小时直接排序对象更简单。
面对“数据很大、$K$ 相对较小且需要有序 Top K”时,可先 nth_element 切出前 K,再对前缀调用 sort;若 $K$ 接近 $N$,直接 std::sort 的常数优化往往更占优。
auto kth = records.begin() + 3;
std::nth_element(records.begin(), kth, records.end(), higher_score);
std::sort(records.begin(), kth, higher_score);
对于 std::list 等节点式容器,优先使用成员 sort 重连节点;但若后续还要做随机访问、二分查找或连续内存遍历,先复制到 std::vector 排序的总体收益可能高于复制成本。
边界与误区
普通排序中比较器抛异常会中断执行,元素仍保持有效对象但顺序为未完成的中间状态;C++17 标准执行策略重载下,被调用函数抛异常可能直接触发 std::terminate。并行执行策略还额外要求比较器无共享可变状态、可并发调用且结果稳定。
工程选型检查顺序:
- 定消费范围:区分全区间、前 K 有序、第 N 分界或仅检测前提。
- 定稳定性:判断是否必须保留等价元素的原相对顺序。
- 查迭代器能力:重排算法需随机访问(
list用成员sort),检测只需前向。 - 验比较器契约:确认严格弱序且只读无状态(并行策略需可并发)。
- 估规模与移动开销:权衡 $N$、$K$、比较成本与对象大小(大对象改排下标)。
- 核内存与结果:确认
stable_sort临时缓冲峰值可接受,并用小样本断言is_sorted、is_sorted_until或分区关系。
最小自检任务
给定下面的数据结构和比较器,回答四个问题:
- 比较器是否满足排序算法需要的严格弱序?
- 只输出分数最高的 3 条且要求这 3 条内部按分数降序时,应选哪个算法?
- 只求第 3 名分数阈值时,应选哪个算法?
- 若同分记录必须保留原输入顺序,应怎样改调用或比较器?
struct ScoreRecord {
std::string name;
int score;
int seq;
};
bool comp(const ScoreRecord& left, const ScoreRecord& right) {
return left.score >= right.score;
}
本章知识点总结
- 结果强度选型
按后续消费范围选择
std::sort(全有序)、std::stable_sort(稳定全有序)、std::partial_sort(前 K 有序)或std::nth_element(第 N 分界与分区)。 - 有序性检测
std::is_sorted用于快速校验前置条件,std::is_sorted_until返回首个破序断点,二者必须与排序及后续算法使用同一比较器。 - 迭代器与平凡边界
四个重排算法要求随机访问迭代器(链表应调用成员
sort);检测算法只需前向迭代器,且空区间与单元素区间默认有序。 - 实现策略与复杂度
sort常基于 introsort($O(N \log N)$),stable_sort基于归并(缓冲充足 $O(N \log N)$,不足退化至 $O(N \log^2 N)$),partial_sort约 $N \log K$,nth_element平均 $O(N)$。 - 严格弱序契约
比较器必须满足非自反(
comp(a, a) == false)、互斥、传递与等价传递,且保持纯只读无状态;<=、>=或可变状态会破坏排序语义。 - 同分与多字段策略
保留输入时间线优先
std::stable_sort,按业务字段打破同分则写词典序复合比较器配std::sort。 - 移动成本与并行边界
大对象可改排下标、指针或
std::reference_wrapper降低移动开销;并行策略下比较器必须可并发调用且抛异常可能触发std::terminate。