多关键字排序实战：从奖学金题学透排序规则与自定义比较函数

某天我在一个在线题库里整理题单的时候又看到了这道编号1106的老朋友——《奖学金》。说它是老朋友是因为这类多关键字排序的题目在信息学竞赛入门阶段太常见了几乎每本教材、每个模拟赛里都会换着花样出现一次。第一次见到它的人往往觉得这题不就是排个序吗可真正动手写的时候很多人会在比较规则上翻车样例都过不去。这篇文章就拿这道题当引子把多关键字排序的完整思考过程、代码实现、边界测试和常见扩展都梳理一遍。无论你是刚接触竞赛编程的初学者还是准备参加入门级信息学比赛想补基础的同学都可以把这篇当成一份可以反复对照的复习材料。1. 题目到底在考什么从会排序到会定义规则1.1 先把原题描述复原出来这道题的背景很简单某个年级有N名学生每名学生考了语文、数学、外语三科。学校要评选出一批奖学金获得者规则是这样的——先按三科总分从高到低排序如果总分相同再看语文成绩语文高的排前面如果总分和语文成绩都相同则学号小的排前面。排序结束后取前5名学生输出他们的学号和总分。题目本身没有复杂的算法数据范围一般也不大N通常在几百到几千之间但它有一个非常鲜明的特点排序规则是由三个关键字逐层嵌套组成的。总分是第一关键字语文是第二关键字学号是第三关键字。这种一级一级比下去的规则恰好是很多新手第一次接触多关键字排序时的典型痛点。1.2 为什么它不算一道纯代码题如果光说排序大家都会说用sort。可一旦规则变成总分相同看语文语文还相同看学号事情就没那么简单了。你需要先把中文描述翻译成一组计算机能理解的比较逻辑这个翻译过程才是真正的考点。举个例子很多同学会把总分从高到低和语文从高到低直接各自写一个排序然后用先按语文排再按总分排这种顺序去调用两次排序。这在小范围数据里偶尔能蒙对但严格来说是个错误做法。为什么因为后一次排序会打乱前一次排序的稳定结果除非你依赖的排序算法是稳定的而且你还得保证关键字处理顺序完全相反。这个思路不但绕还特别容易在边界情况上出错。与其这样不如把规则合并成一个统一的比较函数一次排序解决所有问题。1.3 复盘这道题真正的能力要求拆开来看题目考察的能力有三层第一层是读题能力能不能从一段文字里准确抽取出三条比较规则并分清它们之间的优先级。第二层是建模能力能不能用一个合适的数据结构把每个学生的多科成绩和学号打包在一起。第三层是表达能力能不能把比较规则准确无误地翻译成代码尤其是学号小的排前面这种容易被忽略的最后一层。这三层能力恰恰是很多编程初学者在学完语法之后最欠缺的。语法都会但一遇到条件多一点的排序就不知道从哪里下手。所以这道题虽然简单用来检验基础却非常合适。2. 数据结构设计先别急着写排序想清楚怎么存学生信息2.1 用结构体把信息打包既然一个学生同时拥有学号、语文、数学、外语和总分这些属性最自然的做法就是用结构体把它们包成一个整体。C里可以这样定义struct Student { int id; // 学号 int chinese; // 语文成绩 int math; // 数学成绩 int english; // 英语成绩 int total; // 总分 };有的同学会问为什么不分别用几个数组存比如id[i]、chinese[i]、math[i]、english[i]然后排序的时候只排下标这样做当然也可以但问题在于排序时会非常别扭。因为排序的本质是交换元素的顺序如果你用的是多个平行数组交换一个下标的时候必须同时交换五个数组里的对应值漏掉一个就全乱了。结构体的好处是一个Student对象就是一个完整的学生交换时整体交换代码既短又不容易出错。Python 那边就更灵活了可以用dataclass也可以直接用元组或者用一个字典。为了可读性初学者最适合用dataclass或者普通类。但说实话竞赛场景里最简单粗暴的做法是用元组每个元组代表一个学生# (学号, 语文, 数学, 英语, 总分) student (1, 88, 95, 92, 275)2.2 总分是存还是临时算这是很多初学同学忽略的设计问题。总分可以在读入数据时直接算好存进结构体或元组里也可以在排序的时候临时算。看到这里你可能觉得这有什么好纠结的临时算就行。但我们要考虑一个现实问题如果在比较函数里临时算总分那每比较两个学生就要做两次三数相加。虽然一次加法很便宜但排序的比较次数接近 N 乘以 log N数据量一大这种重复计算就白白浪费了很多时间。更关键的是临时算总分会让比较函数的逻辑变复杂// 比较时临时算总分代码又多又乱 bool cmp(const Student a, const Student b) { int totalA a.chinese a.math a.english; int totalB b.chinese b.math b.english; if (totalA ! totalB) return totalA totalB; if (a.chinese ! b.chinese) return a.chinese b.chinese; return a.id b.id; }不推荐。正确的做法是在读入阶段就把总分算好存进total字段里后面所有地方都用现成字段。这样比较函数更短也更容易核对。所谓把能提前算好的东西提前算好是写任何程序都应该养成的习惯。2.3 读入时的学号偏移坑题目里的学号是从1开始编号的所以读到第i个学生时id i 1如果循环变量从0开始。这个看起来不值一提的细节反而是每年都有人踩的坑。排序时如果学号排错了哪怕其他逻辑全对输出的学号也会整体偏移一位最后白白丢分。另外如果使用 C 的vector记得先reserve或者直接初始化大小再读入避免反复扩容带来的性能损耗int n; cin n; vectorStudent students(n); for (int i 0; i n; i) { students[i].id i 1; cin students[i].chinese students[i].math students[i].english; students[i].total students[i].chinese students[i].math students[i].english; }这样数据结构和读入就完成了从代码上看学生信息是整齐划一的后续排序只需要关心怎么比这一个问题。3. 实现排序规则两种主流语言三条比较条件3.1 C用sort加自定义比较函数C 的std::sort接受一个比较器这个比较器的返回值表示第一个参数是否应该排在第二个参数前面。对应到这道题就是下面这段代码bool cmp(const Student a, const Student b) { if (a.total ! b.total) return a.total b.total; if (a.chinese ! b.chinese) return a.chinese b.chinese; return a.id b.id; } sort(students.begin(), students.end(), cmp);三段逻辑分别对应题目里的三句话。第一句a.total ! b.total表示总分不同时总分大的放前面第二句a.chinese ! b.chinese表示总分相同且语文不同时语文大的放前面第三句return a.id b.id表示前面两项都相同的时候学号小的放前面。这段代码的关键在于嵌套。每一层都先判断当前关键字是否相等如果不相等就直接给出结果如果相等就落入下一层继续判断。这个模式很固定你可以把它背下来以后遇到任何多关键字排序题都能套用。3.2 CLambda 写法的对比如果你嫌单独写一个cmp函数麻烦也可以直接在sort里用 lambdasort(students.begin(), students.end(), [](const Student a, const Student b) { if (a.total ! b.total) return a.total b.total; if (a.chinese ! b.chinese) return a.chinese b.chinese; return a.id b.id; });这两种写法没有本质差别lambda 只是把函数定义内联到了调用处。比赛里我一般推荐单独写一个具名函数理由很简单具名函数可以被复用而且更容易在多个地方调用时保持一致lambda 虽然短但如果后面需要调试反而不方便。当然如果你已经习惯 lambda用起来也没有任何问题。3.3 Python利用元组 key 的天然顺序Python 的list.sort方法允许你传入一个key函数它会根据key的返回值进行排序。返回值可以是元组元组会从左到右依次比较每个元素。巧的是我们正好可以利用这个特性students.sort(keylambda s: (-s[total], -s[chinese], s[id]))注意这里的小技巧想要总分从高到低可以用-s[total]取负以后值越大负数越小自然就排在前面了。语文同理。学号要从小到大直接写s[id]即可。如果用的是dataclass或类对象可以先把学生存成对象列表然后写一个返回元组的函数students.sort(keylambda s: (-s.total, -s.chinese, s.id))这个写法非常简洁几乎就是把中文规则逐字翻译成了代码。需要提醒的是取负技巧只适用于纯数值类型。如果关键字是字符串就需要用reverseTrue或者自定义更复杂的key了。3.4 完整代码骨架把前面所有的内容拼在一起C 版本可以长这样#include bits/stdc.h using namespace std; struct Student { int id, chinese, math, english, total; }; bool cmp(const Student a, const Student b) { if (a.total ! b.total) return a.total b.total; if (a.chinese ! b.chinese) return a.chinese b.chinese; return a.id b.id; } int main() { int n; cin n; vectorStudent students(n); for (int i 0; i n; i) { students[i].id i 1; cin students[i].chinese students[i].math students[i].english; students[i].total students[i].chinese students[i].math students[i].english; } sort(students.begin(), students.end(), cmp); for (int i 0; i 5; i) { cout students[i].id students[i].total endl; } return 0; }Python 版本可以长这样n int(input()) students [] for i in range(1, n 1): chinese, math, english map(int, input().split()) students.append((i, chinese, math, english, chinese math english)) students.sort(keylambda s: (-s[4], -s[1], s[0])) for i in range(5): print(students[i][0], students[i][4])这已经是一份能够正确运行的完整代码了。但说实话能写出这份代码的人并不少真正把分数稳稳拿到手里的是那些能意识到这个代码在什么情况下会出问题的人。4. 边界与验证样例过了不算完还要这样自测4.1 手动构造一组能触发所有规则的数据很多同学提交之后发现样例能过但评测就是错问题往往出在只测试了样例数据。一道排序题的正确性必须覆盖所有规则分支。我建议你养成构造临界数据的习惯。对于这道题我通常会构造这样一组数据三个人总分分别为 300、299、300语文分别为 100、99、100学号分别为 1、2、3。此时排序预期是学号1、学号3、学号2。因为学号1和学号3总分相同、语文也相同学号小的排前面。然后再构造一组总分相同、语文不同确保第二关键字生效再构造一组总分不同确保第一关键字生效。把这三组数据凑在一起就能覆盖所有判断分支。4.2 常见翻车点比较器顺序、学号偏移、总分开头没算我观察过不少同学的代码发现翻车点高度集中在三处。第一处是把return a.id b.id写成了return a.id b.id。这个错误非常隐蔽因为如果数据里没有出现总分和语文都相同的情况这个分支根本不会被执行程序照样能过样例。可一旦出现并列情况排序结果就会颠倒。第二处是学号偏移。前面讲过学号从1开始可循环变量往往从0开始一不留神就会让第1个学生的学号变成0。这种错误同样可能在简单数据下被掩盖。第三处是只计算了total但排序时错用了chinese当总分或者排序后再修改成绩但没有重新计算总分。这类错误归根结底是数据冗余导致的同步问题。改进思路很简单总分只在读入时计算一次之后永远不要手动修改单个成绩字段如果你非改不可那就重新算总分。4.3 性能与复杂度这道题到底能开到多大std::sort的时间复杂度是 O(N log N)空间复杂度 O(log N) 到 O(N) 不等。对于这道题通常给定的 N 范围这个复杂度绰绰有余。但如果你非要较真还可以思考一种优化题目只要前5名并不需要完整排序。在 N 非常大的时候完整排序的 O(N log N) 可能不是最优解。我们可以维护一个大小为5的小顶堆遍历所有学生如果当前学生比堆顶更优秀就替换掉堆顶并重新调整堆。这样时间复杂度是 O(N log 5)近似 O(N)。但老实说这道题的数据规模下完全没有必要。我提出这点是为了提醒你学习排序算法时不要只背 API也要理解什么时候排序是浪费的。5. 如果题目稍微改一改多关键字排序的通用思路5.1 改一取前K名而不是前5名把前5名改成前K名代码只需要改一处输出循环其他完全不用动。但如果你做的是优化版小顶堆K 的引入就要注意堆的大小从5变成K输出的时候需要从堆里依次弹出元素再反转因为你取到的是当前K个最优但顺序是反的。5.2 改二名次并列怎么处理原题只要求输出前5名学生的学号和总分但很多变种题会要求按名次输出并且总分相同则名次相同。比如三个人总分分别是 300、299、299那么第2名和第3名并列下一个人名次是4而不是3。这种题就涉及根据排序结果计算名次的逻辑也是一个非常经典的考点。具体做法是排序完成后遍历排序结果如果当前学生的关键字段与上一个学生完全相同名次延续否则名次等于当前下标1。这套逻辑理解之后你会发现它跟多关键字排序其实是一脉相承的——既然排好了序名次就只是统计问题。5.3 多关键字排序的通法总结遇到任何多关键字排序题都可以按这三步走第一步把每个待排序对象封装成结构体或对象。第二步找出题目里所有的排序关键字并且确定它们的优先级从高到低。第三步写一个比较函数按优先级顺序逐层比较每层只处理当前关键字相等或不等两种情况。这个套路几乎能解决九成的排序题不管关键字是成绩、时间、字符串还是其他任何可比较类型。我还想补充一点如果你用的是 C比较函数一定要满足严格弱序strict weak ordering。简单说就是不能出现自相矛盾的情况比如既返回a b又返回b a。std::sort在比较器不满足这个条件时会产生未定义行为排序结果会变得不可预测。上面那段cmp里的嵌套写法天然满足这个要求所以照着写基本不会出问题。6. 这类排序题最容易埋在细节里的坑6.1 读入和输出的格式陷阱有些在线评测题的第一个坑就是输入输出格式。这道题一般输入是第一行一个整数 N接下来 N 行每行三个整数分别表示语文、数学、英语。输出是五行每行两个整数学号和总分中间用空格分隔。别小看这个空格分隔末尾有没有多余空格、用printf还是cout在多数评测系统里都不影响判断但在某些严格系统里行末空格也可能导致格式错误。我习惯在输出时不在行尾留多余空格直接每次输出完后换行。6.2 不要过度设计简单题用简单写法见过一些同学明明是一道排序入门题非要自己实现一个快速排序或者引入一堆复杂的数据结构。结果不仅代码长还容易出现低级错误。我的建议是在竞赛里能用库函数完成的事就不要自己造轮子。std::sort和list.sort都是经过千锤百炼的实现正确性和效率都远胜于大多数人手写的排序算法。除非题目明确要求不能使用排序函数或者考查的是排序算法本身否则直接用库函数就是最高效的选择。6.3 一个值得长期坚持的练习方法最后分享一个我自己带新人时经常用的方法把一道排序题的测试数据分成正序逆序全相同只有一对相同最大数据量最小数据量六组每次写完排序代码都要拿这六组数据各跑一遍。刚开始会觉得很麻烦但跑多了之后你对排序规则的理解会变得异常敏感甚至看代码一眼就能找出比较逻辑里的不对称问题。这道《奖学金》题说难真的不难说简单也不算完全简单。它恰好卡在一个很好的位置能区分出背过API和真正理解规则两类选手。如果你把这一道题研究透了后面遇到再复杂的多关键字排序本质上都是在重复今天这套方法封装数据、定义比较规则、分级判断、自测边界。把这四件事变成肌肉记忆排序类题目就算真正过关了。