稳定性有什么用

稳定性在"多次排序"时特别有用。比如成绩单先按姓名排好，再按成绩排一次；如果第二次排序是稳定的，同分的同学之间就还保持着姓名顺序——一次排序顺带保留了上一步的成果。下面用"原始座位号"来演示这个效果：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Stu { int score, seat; };            // seat 是原来的座位号
int main() {
    vector<Stu> v = {{90, 1}, {85, 2}, {90, 3}, {85, 4}};
    stable_sort(v.begin(), v.end(),
        [](Stu a, Stu b){ return a.score > b.score; });
    for (auto s : v) cout << s.score << "号座" << s.seat << "  ";
    // 90号座1  90号座3  85号座2  85号座4：同分仍按原座位号
}

如果这里换成不稳定的排序，同分同学的先后就可能被打乱。凡是要"保留上一层顺序"，就一定选稳定排序。