S2 排序的稳定性与原下标技巧（20 分钟补丁）

这是什么： 当两个元素"一样大"时，排完序谁在前面？这件事 sort 不保证，而有些题的答案就取决于它。

为什么现在补： L02 已经教过结构体 + 自定义 cmp 多关键字排序（排队接水、奖学金），这部分你已经会了，本补丁不重复。缺的只有一块：稳定性。CSP-J 2021 T2 插入排序（P7910）整道题的钥匙就是这一个概念。

前置： L02 的 sort + bool cmp。

一、最小可用模板

1.1 什么叫"稳定"

稳定排序 = 比较起来相等的元素，排完序后仍然保持它们原来的先后顺序。

看一个例子。三个学生按分数排序，李四和王五都是 90 分：

排序前：  张三 80    李四 90    王五 90
                     ↑ 李四本来在王五前面

稳定排序：李四 90    王五 90    张三 80     ← 李四仍在王五前
不稳定：  王五 90    李四 90    张三 80     ← 顺序被打乱了，也不算错

⚠️ C++ 的 sort 不保证稳定。 它内部是快速排序，相等元素的顺序是"随机"的——在你电脑上跑出一个结果，在评测机上可能是另一个。

📝 stable_sort 保证稳定，用法和 sort 一模一样，代价是稍慢一点（对 CSP-J 的数据量完全够用）。

#include <bits/stdc++.h>
using namespace std;

struct Student {
    int id, score;
};

bool cmp(Student x, Student y) {
    return x.score > y.score;      // 只按分数降序，没管同分怎么办
}

int main() {
    Student s[3] = {{1, 80}, {2, 90}, {3, 90}};
    stable_sort(s, s + 3, cmp);    // 换成 sort 的话，2 和 3 谁在前不确定
    for (int i = 0; i < 3; i++) {
        cout << s[i].id << " ";
    }
    cout << endl;                  // 稳定排序保证输出 2 3 1
    return 0;
}

1.2 更好的办法：把原下标当最后一个关键字

stable_sort 要额外记一个函数名。有个更通用的办法，用回你在 L02 已经会的多关键字写法：把每个元素的原始下标存进结构体，在 cmp 的最后一层比它。

#include <bits/stdc++.h>
using namespace std;

struct Item {
    int val;      // 值
    int idx;      // 它原来在第几个位置
};

bool cmp(Item x, Item y) {
    if (x.val != y.val) return x.val < y.val;   // 主关键字：值小的在前
    return x.idx < y.idx;                       // 值相同：原来靠前的仍靠前
}

int main() {
    int a[5] = {30, 10, 20, 10, 20};
    Item b[5];
    for (int i = 0; i < 5; i++) {
        b[i].val = a[i];
        b[i].idx = i;              // 读入的时候顺手记下原下标
    }
    sort(b, b + 5, cmp);           // 普通 sort 就够了
    for (int i = 0; i < 5; i++) {
        cout << b[i].val << "(原第" << b[i].idx << "个) ";
    }
    cout << endl;
    // 10(原第1个) 10(原第3个) 20(原第2个) 20(原第4个) 30(原第0个)
    return 0;
}

📝 加了原下标这一层之后，任意两个元素都不再"相等"了——cmp 有了唯一确定的答案，排序结果就是唯一的，用 sort 还是 stable_sort 都一样。

📝 这个技巧还有个附赠好处：排完之后你还知道每个元素原来在哪。 需要输出"第几号"的题（L02 的排队接水就是）全靠它。

二、两个坑

⚠️ 坑 1：cmp 在"相等"时返回 true，程序会崩溃。

bool cmp(Item x, Item y) {
    return x.val <= y.val;      // 用了 <=
}

sort 要求 cmp(x, x) 必须是 false（"自己不能排在自己前面"）。写 <= 的话 cmp(x, x) 是 true，sort 会读到数组外面去，运行时直接崩溃，而且编译器一个字都不报。

📝 cmp 里只用 < 或 >，永远不加等号。 想处理相等的情况，就像 1.2 那样再加一层关键字。

⚠️ 坑 2：本地对、评测机错，而且你查不出原因。

同分顺序不确定这个坑最阴险的地方是：你本地跑样例可能一直是对的。不同的编译器版本、不同的数据规模，sort 内部走的分支都不一样。

📝 只要题目里可能出现"两个元素比较起来相等"，就必须自己把顺序定死——要么 stable_sort，要么加原下标关键字。不要赌。

三、配套真题

CSP-J 2021 T2 插入排序（洛谷 P7910） —— 给一个数组，支持两种操作：① 修改某个位置的值；② 询问"做完插入排序后，原来第 x 个元素跑到了第几位"。

这题的钥匙就是本补丁的内容：题目给的插入排序只在严格小于时才交换，所以它是一个稳定排序。于是"插入排序后的位置"等价于按 (值升序, 原下标升序) 排完序之后的位置——正是 1.2 那个模板。

注意数据范围：n ≤ 8000，Q ≤ 2×10⁵，但类型一（修改）最多只有 5000 次。这句话在暗示你什么复杂度可以接受，想清楚再动手。

思路提示见 S8_真题分级提示.md，代码自己写。

四、30 秒自测

1. sort 和 stable_sort 的区别是什么？
2. bool cmp(int x, int y) { return x >= y; } 有什么问题？
3. 想让排序结果唯一确定，除了用 stable_sort，还能怎么做？

以后学： stable_sort 内部是归并排序，归并排序本身属于提高级（大纲 2.2.4），本次冲刺只要会用不用会写。