C++中std：：sort函数介绍和使用场景

前言std::sort是 C 标准库最常用的算法之一声明在algorithm里作用是把一个区间按升序或自定义规则重新排列。它接受一对随机访问迭代器默认用operator比较元素也可以传入自定义比较器。日常代码里排序std::vector、内置数组、std::string的字符几乎都用它。关于它有两个流传很广的误解。第一个是「std::sort是稳定排序」——并不是。元素相等时它们的相对次序不保证保持需要稳定就改用std::stable_sort。第二个是「比较器随便写只要大小关系差不多就行」——比较器必须满足严格弱序strict weak ordering写成或在标准层面是未定义行为undefined behavior, UB在某些实现上会直接越界访问。本文先讲std::sort的接口与复杂度保证再说明比较器的数学要求然后按使用场景给出示例普通升序降序、结构体多关键字排序、只需要前若干名、只需要中位数、以及对链表排序。最后列出实际写代码时最常见的错误。一、接口与复杂度标准给出的两个重载是形式说明std::sort(first, last)用operator比较升序std::sort(first, last, comp)用二元谓词comp比较两个版本都返回void排序是原地进行的。要求[first, last)是有效区间迭代器至少是随机访问迭代器random access iterator元素可交换swappable比较器对元素类型构成严格弱序。复杂度方面C11 起标准要求std::sort至多进行 O(N log N) 次比较其中 N 是区间长度。C11 之前只写了「平均约 N log N」没有最坏情况的硬性上界。这一点常被忽略今天的标准库实现通常能保证最坏 O(N log N)是因为普遍采用内省排序introsort而不是标准规定了某一种算法。内省排序的思路是以快速排序为主体用递归深度作监控深度超过约 2×log₂N 时切换成堆排序避免快排退化成 O(N²)小区间常见阈值是十几个元素改用插入排序减少函数调用和递归开销。需要强调这只是主流实现的做法标准并未规定必须如此具体阈值和行为属于实现细节不能写进可移植代码的假设里。另外std::sort不分配额外内存实现可能用少量栈空间而std::stable_sort在额外内存不足时可能退化为 O(N log²N) 次比较。这也是「默认用 sort需要稳定才用 stable_sort」的原因之一。二、比较器为什么必须满足严格弱序设比较器为comp严格弱序要求对区间内任意元素 a、b、c 满足非自反comp(a, a)必须为假。非对称若comp(a, b)为真则comp(b, a)必须为假。传递若comp(a, b)与comp(b, c)都为真则comp(a, c)为真。等价关系传递若 a 与 b 等价互相都不小于对方b 与 c 等价则 a 与 c 等价。a b违反第一条comp(a, a)为真。排序算法内部会据此认为元素小于自己划分区间时可能把下标推到边界之外。这种错误不一定立刻崩溃可能只是结果乱序也可能在某个数据规模上越界所以特别难查。正确的写法是只用表达「严格小于」相等时返回false。多关键字排序时把「相等」的分支交给下一个关键字最后一个关键字仍然用严格小于// 适用于 C17bool lessByAgeThenName(const Employee a, const Employee b) {if (a.age ! b.age) {return a.age b.age;}return a.name b.name; // 相等时返回 false符合严格弱序}用std::tie可以把多关键字比较写得紧凑它按成员声明顺序生成一个引用元组元组的operator是逐元素字典序// 适用于 C17bool lessByAgeThenName(const Employee a, const Employee b) {return std::tie(a.age, a.name) std::tie(b.age, b.name);}std::tie返回的是引用元组比较时不会拷贝字符串前提是被比较的成员在比较期间不被修改。比较器本身也不应该修改元素——标准要求谓词不能通过参数施加副作用否则行为未定义。三、典型使用场景场景一基本类型升序与降序// 适用于 C17#include algorithm#include functional#include vectorvoid basicSort(std::vectorint v) {std::sort(v.begin(), v.end()); // 升序用 operatorstd::sort(v.begin(), v.end(), std::greaterint()); // 降序}std::greaterint声明在functional里。用std::greaterC14 起的透明比较器可以省掉模板实参让编译器推导// 适用于 C14 及以上std::sort(v.begin(), v.end(), std::greater());场景二结构体按多个字段排序// 适用于 C17#include algorithm#include string#include tuple#include vectorstruct Employee {std::string name;int age 0;double salary 0.0;};void sortStaff(std::vectorEmployee staff) {std::sort(staff.begin(), staff.end(),[](const Employee a, const Employee b) {if (a.salary ! b.salary) {return a.salary b.salary; // 工资从高到低}return std::tie(a.age, a.name) std::tie(b.age, b.name);});}这里第一关键字是降序用后面两个是升序用混用没有问题只要每个分支都表达严格序。浮点数比较要注意如果数据里可能有 NaNa.salary ! b.salary与的组合不再构成严格弱序因为 NaN 与任何值包括自己都不相等也不小于。含 NaN 的数据应先清洗或者用std::isnan显式定义 NaN 的排序位置。场景三只要前 k 名对整个区间排序是 O(N log N)如果只关心最小的 k 个std::partial_sort更合适// 适用于 C17#include algorithm#include vectorstd::vectorint topK(std::vectorint v, std::size_t k) {if (k v.size()) {k v.size();}std::partial_sort(v.begin(), v.begin() static_caststd::ptrdiff_t(k), v.end());v.resize(k);return v;}partial_sort(first, middle, last)保证[first, middle)是整体中最小的若干元素且已排好序其余元素的顺序未指定。复杂度约 O(N log k)。场景四只要中位数或第 k 小// 适用于 C17#include algorithm#include vectorint median(std::vectorint v) {const std::size_t mid v.size() / 2;std::nth_element(v.begin(), v.begin() static_caststd::ptrdiff_t(mid), v.end());return v[mid];}std::nth_element平均 O(N)保证位置mid上的元素就是「如果整体排序后该位置应有的元素」并且它左边的都不大于它、右边的都不小于它但两侧内部无序。调用前要确保容器非空。场景五链表排序std::sort需要随机访问迭代器std::list的迭代器是双向的直接传进去编译不过。链表应用成员函数sort// 适用于 C17#include listvoid sortList(std::listint lst) {lst.sort(); // 升序lst.sort(std::greaterint()); // 降序}std::list::sort是稳定排序且不要求元素可随机访问通常用归并实现。std::forward_list也有成员sort。场景六稳定排序当相等元素的原始次序有业务含义时用std::stable_sort// 适用于 C17#include algorithm#include vectorvoid stableByScore(std::vectorEmployee staff) {std::stable_sort(staff.begin(), staff.end(),[](const Employee a, const Employee b) {return a.salary b.salary;});}如果先按姓名排过一遍再按工资稳定排序工资相同的员工之间仍保持姓名的次序这就是稳定排序的用途。四、几个容易混淆的边界std::sort不会改变元素的个数也不会让迭代器失效元素被移动但容器本身不重新分配。不过如果比较器捕获了外部状态并在排序过程中修改它或者比较器依赖的元素在排序过程中被其他线程修改行为都是未定义的。对内置数组也可以直接用// 适用于 C17int a[] {3, 1, 4, 1, 5};std::sort(std::begin(a), std::end(a));std::begin/std::end在iterator里对数组返回指针。用a, a 5也可以但长度写死容易出错。对std::string排序字符// 适用于 C17#include algorithm#include stringvoid sortChars(std::string s) {std::sort(s.begin(), s.end());}std::string::iterator是随机访问迭代器满足要求。按字节排序对 ASCII 没问题对 UTF-8 中文则是按字节值排不会得到拼音序这一点要清楚。关联容器std::map、std::set自身按比较器维持有序不能对它们调用std::sort也没有必要。std::unordered_map的元素类型是std::pairconst Key, T键是 const 的不可赋值无法排序要排序只能把元素拷贝到std::vector再排。常见坑点1. 比较器写成❌[](int a, int b) { return a b; }—— 违反非自反性是 UB。 ✅[](int a, int b) { return a b; }。2. 以为 sort 稳定❌ 先按姓名排序再按分数排序指望同分者保持姓名序。 ✅ 需要保持就用std::stable_sort或把姓名作为第二关键字。3. 对 list 调用 std::sort❌std::sort(lst.begin(), lst.end());—— 迭代器不是随机访问编译失败。 ✅lst.sort();。4. 比较器里修改元素❌[](Employee a, Employee b) { a.age 1; return a.age b.age; }—— 副作用导致行为未定义参数也不该是非常量引用。 ✅ 比较器参数用const只读不写。5. 浮点 NaN 参与比较❌ 直接对可能含 NaN 的std::vectordouble排序比较器不构成严格弱序。 ✅ 先过滤或替换 NaN或在比较器里显式规定 NaN 排在最后。6. 对 unordered_map 直接排序❌std::sort(um.begin(), um.end());—— 元素键为 const不可赋值且迭代器不满足要求。 ✅ 把std::pair拷贝进std::vector再按值排序。7. 降序时混用和❌ 多关键字里一处写a.x b.x另一处写a.y b.y。 ✅ 每个关键字都只用严格比较降序用升序用。8. 忘记algorithm❌ 只包含vector就调用std::sort换一个标准库实现可能编译失败。 ✅ 显式包含algorithm用到std::greater时再包含functional。总结需求选择复杂度比较次数普通全排序std::sort最坏 O(N log N)保持相等元素次序std::stable_sort有额外内存时 O(N log N)只要前 k 个std::partial_sort约 O(N log k)只要第 k 位std::nth_element平均 O(N)链表排序std::list::sortO(N log N)关联容器无需排序插入时维护std::sort的接口只有两个重载难点几乎全在比较器上只用严格小于、不修改元素、不引入 NaN 这类破坏严格弱序的值。选对算法同样重要——只需要前几名或中位数时partial_sort与nth_element能省下大量不必要的工作而需要稳定时应当明确改用stable_sort不要指望sort碰巧保持次序。