在 GESP、CSP-J“结构体 sort 排序”几乎是一个高频组合。今天的内容分成两个问题① 两个结构体变量到底怎么比大小②sort()怎么知道结构体应该按照什么规则排序一、先认识结构体变量假设我们有一个学生结构体struct Student { string name; int score; int age; };我们可以创建两个学生Student a {小明, 95, 10}; Student b {小红, 88, 11};可以把它想象成a ┌─────────────┐ │ name 小明 │ │ score 95 │ │ age 10 │ └─────────────┘ b ┌─────────────┐ │ name 小红 │ │ score 88 │ │ age 11 │ └─────────────┘那么问题来了a b到底是什么意思C并不会自动知道你想按照什么比较。因为一个学生有姓名分数年龄到底应该比较分数 年龄 姓名 还是全部一起比较所以结构体的大小关系必须明确“比较规则”。二、最简单的方法自己写比较函数比如我们规定分数高的学生更大。那么可以写bool cmp(Student a, Student b) { return a.score b.score; }注意这里非常重要return a.score b.score;意思不是“a 比 b 大。”而是“如果 a 应该排在 b 前面就返回 true。”这是sort()最重要的思想之一。三、先别急着写 sort理解“比较器”我们先看一个简单问题。有三个学生小明 95 小红 88 小刚 92我们想从高到低小明 95 小刚 92 小红 88那么比较器bool cmp(Student a, Student b) { return a.score b.score; }可以理解成cmp(小明, 小红) 95 88 ↓ true 说明 小明应该排在小红前面再比如cmp(小红, 小刚) 88 92 ↓ false 说明 小红不应该排在小刚前面所以比较器其实就是一个“裁判”四、sort()就像一个“排队管理员”假设有Student s[3] { {小明, 95, 10}, {小红, 88, 11}, {小刚, 92, 10} };我们写sort(s, s 3, cmp);意思是把s[0] ~ s[2]这些学生按照cmp规定的规则排序。也就是sort ↓ “我来帮你排队” ↓ 但是…… ↓ “按照什么规则排” ↓ cmp 告诉它 “分数高的排前面”于是小明 95 小刚 92 小红 88五、完整程序#include iostream #include algorithm using namespace std; struct Student { string name; int score; int age; }; bool cmp(Student a, Student b) { return a.score b.score; } int main() { Student s[3] { {小明, 95, 10}, {小红, 88, 11}, {小刚, 92, 10} }; sort(s, s 3, cmp); for(int i 0; i 3; i) { cout s[i].name s[i].score s[i].age endl; } return 0; }输出小明 95 10 小刚 92 10 小红 88 11六、为什么是从大到小这是初学者最容易搞混的地方。看bool cmp(Student a, Student b) { return a.score b.score; }实际上a.score b.score表示a 应该排在 b 前面。例如a 小明95 b 小红88 95 88 true所以小明 ↓ 排前面因此得到95 92 88也就是从大到小。七、如果改成呢bool cmp(Student a, Student b) { return a.score b.score; }那么88 92 true表示小红应该排在小刚前面最终88 92 95所以a.score b.score就是从小到大。可以让孩子直接记住sort ↓ 小 → 大 sort ↓ 大 → 小八、结构体可以按照多个条件排序这才是考试中真正重要的部分。例如先按照分数从高到低。如果分数相同再按照年龄从小到大。例如小明 95 10 小红 95 11 小刚 92 10 小丽 95 9我们希望小丽 95 9 小明 95 10 小红 95 11 小刚 92 10怎么办九、两个条件的比较器写bool cmp(Student a, Student b) { if(a.score ! b.score) { return a.score b.score; } return a.age b.age; }这是非常经典的写法。我们一步一步理解。第一关比较分数if(a.score ! b.score) { return a.score b.score; }意思如果分数不一样直接按照分数排序。例如a95 b92因为95 ! 92所以return 95 92;得到true于是95 排前面 92 排后面十、第二关分数相同怎么办如果小明 95 10 小红 95 11那么a.score ! b.score是95 ! 95结果false于是不会执行return a.score b.score;而是继续往下面return a.age b.age;于是10 11得到true所以年龄10岁的小明 排在 年龄11岁的小红 前面十一、这就是“第一关键字、第二关键字”考试中经常这样说按照成绩降序如果成绩相同按照编号升序。翻译成代码bool cmp(Student a, Student b) { if(a.score ! b.score) return a.score b.score; return a.id b.id; }可以形成一个非常重要的口诀先比第一关键字不同就结束相同再比第二关键字。例如第一关键字score 第二关键字id代码if(a.score ! b.score) return a.score b.score; return a.id b.id;十二、三个条件怎么办比如第一关键字成绩从高到低第二关键字年龄从小到大第三关键字学号从小到大可以写bool cmp(Student a, Student b) { if(a.score ! b.score) return a.score b.score; if(a.age ! b.age) return a.age b.age; return a.id b.id; }逻辑就是比成绩 ↓ ┌────┴────┐ 不同 相同 ↓ ↓ 结束 比年龄 ↓ ┌────┴────┐ 不同 相同 ↓ ↓ 结束 比学号这就是结构体排序中非常经典的多关键字排序。十三、vector里面的结构体也可以排序现在我们把数组换成vectorvectorStudent v; v.push_back({小明, 95, 10}); v.push_back({小红, 88, 11}); v.push_back({小刚, 92, 10}); sort(v.begin(), v.end(), cmp);这里sort(v.begin(), v.end(), cmp);和数组sort(s, s 3, cmp);本质是一样的。区别只是数组 sort(s, sn, cmp) vector sort(v.begin(), v.end(), cmp)十四、能不能直接写sort(s, sn)如果是int a[5];可以sort(a, a 5);因为int本身就知道怎么比较1 2 3 5但是结构体struct Student { string name; int score; };C 不知道Student A Student B到底应该按照 score 按照 name 按照 age所以通常需要告诉sort()sort(s, sn, cmp);十五、结构体排序最重要的模板对于小学生我建议直接记住下面这个模板struct Student { int score; int id; }; bool cmp(Student a, Student b) { if(a.score ! b.score) return a.score b.score; return a.id b.id; }然后sort(s, sn, cmp);脑子里翻译成sort ↓ 帮我排队 cmp ↓ 告诉你排队规则 if ↓ 第一条件不同 ↓ 按照第一条件 相同 ↓ 看第二条件十六、一个非常容易犯的错误很多初学者会写bool cmp(Student a, Student b) { if(a.score b.score) return true; if(a.score b.score) return a.id b.id; return true; }这里最后return true;就是错的。例如a.score 80 b.score 90此时a.score b.score是80 90 false然后a.score b.score也是false最后却return true;这等于告诉sort()“80分的学生应该排在90分学生前面。”显然错了。正确写法最简单bool cmp(Student a, Student b) { if(a.score ! b.score) return a.score b.score; return a.id b.id; }十七、一个更重要的理解cmp(a,b)到底是什么意思这是学习sort的关键。不要把cmp(a,b)理解成“a 大于 b 吗”更准确的理解是“按照我的排序规则a 应该排在 b 前面吗”例如bool cmp(Student a, Student b) { return a.score b.score; }那么cmp(95分, 88分)结果true意思95分应该排在88分前面而cmp(88分, 95分)结果false意思88分不应该排在95分前面十八、最后给孩子一个“排序裁判”的故事可以把sort()想象成一个学校老师。有一排学生小明 小红 小刚 小丽老师说“我要按照成绩从高到低排队。”但是老师自己不知道谁应该站谁前面于是我们给老师一个裁判bool cmp(Student a, Student b) { return a.score b.score; }老师每次问裁判a 和 b 谁站前面裁判回答cmp(a,b) true a站前面 false a不站前面于是sort()就能完成整个排序。所以sort() │ “帮我排队” │ ↓ cmp() │ “谁应该站前面” │ ┌──────┴──────┐ true false ↓ ↓ a在前 a不在前十九、GESP/CSP-J必须掌握的四种写法① 单关键字从小到大bool cmp(Student a, Student b) { return a.score b.score; }② 单关键字从大到小bool cmp(Student a, Student b) { return a.score b.score; }③ 两个关键字bool cmp(Student a, Student b) { if(a.score ! b.score) return a.score b.score; return a.id b.id; }④ 三个关键字bool cmp(Student a, Student b) { if(a.score ! b.score) return a.score b.score; if(a.age ! b.age) return a.age b.age; return a.id b.id; }二十、最后同学们一定要记住这句话 ⭐把整个知识点压缩成一句话sort()负责“排队”cmp()负责“制定排队规则”。而结构体排序最核心的代码bool cmp(Student a, Student b) { if(a.score ! b.score) return a.score b.score; return a.id b.id; }意思就是先比成绩成绩高的在前成绩一样再比学号学号小的在前。掌握了这个模板之后后面的学生排名、比赛排名、成绩排序、结构体数组排序、vector 排序、二维信息排序、多关键字排序基本都可以举一反三。
