结构体与排序

当一条记录有多个相关字段（比如学生的姓名、学号、成绩），就用结构体把它们打包成一个整体，排序时按需要的字段比较，字段之间的对应关系不会乱。

struct Student {
    string name;
    int score;
};
Student a[105];
// 按成绩降序; 成绩相同再按姓名字典序升序
sort(a, a + n, [](const Student& x, const Student& y) {
    if (x.score != y.score) return x.score > y.score;
    return x.name < y.name;
});

多关键字排序就是在比较函数里按优先级依次判断：主关键字不同就用主关键字定序，相同再看次关键字。排序本身是 $O(n\log n)$。

坑：一是比较函数传参尽量用 const& 引用，避免每次比较都拷贝整个结构体（含 string 时尤其慢）；二是比较函数要满足严格弱序，相等情形必须返回 false，否则可能运行时崩溃；三是别在比较里写有副作用的代码，sort 会以不确定的次数和顺序调用它。