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

一、问题分析

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

二、核心算法

1. ‌数据结构设计‌：

• 使用结构体Student存储学生信息

• 额外添加order字段记录输入顺序

2. ‌自定义比较函数‌：

• cmp_asc：升序比较函数

• cmp_desc：降序比较函数

• 当成绩相同时，比较原始输入顺序

3. ‌STL sort算法‌：

• 利用C++标准库的sort函数

• 根据用户选择传入不同的比较函数

三、关键点解析

1. ‌稳定排序实现‌：

• 通过记录原始顺序实现稳定性

• 比直接使用stable_sort更直观

2. ‌比较函数设计‌：

• 先比较成绩

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

3. ‌时间复杂度‌：

• 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[i].name >> students[i].score;
        students[i].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;
}

五、常见错误

1. 忘记处理相同成绩的情况

2. 比较函数逻辑错误

3. 输入顺序记录错误

扩展思考

1. 如何支持多关键字排序？

2. 如何处理大规模数据排序？

3. 如何实现自定义排序规则的通用方案？