GESP四级第二题六个字“排序”每年都能让一批同学从信心满满到怀疑人生。今年6月的这道题实际上并不复杂核心就是排序规则的理解 C sort 的自定义比较器。如果你今早在考场上用了 sort却因为比较函数写反或者没搞懂“分数相同按学号从小到大”这个稳定排序要求最后样例都过不去那这篇文章就是写给你的。我不喜欢讲空话直接还原题目、拆思路、给代码、讲避坑一条龙讲完。不说官方题库原话但题目结构和考点跟我在备考阶段反复练的那一类完全一致。1. 题目还原与考点定位1.1 题目描述还原根据考生回忆和历年出题风格这道题大致长这样某班有 n2 ≤ n ≤ 10000个学生。每个学生有一个学号 id 和一个考试成绩 score0 ≤ score ≤ 100。请你按照以下规则对全班学生排序成绩高的排在前面如果成绩相同学号小的排在前面。输入第一行一个整数 n接下来 n 行每行两个整数 id 和 score。 输出排序后每行输出一个学生的学号和成绩用空格隔开。样例输入3 2 90 1 90 3 80样例输出1 90 2 90 3 80题干很短读着也不难但越是这种看起来没坑的题越容易在小细节上砸锅。1.2 这题到底在考什么GESP四级大纲里排序算法和 STL 是必考内容。这道题表面上是排序实际上考了四件事能不能看懂排序规则主关键字是成绩降序次关键字是学号升序。会不会写自定义比较器也就是 C sort 的第三个参数。懂不懂稳定排序和不稳定排序的区别如果你不知道 sort 是不稳定的就可能因为用错函数而丢分。知不知道结构体的基本用法把关联的两个数据打包成一个整体而不是拆成两个平行数组排序。很多同学一看到“排序”两个字脑子里就只有sort(a, an)这个不带条件的一键排序。但遇到多关键字就必须额外给它一套“规则”这就是自定义比较器登场的地方。1.3 样例验证我们先拿样例过一遍等会代码写出来还要靠它验证。输入三行数据原始顺序是id2, score90id1, score90id3, score80按规则90分那两个并列最高id没有顺序要求的话谁排前面都行。但规则明确说了成绩一样就按学号升序。id1 id2所以输出必须是1 90然后2 90最后是3 80。这个样例点专门用来检验你排序后相同成绩学生的相对顺序是否满足要求。2. 完整思路拆解从排序规则到比较器2.1 排序规则的数学表达写代码之前先把规则翻译成逻辑表达式。假设有两个学生 A 和 B成绩分别是 scoreA、scoreB学号分别是 idA、idB。A 应该排在 B 前面也就是 A 小于 B在 sort 的比较逻辑里返回 true需要满足scoreA scoreB或者scoreA scoreB 并且 idA idB对应代码就是bool cmp(Student a, Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; }这里有一个初学者特别容易踩的坑把第一个条件写成return a.score b.score。那样就变成从小到大排序了样例第二个点是 3 80它会被排到最前面直接离谱。2.2 为什么要自定义比较函数sort(a, an)默认是升序也适用于 int、double 这些内置类型但它完全不了解“学生成绩”这种东西。sort 的默认规则是“a 小于 b 就返回 true否则返回 false”。对于两个Student结构体对象它不知道什么叫“大于”更不知道什么叫“成绩相同比学号”。自定义比较器cmp本质是给 sort 提供一本“规则手册”告诉它两个学生谁应该排在前面。sort 内部的排序算法一般是内省排序在整个排序过程中会反复调用这个cmp来决定是否交换两个元素的位置。提示cmp必须是一个严格弱序strict weak ordering。也就是说它需要满足三个基本性质反自反性同一元素比较cmp(a, a)必须返回 false。非对称性cmp(a, b)和cmp(b, a)不能同时为 true。传递性如果cmp(a, b)且cmp(b, c)则必须cmp(a, c)。只要你的比较规则自洽基本都能满足。但如果你写出return a.score b.score;这种带等号的比较器就是自毁长城后面详说。2.3 两种数据结构存储struct vs pair这道题可以把学生信息存成结构体也可以用pairint, int但是两种写法有细微差别。写法一structstruct Student { int id; int score; };清晰、可读性强自定义比较器里访问字段也舒服。缺点是代码量稍多。写法二pairpairint, int默认的比较规则是先比较 first再比较 second。如果我们直接存pairscore, id那 sort 会先按分数升序分数相同再按学号升序。这不是我们要的分数降序所以要把分数存成负数或者用pairid, score然后用特殊比较器。存负分数能利用默认规则但代码语义不够直观vectorpairint, int v; // pairscore取负, id v.push_back({-90, 2}); sort(v.begin(), v.end()); // 默认升序-90 -80相当于90排在80前面这种写法很巧妙很多竞赛选手爱用但考场上一紧张容易弄混。我更推荐 struct 显式比较器逻辑清楚不容易翻车。2.4 比较函数的三个“不要”虽然目录看着像是废话但真的有人死在下面这三件事上不要写或。sort的比较器如果对两个等价元素返回 true会破坏内部排序的假设导致未定义行为轻则结果诡异重则直接崩溃。记住比较相等要返回 false。不要把主次关键字搞反。有些人先比较 id 再比较 score结果成绩相同的排对了但不同成绩的顺序完全乱了。不要试图在排序时“保留原顺序”。如果你因为 sort 不稳定而想依赖输入顺序那是不靠谱的要么用stable_sort要么把输入相对顺序作为一个额外关键字存入结构体。3. 参考代码与逐行解析3.1 第一种写法struct 自定义比较器直接上完整可编译代码我在考场上用的就是这种思路大众、稳定、好解释#include bits/stdc.h using namespace std; struct Student { int id; int score; }; bool cmp(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorStudent students(n); for (int i 0; i n; i) { cin students[i].id students[i].score; } sort(students.begin(), students.end(), cmp); for (const Student s : students) { cout s.id s.score \n; } return 0; }逐行说明#include bits/stdc.h是包含全部 STL 头文件的万能头GESP 评测环境普遍支持考试时用它能省很多心。struct Student定义两个成员。结构体就是打包数据的最小单位比开两个数组id[]和score[]更不容易弄错对应关系。cmp接收两个const Student加const和引用是习惯避免拷贝也能防止意外修改原对象。sort的第三个参数写上cmpsort 内部就用它来比较元素。经过排序后students容器里的元素顺序就变成了题目要求的顺序。输出用\n而不是endlendl会强制刷新输出缓冲区循环次数一多会拖慢程序。3.2 第二种写法stable_sort pair如果你更清楚稳定排序的概念也可以这么写#include bits/stdc.h using namespace std; struct Student { int id; int score; int order; // 记录输入顺序 }; bool cmp(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; if (a.id ! b.id) return a.id b.id; return a.order b.order; }等等题目里成绩相同已经规定按学号升序而学号是唯一的所以实际上不需要 order。但我想借此说明一个更常用的技巧如果你想把“输入顺序”作为一个兜底条件保留就加一个 order 成员记录输入序号。这条在处理“排序后保持原相对顺序”的需求时特别有用。还有一种做法是用stable_sort这个算法基于归并排序排序时如果两个元素等价比较结果相等它们会保持排序前的相对顺序。不过在这道题里由于学号唯一成绩相同时学号大小已经唯一决定顺序所以sort也不会乱。但如果你遇到“成绩相同就按输入顺序排”这种题那就必须用stable_sort或者手动记录原始下标。3.3 输入输出性能优化细节题目的 n 上限是 10000理论上用cin 和cout 也能过但你不知道评测机运行环境如何。稳妥起见我总会加上三行代码ios::sync_with_stdio(false); cin.tie(nullptr);第一行关闭 C 和 C 标准流之间的同步让 cin 不再和 scanf 共用一个缓冲区第二行解除 cin 与 cout 的绑定避免每次读入前强制刷新输出。这两个操作能让 cin/cout 的吞吐量明显提升。如果你用 scanf/printf不需要这两行但也别和 cin/cout 混用混用的后果是顺序错乱或者性能下降具体原理属于 C 标准流缓冲区问题这里不多展开。还有一点读入学生信息时用的cin students[i].id students[i].score;会自动跳过空白字符所以输入里多几个空格或换行都没关系别自己去做无谓的scanf格式校验。4. 运行过程与边界测试4.1 样例走查用我们上面的代码跑一遍样例读入 n3。结构体 vector 里依次存入 (2,90), (1,90), (3,80)。sort 调用 cmp 进行排序比较 (2,90) 和 (1,90)score 相等id 2 1所以 (2,90) 不排在前面(1,90) 需要前置。比较 (1,90) 和 (3,80)90 80(1,90) 前置。最终顺序 (1,90), (2,90), (3,80)。输出格式完全一致。4.2 边界数据构造与测试考试不只考样例边界条件才是杀招。我给你列几个典型的边界用例你可以粘贴到本地跑一遍用例1n2两个学生成绩相同2 5 88 2 88期望输出2 88 5 88这个用例专门测试“次关键字学号升序”。如果你的代码只按成绩排不管学号两行输出会跟原始输入顺序一致因为 sort 不稳定运气不好时可能输出 5 88 在 2 88 前面。用例2成绩跨度最大4 100 100 99 0 1 50 2 50期望输出100 100 1 50 2 50 99 0这里有两个 50 分的学号 1 和 2必须按 1 2 的顺序不能变成 2 1。用例3所有学生成绩完全相同3 10 60 20 60 30 60期望输出就是按学号升序。这个用例测的是比较器在 score 都相等时能否完全依赖 id 排序。如果比较函数里写成了return a.score b.score;而没有后续 id 比较那么这 3 个元素的相对顺序在 sort 里是不确定的。用例4n 的最小值 2这个几乎所有人都会过但恰好是很多同学不会循环的起点。如果你把循环从 i1 开始读 n2 时会漏一个输出就缺行。注意循环写for (int i 0; i n; i)别自作聪明。4.3 大数据量与复杂度验证我构造了一个 n10000 的随机数据在本地跑程序运行时间几乎可以忽略。时间复杂度是 O(n log n)这是排序算法的理论下限附近的常见复杂度。空间复杂度是 O(n)存储所有学生信息。具体到 sort 的内省排序平均时间复杂度 O(n log n)最坏 O(n log n)它结合了快速排序、堆排序和插入排序的优点。对于 n10000sort 处理起来毫无压力。而如果这道题你手写了一个冒泡排序最坏情况 O(n^2)n10000 时就是一亿次比较在评测机里极可能超时这也是GESP四级喜欢考察“能直接用STL就用STL”的原因。5. 常见错误与避坑经验5.1 比较器写反/搞错降序升序我见过最多的错误是bool cmp(Student a, Student b) { return a.score b.score; // 从小到大 }或者把成绩降序写成return a.score b.score ? true : false;这种写法本身没问题但后面接 id 时容易把逻辑写乱。真正稳妥的顺序是先写不相等的情况再写相等的情况。别为了省一行代码把两个条件合并。错误范例return a.score b.score || (a.score b.score a.id b.id);我知道很多人爱这么写要求也符合但在新手阶段分开写更不容易出错。分开写的代码即使将来改成别的排序规则也一眼能看出主次关键字。5.2 忽略 sort 的不稳定性造成顺序错乱很多人把“sort”等同于“稳定排序”这是错误认知。C 的sort是不稳定排序它不能保证等价元素的相对顺序。什么叫等价元素在我们这道题里如果学号唯一实际上没有完全等价的元素因为学号总能区分顺序。但如果题目改成“如果得分相同按输入顺序先后排列”你再用 sort它可能把输入顺序打乱。这时候有两个选择用stable_sort替换sort它基于归并排序保证等价元素保持原有顺序。或者给每个元素记录一个唯一的 order 字段作为最后一个比较关键字。这样即使用不稳定 sort也等价于稳定排序。我个人倾向第二种因为stable_sort的时间复杂度虽然是 O(n log n)但常数比sort大数据量大时会有感知。更重要的是通过记录 order你还能顺便掌握多关键字排序的精髓一举两得。5.3 输入输出效率导致超时n10000一般情况下 cin 不会超时但GESP评测机“卡IO”的情况也不是没出现过。有同学用cin n;然后循环cout endl;在 n 比较大的时候endl不断刷新缓冲区性能急剧下降。这不是技术问题是细节问题。我的习惯是在文件开头写上ios::sync_with_stdio(false);和cin.tie(nullptr);输出统一用\n。这一点不管你参加什么C考试都是好习惯。5.4 错误使用相等元素的比较再强调一次cmp返回 true 表示 a 应该排在 b 前面返回 false 表示不一定。如果你写了return a.score b.score;当两个分数相等时cmp(a,b) 和 cmp(b,a) 都返回 true这就违反了严格弱序的反对称性原则。sort 内部算法碰到这种情况会行为异常结果可能是一团乱序。很多同学自以为看懂了比较器其实只看了眼“大于号”和“小于号”。要判断一个比较器是否合格可以把它放到 set 或 priority_queue 中使用如果出现莫名其妙的重复或顺序错乱那就是比较器有问题。最简单的自查方法对两个相同 key 的数据 a 和 b手动算一遍cmp(a,b)和cmp(b,a)如果两个都是 true立刻重写。6. 从这道题延伸GESP四级排序题还能怎么考6.1 字符串排序四级考试另一大经典就是字符串排序。比如给你 n 个字符串按长度从小到大排长度相同按字典序升序。这题同样用自定义比较器区别是要处理string类型的比较。string类型自带length()和运算符所以代码写起来更简单bool cmp(const string a, const string b) { if (a.length() ! b.length()) return a.length() b.length(); return a b; }再进阶一点题目可能要求忽略大小写排序那就需要额外写一个toLower函数或者用 C 标准库的tolower。这种字符串排序考的就是你对 STL 字符串容器的熟悉程度以及处理局部比较规则的能力。6.2 结构体多关键字排序多关键字排序是四级排序题里最常见的配方。常见的规则组合有总分降序总分相同语文降序语文相同数学降序再相同学号升序。日期排序先年再月再日。学生信息表按班级升序班级相同按成绩降序。无论规则多复杂比较器和我们的 cmp 函数思路完全一样把每个关键字按照优先级依次比较某个关键字能分出高下就立刻返回结果否则继续比较下一个。写的时候记住“先主后次相等再比下一个”这个口诀。6.3 手写排序算法虽然四级不强制要求手写排序算法但大纲明确覆盖冒泡排序、选择排序、插入排序这些基础排序。像这种“第二题排序”的题目如果你只用 sort是可能被扣过程分的。我这里说的“过程分”不是指考试评分而是指你学习算法时的自我要求。比如选择排序每一轮找到剩余元素中最小或最大的元素交换到前面。它是不稳定排序但如果你利用“稳定化技巧”比如只交换相邻元素或者在比较相等时不交换就可以变成稳定的。考试时如果要求写出算法过程你应该能手动模拟冒泡排序的每一轮交换。6.4 排序和其他知识结合排序经常跟贪心、二分、前缀和等搭配出题。比如“最小移动次数使数组有序”“合并区间”“求逆序对”等都是排序的延展。回到这道题它本身很基础但你要是能把它背后的比较器原理吃透那么后面遇到“自定义对象装入优先队列”“按字典序拼接字符串得到最小数字”这类题时思路会轻松不少。比如有一个经典面试题给定一组非负整数将它们拼接起来得到一个最大的数。解法是自定义排序规则两个数 a 和 b比较字符串 ab 和 ba 哪个大。这本质上用的还是 cmp 函数只不过比较的是拼接后的字符串。如果没学会自定义比较器这类题会无从下手。最后再分享一点考场经验我每次参加这类编程考试都会在写排序题时主动做三件事第一先在草稿纸上把排序规则写成if...else伪代码避免直接写 cmp 时脑子乱。第二代码写完立刻拿样例走一遍重点看相同分数学生的顺序对不对。第三故意构造一个“最阴间”的边界用例比如所有分数都相同或者 n 最小的用例测试输出是否稳定。这三步看着浪费时间但能把失误概率压到最低。尤其是这道“第二题排序”它往往是整张卷子区分度的分水岭写对了后面的大题心态就稳写错了则可能连锁影响到后面的发挥。希望明白这些坑之后你再遇到类似的题目能像条件反射一样写出正确的比较器稳稳拿下这些分数。