Skip to main content

Chapter 28: Sorting Algorithms

核心问题与阅读主线

本章导读5 个核心小节 · 附自检与总结

排序算法重排半开区间 [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_sortedbool(全区间是否有序)前向迭代器生产入口断言或前置条件校验
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::sortintrosort(快排 + 深度受限堆排 + 小区间插排)无需临时归并缓冲不稳定是否计算 last - first 与递归深度上限
std::stable_sort归并排序(等价时优先输出左侧)申请临时缓冲,不足时退化为高比较路径稳定(来自归并取左)是否有缓冲申请与等价取左合并分支
std::partial_sort大小为 $K$ 的堆选择 + 堆展开原地堆调整不稳定;仅前 K 有序是否先对 [first, middle) 建堆再扫尾部
std::nth_elementintroselect(单侧分区收缩)无需临时归并缓冲不稳定;仅第 N 位及分区分区后是否仅保留包含 nth 的一侧子区间

28.4 comparator 与 strict weak ordering​

对比较器 comp(a, b) 的工作定义是:返回 true 时表示 a 应排在 b 之前。标准库排序算法要求比较器满足严格弱序(strict weak ordering),使算法能把元素划分为有序等价类并在分区、交换与合并时维持一致结论。

严格弱序必须满足四条可检查条件:

  1. 非自反性:对任意元素 a,comp(a, a) 必须为 false。
  2. 互斥性:若 comp(a, b) 为 true,则 comp(b, a) 必须为 false。
  3. 传递性:若 comp(a, b) 与 comp(b, c) 均为 true,则 comp(a, c) 必须为 true。
  4. 等价传递性:由 !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。并行执行策略还额外要求比较器无共享可变状态、可并发调用且结果稳定。

工程选型检查顺序:

  1. 定消费范围:区分全区间、前 K 有序、第 N 分界或仅检测前提。
  2. 定稳定性:判断是否必须保留等价元素的原相对顺序。
  3. 查迭代器能力:重排算法需随机访问(list 用成员 sort),检测只需前向。
  4. 验比较器契约:确认严格弱序且只读无状态(并行策略需可并发)。
  5. 估规模与移动开销:权衡 $N$、$K$、比较成本与对象大小(大对象改排下标)。
  6. 核内存与结果:确认 stable_sort 临时缓冲峰值可接受,并用小样本断言 is_sorted、is_sorted_until 或分区关系。

最小自检任务​

动手自检先独立判断

给定下面的数据结构和比较器,回答四个问题:

  1. 比较器是否满足排序算法需要的严格弱序?
  2. 只输出分数最高的 3 条且要求这 3 条内部按分数降序时,应选哪个算法?
  3. 只求第 3 名分数阈值时,应选哪个算法?
  4. 若同分记录必须保留原输入顺序,应怎样改调用或比较器?
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。