前言std::sort定义在algorithm中是 C 最常用的排序算法。它的接口只有两个核心参数——首迭代器和尾后迭代器——再加一个可选的比较器。看似简单但围绕它有大量误用比较器写成、对std::list调用、以为排序稳定、在比较器里修改元素。这些错误有的直接编译失败有的则是未定义行为undefined behavior, UB运行时才以奇怪的方式暴露。先把几个事实说清楚。std::sort要求随机访问迭代器因此std::vector、std::array、普通数组、std::deque可以用std::list、std::forward_list不行它们有成员函数sort。它不保证稳定需要稳定排序用std::stable_sort。它的比较次数是 O(N log N)但具体实现内省排序、混合算法由标准库决定标准不规定。比较器必须满足严格弱序strict weak ordering违反它是 UB不是“结果可能不理想”。本文覆盖基本用法、自定义比较器、结构体多关键字排序、稳定性与部分排序并给出常见错误的正确写法。示例以 C17 为基准。一、基本用法最简单的形式是对一个区间升序排序// 适用于 C17#include algorithm#include array#include iostream#include vectorint main(){std::vectorint v{5, 2, 9, 1, 5, 6};std::sort(v.begin(), v.end()); // 升序std::arrayint, 4 a{4, 3, 2, 1};std::sort(a.begin(), a.end()); // 对 std::array 同样适用int raw[5] {5, 4, 3, 2, 1};std::sort(raw, raw 5); // 普通数组用指针作为迭代器for (int x : v) {std::cout x ;}std::cout \n;return 0;}first与last构成左闭右开区间[first, last)last是尾后位置不参与排序。对空区间或只有一个元素的区间调用sort是合法的什么也不做。降序有两种常见写法// 适用于 C17#include algorithm#include functional#include vectorvoid sort_desc(std::vectorint v){std::sort(v.begin(), v.end(), std::greaterint{});// 或std::sort(v.begin(), v.end(), [](int a, int b) { return a b; });}std::greaterint在functional中。C14 起可以写std::greater{}让模板实参由调用时推导省去重复写类型。二、比较器的语义比较器comp(a, b)返回true表示“a 应该排在 b 前面”。它必须满足严格弱序可以概括为四条对任意 acomp(a, a)为false非自反若comp(a, b)为真则comp(b, a)为假非对称若comp(a, b)且comp(b, c)则comp(a, c)传递不可比较的元素之间满足传递性等价关系传递。写成a b违反第 1 条comp(a, a)会返回true。标准库的排序实现依赖“小于”语义做划分和二分会让它把相等元素来回搬运甚至越界访问。这是 UB不是“排序结果不稳定”这么轻。// 适用于 C17#include algorithm#include vectorvoid wrong(std::vectorint v){std::sort(v.begin(), v.end(),[](int a, int b) { return a b; }); // UB}void right(std::vectorint v){std::sort(v.begin(), v.end(),[](int a, int b) { return a b; }); // 严格弱序}比较器还应当是纯函数不修改被比较的元素不依赖会在排序过程中变化的外部状态。如果比较器读取一个全局计数器并在内部自增排序过程中元素间的相对顺序会随调用次序改变同样破坏严格弱序。三、结构体与多关键字排序对结构体排序比较器要明确“主键、次键”// 适用于 C17#include algorithm#include iostream#include string#include tuple#include vectorstruct Person {std::string name;int age;double score;};int main(){std::vectorPerson people{{Ann, 30, 88.5},{Bob, 25, 92.0},{Cid, 30, 75.0},{Dan, 25, 92.0}};// 按年龄升序年龄相同按分数降序再按姓名升序std::sort(people.begin(), people.end(),[](const Person a, const Person b) {if (a.age ! b.age) {return a.age b.age;}if (a.score ! b.score) {return a.score b.score;}return a.name b.name;});// 等价的简洁写法std::tie 构造可比较的元组std::sort(people.begin(), people.end(),[](const Person a, const Person b) {return std::tie(a.age, b.name) std::tie(b.age, b.name);});for (const auto p : people) {std::cout p.name p.age \n;}return 0;}std::tie生成左值引用组成的tupletuple的比较是按元素字典序进行的因此std::tie(a.age, a.name) std::tie(b.age, b.name)等价于“先比年龄再比姓名”。注意不能把“降序字段”和“升序字段”混在一个tie里因为tuple的每个元素都按同一种方向比较混合方向时还是手写分支更清楚。如果结构体本身定义了operator可以直接调用无比较器版本// 适用于 C17struct Point {int x;int y;};bool operator(const Point a, const Point b){return a.x ! b.x ? a.x b.x : a.y b.y;}四、稳定性、部分排序与容器选择稳定性std::sort不保证相等元素的相对顺序。如果业务要求“先按分数排再按姓名排且同分者保持原有顺序”应使用std::stable_sort// 适用于 C17#include algorithm#include string#include vectorstruct Record {std::string name;int score;};void sort_stable(std::vectorRecord v){std::stable_sort(v.begin(), v.end(),[](const Record a, const Record b) {return a.score b.score;});}stable_sort的比较次数同样是 O(N log N)但可能需要额外的临时存储具体实现和内存用量由标准库决定标准不规定。部分排序只需要前 K 个元素有序时不必对整个区间排序// 适用于 C17#include algorithm#include cstddef#include vectorvoid top_k(std::vectorint v, std::size_t k){if (k v.size()) {std::partial_sort(v.begin(), v.begin() static_caststd::ptrdiff_t(k), v.end());}}partial_sort(first, middle, last)之后[first, middle)是整体最小的 K 个元素且已排序[middle, last)的顺序未指定。如果只关心“第 K 小是谁”而不关心前面是否有序用std::nth_element平均复杂度是线性的。容器选择容器/区间能否用std::sort替代方案std::vector可以无std::array可以无普通数组可以指针作迭代器无std::deque可以无std::list不可以非随机访问成员sort()std::forward_list不可以成员sort()std::map/std::set不需要插入时自动有序对std::list调用std::sort会在编译期报错因为它的迭代器不满足随机访问要求。std::list::sort是成员函数稳定复杂度 O(N log N)并且只重新链接节点不移动元素。常见坑点❌ 比较器写return a b;。✅ 必须是严格弱序用a b会让comp(a, a)为真属于 UB。❌ 比较器依赖并在内部修改外部状态。✅ 比较器应是纯函数需要附加信息就作为参数传入不要在比较过程中改变它。❌ 对std::list或std::forward_list调用std::sort。✅ 用它们的成员sort()std::sort要求随机访问迭代器。❌ 认为std::sort稳定依赖相等元素的原有顺序。✅ 需要稳定用std::stable_sortstd::sort只保证有序不保证相等元素的相对次序。❌ 在比较器里用a.score - b.score的符号做判断整数相减可能溢出。✅ 写成a.score b.score或a.score b.score不要用减法制造溢出风险。❌ 对含 NaN 的浮点数组直接用排序。✅ NaN 与任何值比较都为假破坏严格弱序。先把 NaN 过滤或定义明确的排序规则。❌ 排序后继续使用指向原元素的迭代器以为它还指向原来的值。✅std::sort会重排元素迭代器本身仍有效对vector不重新分配但指向的位置内容已变。❌ 只对前 K 个元素排序却调用了完整的std::sort。✅ 用std::partial_sort或std::nth_element避免做多余的工作。总结用法写法说明升序std::sort(v.begin(), v.end())默认operator降序std::sort(v.begin(), v.end(), std::greater{})需要functional自定义std::sort(begin, end, comp)comp必须严格弱序稳定std::stable_sort(...)保留相等元素相对顺序前 K 个std::partial_sort(first, middle, last)只保证前段有序第 K 小std::nth_element(...)平均线性链表lst.sort()成员函数稳定std::sort的难点不在调用而在比较器只要保证它满足严格弱序、不修改元素、不依赖变化的状态剩下的交给标准库即可。需要稳定就用stable_sort需要部分有序就用partial_sort不要把不同需求都压给同一个函数。