题目

编写程序，设计学生考试成绩记录（学号、姓名、总分）。对比 std::sort 与 std::stable_sort 的行为差异：验证当仅根据总分进行单级排序时，不稳定排序 std::sort 可能打乱同分考生的原始输入登记顺序；而 std::stable_sort（基于归并排序）绝对保证等价值元素的相对次序保持不变。

输入格式：无需外部输入。

输出格式：比对稳定排序与不稳定排序在同分数据上的先后排位次序。

数据范围与约定：算法稳定性、归并排序开销与多级复合规则。

思路与算法

1. 排序稳定性的定义
若输入序列中存在两个相同键值的元素 \(A\) 和 \(B\)，且在原序列中 \(A\) 处于 \(B\) 前面；若排序后 \(A\) 依然严格位于 \(B\) 前面，则该排序算法是“稳定”的（Stable）。

2. 底层算法开销
std::sort 采用内省快排，空间复杂度为 O(log N)，平均时间 O(N log N) 但不稳定；std::stable_sort 采用自适应归并排序，若内存充足时消耗 O(N) 缓冲区保证线性对数时间，若内存不足则退化为 O(N (log N)^2) 原地归并。

3. 多级排序与稳定排序的关系
有了稳定排序，我们可以先对次要关键字（如姓名）排一次，再对主要关键字（如成绩）排一次，自然达成多级排序效果。

完整程序

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

struct Candidate {
    int id;
    std::string name;
    int score;
};

void printCandidates(const std::vector<Candidate>& list, const std::string& label) {
    std::cout << "=== " << label << " ===\n";
    for (const auto& c : list) {
        std::cout << "工号: " << c.id << " \t姓名: " << c.name << " \t成绩: " << c.score << "\n";
    }
    std::cout << "\n";
}

int main() {
    // 原始序列中，同分 85 的先后顺序为：张三 (101) -> 王五 (103) -> 钱七 (105)
    std::vector<Candidate> data = {
        {101, "张三", 85},
        {102, "李四", 95},
        {103, "王五", 85},
        {104, "赵六", 90},
        {105, "钱七", 85}
    };

    auto dataSort = data;
    auto dataStable = data;

    // 仅按成绩从高到低降序
    auto scoreDesc = [](const Candidate& a, const Candidate& b) {
        return a.score > b.score;
    };

    // 1. std::sort (可能打乱同分顺序)
    std::sort(dataSort.begin(), dataSort.end(), scoreDesc);
    printCandidates(dataSort, "std::sort 排序结果 (同分相对顺序可能无法保证)");

    // 2. std::stable_sort (严格保持原录入相对顺序)
    std::stable_sort(dataStable.begin(), dataStable.end(), scoreDesc);
    printCandidates(dataStable, "std::stable_sort 稳定排序结果 (同分 85 分保持张三->王五->钱七)");

    return 0;
}

运行示例

输出：

=== std::sort 排序结果 (同分相对顺序可能无法保证) ===
工号: 102 	姓名: 李四 	成绩: 95
工号: 104 	姓名: 赵六 	成绩: 90
工号: 101 	姓名: 张三 	成绩: 85
工号: 103 	姓名: 王五 	成绩: 85
工号: 105 	姓名: 钱七 	成绩: 85

=== std::stable_sort 稳定排序结果 (同分 85 分保持张三->王五->钱七) ===
工号: 102 	姓名: 李四 	成绩: 95
工号: 104 	姓名: 赵六 	成绩: 90
工号: 101 	姓名: 张三 	成绩: 85
工号: 103 	姓名: 王五 	成绩: 85
工号: 105 	姓名: 钱七 	成绩: 85