牛客4854题：学生信息排序算法实现与优化

19339201706

一、题目解读

牛客4854题要求对n个学生的姓名和成绩进行排序，操作op=1时按成绩升序，op=2时按成绩降序，若成绩相同则按原始输入顺序排序。题目核心在于处理双重排序条件：成绩优先级高于输入顺序，需设计合理的排序逻辑。

二、解题思路

1. 使用C++ STL的sort函数简化排序流程，关键在于自定义比较函数。

2. 定义Student结构体存储姓名、成绩及输入顺序（order字段），确保成绩相同时可依据order排序。

3. 根据op选择升序（cmp_asc）或降序（cmp_desc）比较函数，二者均优先比较成绩，成绩相同则比较order。

三、解题步骤

1. 输入学生数量n与排序操作op。

2. 创建Student数组并读取姓名、成绩，同时记录当前输入顺序（i）。

3. 根据op选择排序方式：

    op=1调用sort(students, cmp_asc)升序排序；

    op=2调用sort(students, cmp_desc)降序排序。

4. 遍历排序后的students输出姓名与成绩。

四、代码及注释

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. // 升序比较函数
    
13. bool cmp_asc(const Student &a, const Student &b) {
    
14.     if(a.score!= b.score) return a.score < b.score;  // 优先按成绩升序
    
15.     return a.order < b.order;  // 成绩相同按输入顺序
    
16. }
    
17. 
    
18. // 降序比较函数
    
19. bool cmp_desc(const Student &a, const Student &b) {
    
20.     if(a.score!= b.score) return a.score > b.score;  // 优先按成绩降序
    
21.     return a.order < b.order;  // 成绩相同按输入顺序
    
22. }
    
23. 
    
24. int main() {
    
25.     int n, op;
    
26.     cin >> n >> op;  // 输入学生数与排序操作
    
27. 
    
28.     vector<Student> students(n);
    
29.     for(int i = 0; i < n; i++) {
    
30.         cin >> students[i].name >> students[i].score;
    
31.         students[i].order = i;  // 记录当前学生的输入顺序
    
32.     }
    
33.    
    
34.     // 根据op选择排序方式
    
35.     if(op == 1) {
    
36.         sort(students.begin(), students.end(), cmp_asc);
    
37.     } else {
    
38.         sort(students.begin(), students.end(), cmp_desc);
    
39.     }
    
40.    
    
41.     // 输出排序结果
    
42.     for(const auto &s : students) {
    
43.         cout << s.name << " " << s.score << endl;
    
44.     }
    
45.    
    
46.     return 0;
    
47. }

复制代码

五、总结

1. 自定义比较函数是sort函数处理复杂排序的核心，需明确优先级逻辑（成绩 > 输入顺序）。

2. 记录输入顺序的“order”字段巧妙解决成绩相同时的二重排序问题，避免额外数据结构。

3. 利用sort函数提升效率，避免手动编写冒泡/选择排序的复杂性与低效性。

4. 该解法兼顾代码简洁性与算法正确性，适合实际编程场景。

参考：牛客4854题：学生信息排序算法实现与优化