牛客网4854题：从零掌握稳定排序：学生成绩排序算法详解
https://dajuwangluo.cn/zb_users/upload/2025/06/202506201750428926589141.jpg一、问题分析本题要求对学生的成绩进行排序，并保持相同成绩学生的原始输入顺序。这种要求被称为"稳定排序"，是排序算法中的一个重要概念。二、核心算法
[*]数据结构设计：
[*]使用结构体Student存储学生信息
[*]额外添加order字段记录输入顺序
[*]自定义比较函数：
[*]cmp_asc：升序比较函数
[*]cmp_desc：降序比较函数
[*]当成绩相同时，比较原始输入顺序
[*]STL sort算法：
[*]利用C++标准库的sort函数
[*]根据用户选择传入不同的比较函数
三、关键点解析
[*]稳定排序实现：
[*]通过记录原始顺序实现稳定性
[*]比直接使用stable_sort更直观
[*]比较函数设计：
[*]先比较成绩
[*]成绩相同再比较输入顺序
[*]时间复杂度：
[*]sort算法平均O(nlogn)
[*]适合n≤200的数据规模
四、完整代码#include <iostream>
#include <vector>
#include <algorithm>
using namespACe std;
struct Student {
string name;
int score;
int order;// 记录输入顺序
};
bool cmp_asc(const Student& a, const Student& b) {
if (a.score != b.score) return a.score < b.score;
return a.order < b.order;// 成绩相同按输入顺序
}
bool cmp_desc(const Student& a, const Student& b) {
if (a.score != b.score) return a.score > b.score;
return a.order < b.order;// 成绩相同按输入顺序
}
int main() {
int n, op;
cin >> n >> op;
vector<Student> students(n);
for (int i = 0; i < n; i++) {
cin >> students.name >> students.score;
students.order = i;// 记录原始顺序
}
// 根据排序方式选择比较函数
if (op == 1) {
sort(students.begin(), students.end(), cmp_asc);
} else {
sort(students.begin(), students.end(), cmp_desc);
}
// 输出结果
for (const auto& s : students) {
cout << s.name << " " << s.score << endl;
}
return 0;
}五、常见错误
[*]忘记处理相同成绩的情况
[*]比较函数逻辑错误
[*]输入顺序记录错误
扩展思考
[*]如何支持多关键字排序？
[*]如何处理大规模数据排序？
[*]如何实现自定义排序规则的通用方案？
来源：牛客网4854题：从零掌握稳定排序：学生成绩排序算法详解
页:
[1]