牛客网4854题：从零掌握稳定排序：学生成绩排序算法详解

19339201706

一、问题分析

本题要求对学生的成绩进行排序，并保持相同成绩学生的原始输入顺序。这种要求被称为"稳定排序"，是排序算法中的一个重要概念。

二、核心算法

• ‌数据结构设计‌：

  
  
  • 使用结构体Student存储学生信息
  • 额外添加order字段记录输入顺序
    
    

• ‌自定义比较函数‌：

  
  
  • cmp_asc：升序比较函数
  • cmp_desc：降序比较函数
  • 当成绩相同时，比较原始输入顺序
    
    

• ‌STL sort算法‌：

  
  
  • 利用C++标准库的sort函数
  • 根据用户选择传入不同的比较函数
    
    

三、关键点解析

• ‌稳定排序实现‌：

  
  
  • 通过记录原始顺序实现稳定性
  • 比直接使用stable_sort更直观
    
    

• ‌比较函数设计‌：

  
  
  • 先比较成绩
  • 成绩相同再比较输入顺序
    
    

• ‌时间复杂度‌：

  
  
  • sort算法平均O(nlogn)
  • 适合n≤200的数据规模
    
    

四、完整代码

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespACe std;
   
5. 
   
6. struct Student {
   
7.     string name;
   
8.     int score;
   
9.     int order;  // 记录输入顺序
   
10. };
    
11. 
    
12. bool cmp_asc(const Student& a, const Student& b) {
    
13.     if (a.score != b.score) return a.score < b.score;
    
14.     return a.order < b.order;  // 成绩相同按输入顺序
    
15. }
    
16. 
    
17. bool cmp_desc(const Student& a, const Student& b) {
    
18.     if (a.score != b.score) return a.score > b.score;
    
19.     return a.order < b.order;  // 成绩相同按输入顺序
    
20. }
    
21. 
    
22. int main() {
    
23.     int n, op;
    
24.     cin >> n >> op;
    
25. 
    
26.     vector<Student> students(n);
    
27.     for (int i = 0; i < n; i++) {
    
28.         cin >> students[i].name >> students[i].score;
    
29.         students[i].order = i;  // 记录原始顺序
    
30.     }
    
31. 
    
32.     // 根据排序方式选择比较函数
    
33.     if (op == 1) {
    
34.         sort(students.begin(), students.end(), cmp_asc);
    
35.     } else {
    
36.         sort(students.begin(), students.end(), cmp_desc);
    
37.     }
    
38. 
    
39.     // 输出结果
    
40.     for (const auto& s : students) {
    
41.         cout << s.name << " " << s.score << endl;
    
42.     }
    
43. 
    
44.     return 0;
    
45. }

复制代码

五、常见错误

• 忘记处理相同成绩的情况
• 比较函数逻辑错误
• 输入顺序记录错误
  
  

扩展思考

• 如何支持多关键字排序？
• 如何处理大规模数据排序？
• 如何实现自定义排序规则的通用方案？
  
  

来源：牛客网4854题：从零掌握稳定排序：学生成绩排序算法详解