【题目链接】
ybt 1178：成绩排序
OpenJudge NOI 1.10 03:成绩排序
【题目考点】
1. 结构体 排序
【君义精讲】排序算法
2. 多关键字排序
方法1：将多关键字的排序条件整合为单一排序条件
方法2：使用稳定的排序算法进行多趟排序
【解题思路】
对结构体对象排序，比较的是成员变量，交换的是对象
【题解代码】
解法1：将多关键字的排序条件整合为单一排序条件
整合成的排序条件为：分数更高，或分数相同且名字字典序小，则排在前面。
冒泡排序
#include<bits/stdc++.h>using namespace std;struct Stu{char name[25];int score;};bool isPrior(Stu &a, Stu &b)//a是否应该排在b的前面 {return a.score > b.score || a.score == b.score && strcmp(a.name, b.name) < 0;}int main(){Stu stu[25];int n;cin >> n;for(int i = 1; i <= n; ++i)cin >> stu[i].name >> stu[i].score;for(int i = 1; i <= n-1; ++i)//冒泡排序 for(int j = 1; j <= n-i; ++j)if(isPrior(stu[j+1], stu[j]))//如果stu[j+1]应该在stu[j]前面swap(stu[j], stu[j+1]); for(int i = 1; i <= n; ++i)cout << stu[i].name << ' ' << stu[i].score << endl;return 0;}
插入排序
#include<bits/stdc++.h>using namespace std;struct Stu{char name[25];int score;};bool isPrior(Stu &a, Stu &b)//a是否应该排在b的前面 {return a.score > b.score || a.score == b.score && strcmp(a.name, b.name) < 0;}int main(){Stu stu[25];int n;cin >> n;for(int i = 1; i <= n; ++i)cin >> stu[i].name >> stu[i].score;for(int i = 2; i <= n; ++i)//插入排序{for(int j = i; j > 1; --j){if(isPrior(stu[j], stu[j-1]))//如果stu[j+1]应该在stu[j]前面swap(stu[j], stu[j-1]);elsebreak; }}for(int i = 1; i <= n; ++i)cout << stu[i].name << ' ' << stu[i].score << endl;return 0;}
STL sort函数排序
#include<bits/stdc++.h>using namespace std;struct Stu{char name[25];int score;};bool cmp(Stu a, Stu b)//a是否应该排在b的前面 {return a.score > b.score || a.score == b.score && strcmp(a.name, b.name) < 0;}int main(){Stu stu[25];int n;cin >> n;for(int i = 1; i <= n; ++i)cin >> stu[i].name >> stu[i].score;sort(stu+1, stu+1+n, cmp); for(int i = 1; i <= n; ++i)cout << stu[i].name << ' ' << stu[i].score << endl;return 0;}
解法2：使用稳定的排序算法进行多趟排序
采用稳定的排序算法，先按名字字典序从小到大排序，再按成绩由高到低进行排序。
可以采用冒牌、插入，归并等稳定的排序算法。这里直接使用stable_sort进行排序。
#include<bits/stdc++.h>using namespace std;struct Stu{char name[25];int score;};bool cmp1(Stu a, Stu b)//名字字典序小的排在前面 {return strcmp(a.name, b.name) < 0;}bool cmp2(Stu a, Stu b)//分数高的排在前面 {return a.score > b.score;}int main(){Stu stu[25];int n;cin >> n;for(int i = 1; i <= n; ++i)cin >> stu[i].name >> stu[i].score;stable_sort(stu+1, stu+1+n, cmp1);stable_sort(stu+1, stu+1+n, cmp2);for(int i = 1; i <= n; ++i)cout << stu[i].name << ' ' << stu[i].score << endl;return 0;}
