写结构体排序绕不开 sort()。这篇文章我直接讲 C 里 sort() 配合结构体排序的完整玩法从基础用法到进阶技巧从排序稳定性到比较函数怎么写才不出错一次性说透。先给个结论结构体排序的核心不是 sort() 本身而是“怎么告诉 sort() 按什么规则排”。C 的 sort() 默认按 运算符排所以你要么给结构体定义 要么给 sort() 传一个比较函数或 lambda二选一。搞懂这一点剩下的都是细节。我当年刚接触算法竞赛的时候在这上面栽过不少跟头。比如定义一个结构体存学生的姓名和成绩想按成绩从高到低排结果排完发现顺序完全不对或者编译器报一堆看不懂的错。后来把 sort() 的底层逻辑和结构体的比较方式彻底啃了一遍才算真正做到“一次写对排查无忧”。这篇文章就把这些经验全部拆开讲。1. sort() 到底怎么工作1.1 快速认识 sort()三个参数几十行代码sort() 是 C 标准库algorithm里的模板函数最常用的调用方式是sort(first, last, comp);first指向序列起始的迭代器或指针。last指向序列末尾的迭代器或指针注意是左闭右开也就是[first, last)。comp可选的比较器用来定义“什么算小于”。不传默认用。对数组排序就是int a[10] {5, 2, 8, 1, 9}; sort(a, a 5); // 对前5个元素排升序对 vector 排序就是vectorint v {5, 2, 8, 1, 9}; sort(v.begin(), v.end());这里强调一个关键点sort() 是不稳定排序。所谓的稳定是指排序后相同关键字的元素之间原本的相对顺序是否保持。std::sort在这个标准里不保证稳定性实际上它通常实现为内省排序Introspective Sort是快速排序、堆排序、插入排序的混合体。如果你的应用场景需要稳定排序那就用std::stable_sort它基于归并排序实现代价是额外空间和时间稍微多一点。1.2 为什么排序必须“告诉” sort() 排序规则sort()的默认行为是升序依赖元素类型支持运算符。基础类型int、double、char天然支持所以sort(a, an)直接能用。但结构体没有内置的大小概念如果不做任何处理sort(vec.begin(), vec.end())会直接编译报错。举个例子struct Student { string name; int score; };Student之间能比大小吗按姓名还是按分数语言不知道怎么比所以要么你自己定义要么给 sort() 传递外部规则。理解了这一步结构体排序的框架就有了。实际项目中“按什么排序”往往是具体业务决定的。比如教务系统里学生按总成绩排序比赛榜单里选手按解题数排再按罚时排。没有“正确的大小”一说只有“当前业务需要的大小”。2. 结构体排序的四种实现方案2.1 方案一重载小于运算符最简单直接给结构体重载然后 sort() 直接用默认形式。#include bits/stdc.h using namespace std; struct Student { string name; int score; bool operator(const Student other) const { return score other.score; // 按分数升序 } }; int main() { vectorStudent stu { {Alice, 88}, {Bob, 95}, {Cindy, 76}, {David, 95} }; sort(stu.begin(), stu.end()); for (auto s : stu) cout s.name s.score endl; return 0; }输出Cindy 76 Alice 88 Bob 95 David 95这段代码里注意几个点。第一operator的参数是const Student函数本身也是 const这是为了能在常量对象上调用。第二返回值是bool含义是“当前对象是否排在 other 前面”。如果要降序只需要把return score other.score改成return score other.score。这个方案的优点是简单、直观代码量少。缺点是一个结构体只能定义一种排序规则。如果业务既要“按分数排”又要“按姓名排”重载运算符就满足不了了因为只有一个。这时就要用到后面两种方案。2.2 方案二自定义比较函数灵活可控自定义比较函数的本质是写一个返回值是bool、接收两个const Student参数的普通函数作为comp传给 sort()。struct Student { string name; int score; }; // 按分数降序 bool cmpByScoreDesc(const Student a, const Student b) { return a.score b.score; } // 按姓名升序 bool cmpByName(const Student a, const Student b) { return a.name b.name; } sort(stu.begin(), stu.end(), cmpByScoreDesc); sort(stu.begin(), stu.end(), cmpByName);比较函数的返回值语义必须准确把握cmp(a, b)返回true表示 a 应该排在 b 前面。搞反了就变成反序这是最常见的低级错误。我当时有一个实用的记忆方法return 后面的表达式哪个值大哪个就排前面或前面提到的含义按你设定的规则。更严谨的说法是比较函数必须严格定义“a 是否先于 b”并且要满足“严格弱序”的要求。这个“严格弱序”听着玄乎但核心就三条cmp(a, a)必须为false。如果cmp(a, b)为true那么cmp(b, a)必须为false。传递性若cmp(a, b)和cmp(b, c)均为true则cmp(a, c)必须为true。大多数情况下直接用a.xxx b.xxx或a.xxx b.xxx天然满足。但如果你写return a.score b.score带了等号第二个规则就被破坏了sort() 在面临相同元素时行为会变成未定义。后续我会专门开一章节讲这个坑。2.3 方案三lambda 表达式现代 C 推荐C11 引入了 lambda不需要单独写函数在调用点直接定义排序规则尤其适合一次性排序。sort(stu.begin(), stu.end(), [](const Student a, const Student b) { return a.score b.score; // 分数降序 });这段代码和前面的自定义函数效果完全一样但可读性提升了一个档次。你一眼就能看到排序规则是什么。如果多个地方要用同一排序规则可以把这个 lambda 存成变量或者仍然用自定义函数。lambda 的另一个优势是它可以捕获上下文中的变量参与比较。比如按“和时间戳的差值”排序时间戳是外部变量普通函数做不到lambda 可以int target 100; sort(stu.begin(), stu.end(), [target](const Student a, const Student b) { return abs(a.score - target) abs(b.score - target); });2.4 方案四仿函数重载 operator() 的类仿函数Functor是重载了operator()的类对象它看起来像函数但有类型、有状态。适合排序规则复杂、需要携带参数的场景。struct CmpByScoreDesc { bool operator()(const Student a, const Student b) const { return a.score b.score; } }; sort(stu.begin(), stu.end(), CmpByScoreDesc());和普通函数相比仿函数最大的优点是可以在对象中存储状态。比如按指定的字段排序字段名称通过构造参数传入struct CmpByField { string field; CmpByField(const string f) : field(f) {} bool operator()(const Student a, const Student b) const { if (field name) return a.name b.name; else return a.score b.score; } }; sort(stu.begin(), stu.end(), CmpByField(score));这种写法在生产代码里很常见尤其是构建通用排序组件时。实际上 STL 中的std::less、std::greater就是标准库提供的仿函数直接可以用在 sort() 上sort(v.begin(), v.end(), greaterint()); // 降序3. 多关键字排序先比啥再比啥3.1 核心写法和“优先级”逻辑真实业务里几乎没有单字段排序。比赛要“解题数多的排前面解题数相同则罚时少的排前面”成绩单要“总分高的排前面总分相同则语文成绩高的排前面”商品列表要“销量多的排前面销量相同则价格低的排前面”。这种就是多关键字排序。写法不复杂核心思路先比第一个字段如果不同就直接返回结果相同则继续比第二个字段依次类推。struct Team { string name; int solved; // 解题数 int penalty; // 罚时 }; bool cmpTeam(const Team a, const Team b) { if (a.solved ! b.solved) return a.solved b.solved; // 解题数降序 return a.penalty b.penalty; // 罚时升序 }如果规则再多一层就继续嵌套if (a.solved ! b.solved) return a.solved b.solved; if (a.penalty ! b.penalty) return a.penalty b.penalty; return a.name b.name; // 最终按队名升序保证唯一顺序这种写法非常直观也容易检查。给个建议如果排序规则有三级以上建议封装成独立的比较函数并加上注释说明每层规则否则两周回来看代码自己也能绕晕。3.2 用 tuple 简化多关键字比较C11 之后可以用 tuple 做多关键字比较代码更紧凑。这里的关键技巧是需要逆序的字段取负因为 tuple 默认按升序比较。#include tuple bool cmpTeam(const Team a, const Team b) { // solved 降序取 -a.solved // penalty 升序直接写 // name 升序直接写 return tupleint, int, string(-a.solved, a.penalty, a.name) tupleint, int, string(-b.solved, b.penalty, b.name); }或者用 C11 的std::tie配合对逆序字段取负bool cmpTeam(const Team a, const Team b) { return tie(-a.solved, a.penalty, a.name) tie(-b.solved, b.penalty, b.name); }刚接触 tuple 的人可能会觉得这种写法“不够直白”但实际用起来非常方便尤其在字段多、规则不算复杂时两三行就能写完。不过前提是你要清楚 tuple 的字典序比较规则否则容易翻车。3.3 多关键字排序的典型坑多关键字排序最容易犯的错是写成了“按第一个字段排完后再按第二个字段整个重排一次”也就是sort(stu.begin(), stu.end(), cmpByScoreDesc); sort(stu.begin(), stu.end(), cmpByName);这样最终只会按 name 排序前面按 score 排的结果被覆盖了。原因很简单sort() 本身不稳定第二次排序重新排列了所有元素不会保留第一次的次级顺序。要得到“先按 name内部再按 score”的效果必须是单个比较函数内处理多级规则而不是多次 sort()。除非你用stable_sort那么可以“先按次级字段排再按主字段排”因为稳定排序会保留上一次排序的相对顺序stable_sort(stu.begin(), stu.end(), cmpByName); // 先按姓名 stable_sort(stu.begin(), stu.end(), cmpByScoreDesc); // 再按分数稳定所以同分内保序这里要注意调用顺序主排序字段的 sort 放在最后。实际使用中能用单次排序解决就不要搞两次逻辑更清晰性能也更好。4. 实战结构体数组与 vector 的排序完整案例4.1 综合案例比赛排行榜需求有若干队伍每支队伍有队名、解题数、罚时。排行榜规则解题数多的排前面。解题数相同罚时少的排前面。解题数和罚时都相同队名 lexicographically 小的排前面。先定义结构体再写比较函数#include iostream #include algorithm #include vector #include string using namespace std; struct Team { string name; int solved; int penalty; }; bool cmpTeam(const Team a, const Team b) { if (a.solved ! b.solved) return a.solved b.solved; if (a.penalty ! b.penalty) return a.penalty b.penalty; return a.name b.name; } int main() { vectorTeam teams { {Red, 5, 120}, {Blue, 6, 100}, {Green, 5, 90}, {Yellow, 6, 110}, {Purple, 4, 80} }; sort(teams.begin(), teams.end(), cmpTeam); for (auto t : teams) { cout t.name t.solved t.penalty endl; } return 0; }输出Blue 6 100 Yellow 6 110 Green 5 90 Red 5 120 Purple 4 80这个输出完全符合规则。Blue 和 Yellow 解题数都是 6Blue 罚时 100 更少排前面Green 和 Red 解题数都是 5Green 罚时 90 更少排前面。4.2 使用 lambda 的等价写法同样的逻辑用 lambda 更紧凑sort(teams.begin(), teams.end(), [](const Team a, const Team b) { if (a.solved ! b.solved) return a.solved b.solved; if (a.penalty ! b.penalty) return a.penalty b.penalty; return a.name b.name; });实测下来现代 C 项目里 lambda 的使用频率已经超过了自定义函数因为它在调用点直接可见不需要跳到另一个地方看函数实现。但如果你写的排序规则会被多个地方复用或者规则特别长建议还是提取成独立函数。4.3 从数组到 vector 的注意点老式 C 风格数组也能用 sort()但要小心数组长度计算Team arr[100]; int n 0; // ... 填充 arr 和 n sort(arr, arr n, cmpTeam);arr n就是末尾迭代器注意这里是“首地址 元素个数”而不是“首地址 数组总大小”。我曾见过有人写成sort(arr, arr 100, cmpTeam)结果把未初始化的元素也排进去输出一堆乱七八糟的数据。特别是当结构体里有string这种非平凡类型时未初始化的对象甚至可能直接崩溃。用 vector 就没这个问题v.begin()和v.end()始终指向有效范围。所以日常开发我基本都是 vector 优先只有性能敏感且数据量巨大的老代码才考虑 C 数组。5. 比较函数怎么写才正确严格弱序5.1 strict weak ordering 的本质sort() 要求比较函数是严格弱序。这个概念是理解排序正确性的关键。严格弱序可以用几个条件来理解cmp(a, a)恒为false。也就是说“任何元素都不小于自己”。如果cmp(a, b)为true那么cmp(b, a)必须为false。这叫反对称性。传递性若cmp(a, b)为true且cmp(b, c)为true则cmp(a, c)必须为true。等价关系的传递性如果cmp(a, b)和cmp(b, a)都为false说明 a 和 b 等价equivalent不是 necessarily 相等。如果 a 等价 bb 等价 c则 a 必须等价 c。为什么要求这么苛刻因为 sort() 的内部算法快速排序的高效实现依赖这些性质来保证元素被正确分区。一旦你写的比较函数违反这些规则sort() 的行为就不是“排错顺序”这么简单了它可能陷入死循环、越界访问、直接崩溃或者只是纯粹地输出错误结果。5.2 常见错误在比较函数里用 或 这是新手最容易犯的错误之一。// 错误示范 bool badCmp(const Student a, const Student b) { return a.score b.score; // 用了 }sore b.score意味着在 a 和 b 分数相等时badCmp(a, b)返回 true同时badCmp(b, a)也返回 true。这直接违反了“反对称性”。sort() 拿到这种比较器等于在告诉它“两个相等元素互相比对方小”结果无法预期。某些 STL 实现下可能刚好能用但这是运气不是正确。换一个编译器的优化选项结果可能就变了。正确的降序写法是bool goodCmp(const Student a, const Student b) { return a.score b.score; // 严格大于 }记住一条口诀比较函数里只能出现严格小于或严格大于永远不能出现 或 。5.3 浮点数排序的特殊注意结构体里有double字段时直接比较没问题return a.price b.price;但如果浮点数是通过运算得来的可能出现 NaNNot a Number。NaN 参与比较时、全都返回 false会导致排序行为异常。如果业务上有可能出现 NaN建议在比较前把 NaN 单独处理例如bool cmpDouble(double a, double b) { if (isnan(a)) return !isnan(b); // NaN 排在最后 if (isnan(b)) return false; return a b; }这种细节在普通业务里很少遇到但做数据处理、科学计算时一次 NaN 引发的诡异排序结果会让你排查到怀疑人生。6. 常见问题与避坑指南6.1 sort() 需要引入什么头文件sort()定义在algorithm头文件里。使用时#include algorithm如果用了std::vector还要#include vector有些代码习惯写#include bits/stdc.h这是 GNU C 的扩展头文件竞赛常用但工程代码里不建议用。原因很简单它不是 C 标准的一部分在 MSVC 等编译器上直接报错。为了代码可移植性老老实实写明确头文件。6.2 结构体里的 string 排序没问题吗没问题。std::string已经重载了运算符比较的是字典序直接用即可。但有一个性能相关的点要留意当结构体很大包含大数组、多个 string 等时sort() 排序期间会复制结构体。复制成本高排序就慢。如果数据量大且结构体臃肿一种优化方案是排序索引数组下标vectorStudent stu ...; vectorint idx(stu.size()); for (int i 0; i (int)idx.size(); i) idx[i] i; sort(idx.begin(), idx.end(), [](int a, int b) { return stu[a].score stu[b].score; }); // 按 idx 的顺序输出 stu[idx[i]]这样排序时只移动 int不拷贝整个 Student 对象性能明显提升。实测下来1MB 级别的结构体数组排序时间能差出几倍。6.3 sort() 和 qsort() 怎么选C 语言里有qsort()C 里兼容存在。两者差别非常大对比点sort()qsort()头文件algorithmcstdlib比较器类型函数/仿函数/lambda函数指针类型安全编译期检查需要 void*无类型检查性能实测相当内省排序通常更快快排稍慢内联优化比较器可内联函数指针不可内联写过 qsort 的人都知道要写一个int (*)(const void*, const void*)的比较函数里面对const void*做强制类型转换非常繁琐且不安全。C 代码里用qsort属于“自找麻烦”建议统一用sort()。我自己的经验是只要编译环境支持 C11就完全不用考虑 qsort。6.4 大小写敏感与多语言排序std::string的是比较 ASCII 码所以大写字母都比小写字母靠前。如果业务需要不区分大小写排序需要自己实现规则bool cmpStringNoCase(const string a, const string b) { string lowerA a, lowerB b; transform(lowerA.begin(), lowerA.end(), lowerA.begin(), ::tolower); transform(lowerB.begin(), lowerB.end(), lowerB.begin(), ::tolower); return lowerA lowerB; }注意::tolower的调用形式它是 C 标准库函数直接传字符可能有符号问题建议先转成unsigned char。这种细节坑过很多新手。6.5 如何排查排序结果“看起来不对”排序出了问题我一般是按这个顺序排查检查是否是稳定排序的要求业务是否要求相等元素保持原序是就用stable_sort。检查比较函数是否严格满足弱序有没有出现或cmp(a,a)有没有可能返回 true检查字段类型字段是 int 还是 doubledouble 有没有可能出现 NaN检查计算过程排序字段是否在排序前被修改过结构体副本的字段是否正确用极小数据量单步调试构造 3~4 个元素的测试样例手动推演一遍跟程序输出对比。排查问题不难难的是“不亲自踩一遍就不知道”。我当年把 sort() 的底层代码翻开看过一遍之后对这些坑的记忆就再也忘不掉了。7. 排序之后的扩展应用去重和查找7.1 排序后元素的唯一性与 unique()排序之后经常要做去重。C 标准库提供std::unique把相邻重复元素“移到”末尾返回新逻辑结尾的迭代器。配合erase可以真正删除sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());这里有一个很容易忽略的前提unique只对相邻的重复元素有效所以必须先排序。如果是结构体需要保证结构体已经重载了operator或者提供等效判断unique才能正确工作。比较常见的场景是“按某个字段去重”。比如一批数据里要按学号去重保留最高分记录思路是先按学号和分数排序再手动去重或者用 unique 自定义判等。注意unique不能用operator之外的比较器只能靠相等判断所以按字段去重时常常得手写循环。7.2 排序后二分查找lower_bound 与 upper_bound结构体排序后还可以用二分查找快速定位元素。std::lower_bound和std::upper_bound的用法很直接// 前提vectorStudent 按 score 升序排列 auto it lower_bound(stu.begin(), stu.end(), targetScore, [](const Student s, int val) { return s.score val; });这里 lambda 的写法是“第一个参数是容器元素第二个参数是要查找的值”返回true表示元素“小于” target。这个位置就是第一个 score 不小于 target 的元素下标。upper_bound同理找“第一个大于 target”的位置。算法竞赛里这种组合非常常用。比如问题变成“查询某个分数段的学生有哪些”排序 二分就能在 O(log n) 的时间内找到范围而每次排序需要 O(n log n)。如果数据频繁变化还可以用std::set或者std::multiset维护有序序列它们底层是红黑树插入删除都是 O(log n)。7.3 取前 K 个元素partial_sort 与 nth_element如果需求只是“分数前 3 名”或者“中位数”没必要对全部数据排序用partial_sort或nth_element更快// 前3个元素变成最小的3个内部有序 partial_sort(stu.begin(), stu.begin() 3, stu.end(), cmpByScoreAsc); // 第N个位置上的元素是第N小的左边都小于它右边都大于它 nth_element(stu.begin(), stu.begin() k, stu.end(), cmpByScoreAsc);nth_element的平均复杂度是 O(n)partial_sort的复杂度是 O(n log k)都比完整排序的 O(n log n) 快。在大数据量下这几个函数的性能差异非常明显。我实测排序 1000 万个元素的 vectornth_element比完整 sort 快 3~4 倍处理“TopK”类问题很实用。8. 性能考量数据量大了怎么办8.1 sort 的时间复杂度std::sort的平均时间复杂度是 O(n log n)最坏情况下也是 O(n log n)这是内省排序的特点——快速排序递归过深时自动切换到堆排序避免退化为 O(n²)。这是它与老式快排的显著区别。数据量在 10^6 级别sort() 排 int 数组大概几毫秒10^8 级别就需要几百毫秒了。如果数据量继续增大或者排序频繁调用就要考虑优化策略。8.2 大数据量排序的优化手段第一尽量用 vector 而不是 list。list 的 sort 是另一套逻辑性能差很多。第二减少结构体复制。前面提到的排序索引数组就是一个有效手段。第三避免无意义的排序。在排序前想清楚是不是非排序不可能不能用堆priority_queue能不能用计数排序数据的取值范围是否有限如果分数只有 0~100计数排序 O(n) 就完成了没必要用 O(n log n) 的 sort()。第四对于多次按键的排序如果数据基本有序可以考虑insertion_sort但手写容易出错直接用库里的std::sort在小型区间上会自动切入插入排序通常不用自己管。8.3 排序稳定性与 stable_sort 的选择策略stable_sort稳定的代价是空间。如果数据量极大stable_sort会尝试申请额外内存内存不足时退化为归并排序的低效实现性能明显下降。衡量标准很简单没有稳定性需求就是用 sort()有稳定性需求再用 stable_sort()。什么场景需要稳定排序典型例子是“先按姓名排再按分数排”要求同分的人内部保持姓名的顺序。这种场景如果用两次 sort() 会丢失第一遍的信息必须用稳定排序。反过来用 stable_sort 就非常自然stable_sort(stu.begin(), stu.end(), cmpByName); stable_sort(stu.begin(), stu.end(), cmpByScoreDesc);同样的场景也可以用单次 sort() 多关键字完成但从代码清晰度来看稳定排序更符合直觉。9. 我在实际项目中总结的几条实战经验写了这么多年代码用 sort() 排结构体可以说是“日常操作”。最后分享几个从实战里沉淀下来的体会。第一比较函数一定要写得“啰嗦”一点。不要为了追求代码精简把多字段比较压缩成一行返回表达式。宁可多写几个 if也要让逻辑清晰的“一眼可见”。因为在后期调试时“啊这里应该是子段优先级错了”和“这段代码在干嘛”是完全不同的心理状态。第二凡是自定义比较函数都要在注释里写明“按 xxx 升序/降序排列”。我见过太多代码里只有一个return a.score b.score旁边没有任何注释后来的人改需求时根本不知道原意是什么。是自己的代码也不例外——两周前的自己就是陌生人。第三调试排序问题时先检查比较规则再怀疑 sort 本身。sort() 是一个被无数人使用过的库函数出错的概率极低。如果你的排序结果不符合预期90% 的情况是你定义的比较规则出了问题比如某个字段类型不对、某个字段没有正确初始化、或者比较函数违反了严格弱序。第四如果是竞赛代码、性能敏感的场景尽量用 vector 预留空间 一次性 sort。频繁在循环中调用 sort 是非常昂贵的操作可以把数据先收集到一个 vector最后统一排序。如果真的要在循环里维护有序容器考虑 multiset 或者堆。结构体排序 sort() 看似基础但把它的底层机理和边界情况吃透之后很多看似复杂的问题都会变得非常简单。希望这篇文章能帮你少踩几个坑。