11.8 stable_sort：穩定排序（延伸知識）

先做一個實驗。20 位同學依座號順序代號 A ~ T，分數只有兩種：A、C、E……考 60，B、D、F……考 90，交錯出現。用「只看分數」的比較函式排序，分數相同的同學誰先誰後——sort 和它的兄弟 stable_sort 給出不同的答案：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 20 位同學依座號順序代號 A ~ T；分數只有 60 和 90 兩種交錯出現
bool cmp(pair<int,char> x, pair<int,char> y) {
    return x.first < y.first;      // 只看分數；分數相同時「不表態」
}

int main() {
    vector<pair<int,char>> v;
    for (int i = 0; i < 20; i++) {
        int score = 60;
        if (i % 2 == 1) score = 90;               // B、D、F……考 90
        v.push_back({score, (char)('A' + i)});    // （分數, 代號）
    }
    vector<pair<int,char>> a = v, b = v;

    sort(a.begin(), a.end(), cmp);
    stable_sort(b.begin(), b.end(), cmp);

    cout << "sort:        ";
    for (int i = 0; i < 20; i++) cout << a[i].second;
    cout << '\n';
    cout << "stable_sort: ";
    for (int i = 0; i < 20; i++) cout << b[i].second;
    cout << '\n';
    return 0;
}

執行結果：

sort:        ACSEGQIKOMTRPNLJHFDB
stable_sort: ACEGIKMOQSBDFHJLNPRT

兩行都是「60 分的在前、90 分的在後」——排序都沒排錯。差別在相等元素內部的順序：

• stable_sort 那行，60 分那群是 ACEGIKMOQS、90 分那群是 BDFHJLNPRT——完全保持原本的座號順序。
• sort 那行，兩群內部的順序被打亂了。

這就是穩定排序（stable sort）的定義：比較起來相等的元素，排序後保持它們原本的相對順序。stable_sort 保證這件事，sort 不保證——注意是「不保證」：資料少的時候 sort 常常碰巧沒亂，一換大測資就原形畢露，這種「小測資對、大測資錯」的 bug 最會咬人。

什麼時候在意穩定？當「原本的順序」本身就是資訊的時候。常見的形式：題目要求「分數相同者，先輸入的排前面」——輸入順序就是隱形的次要關鍵字。這時有兩條路：把輸入編號一起存進 pair、在比較函式裡明寫「分數相同比編號」；或者什麼都不用多寫，直接 stable_sort——它自動用「原本的順序」當最後的裁判。（代價是 stable_sort 比 sort 稍慢、多吃一些記憶體，但同樣是 O(n \log n) 等級，一般題目感覺不出差別。）

動手試試看：解掉怪物——技能每次打「目前血量最高」的怪物，求死亡順序。提示：先用 % 想想，每隻怪物被打到「再一刀就死」時剩多少血（跟 a_i 除以 k 的餘數有關；整除的情況要想成剩 k）；剩得多的先死，而剩得一樣多的怪物，誰先死看編號——「相等時保持原本順序」，正是 stable_sort 出場的時機。