信息学奥赛刷题避坑指南：多关键字排序中的stable_sort与自定义cmp陷阱
在信息学竞赛的赛场上，排序算法就像一把双刃剑——用得好可以轻松斩获高分，用不好则可能让你在看似简单的题目上栽跟头。特别是当遇到需要先按成绩降序，再按编号升序这类多关键字排序问题时，很多选手都会在自定义比较函数和排序稳定性上踩坑。今天我们就以经典的"分数线划定"问题为例，深入剖析这些陷阱背后的原理。
1. 多关键字排序的常见误区
参加过NOIP/NOI系列比赛的选手应该都熟悉这类场景：给定n位考生的编号和成绩，要求先按成绩从高到低排序，成绩相同时按编号从小到大排序。看似简单的需求，在实际编码时却暗藏玄机。
1.1 错误的自定义比较函数写法
很多初学者会尝试这样写比较函数：
bool cmp(Stu a, Stu b) { if(a.s != b.s) return a.s > b.s; return a.k < b.k; }看起来逻辑清晰，但在某些情况下会产生意想不到的结果。问题出在比较函数的严格弱序要求上。C++标准要求比较函数必须满足以下条件：
- 反自反性：
cmp(a,a)必须为false - 反对称性：如果
cmp(a,b)为true，则cmp(b,a)必须为false - 传递性：如果
cmp(a,b)和cmp(b,c)都为true，则cmp(a,c)必须为true
1.2 实际案例分析
假设有以下三个学生数据：
| 编号(k) | 成绩(s) |
|---|---|
| 1001 | 85 |
| 1002 | 85 |
| 1003 | 90 |
使用上述cmp函数排序后，输出顺序应该是：1003(90)、1001(85)、1002(85)。但如果cmp函数实现有误，可能会导致1002排在1001前面，这与题目要求相悖。
2. stable_sort的妙用场景
当简单的sort无法满足需求时，stable_sort就派上用场了。两者的核心区别在于：
| 特性 | std::sort | std::stable_sort |
|---|---|---|
| 时间复杂度 | O(nlogn) | O(nlogn)或O(nlog²n) |
| 稳定性 | 不稳定 | 稳定 |
| 内存使用 | 原地排序 | 可能需要额外空间 |
2.1 何时需要稳定排序
在分数线划定问题中，如果我们先按编号排序，再按成绩排序，使用stable_sort可以保证：
- 第一次排序后，所有学生按编号升序排列
- 第二次排序时，相同成绩的学生会保持之前的相对顺序（即编号小的仍然在前）
// 先按编号排序 stable_sort(stu+1, stu+1+n, [](Stu a, Stu b){return a.k < b.k;}); // 再按成绩排序 stable_sort(stu+1, stu+1+n, [](Stu a, Stu b){return a.s > b.s;});2.2 性能考量
虽然stable_sort能保证稳定性，但在大规模数据下可能比sort稍慢：
- 数据量<1000时，差异可以忽略
- 数据量在5000左右时，stable_sort可能慢10-20%
- 极端情况下(1e6数据)，可能慢30-50%
在竞赛中，通常数据规模不会太大，所以使用stable_sort换取正确性是值得的。
3. 自定义比较函数的正确姿势
编写健壮的自定义比较函数需要注意以下几点：
3.1 参数传递方式
优先使用常量引用传递参数，避免不必要的拷贝：
bool cmp(const Stu &a, const Stu &b) { if(a.s != b.s) return a.s > b.s; return a.k < b.k; }3.2 处理边界情况
良好的比较函数应该处理所有可能的输入组合：
- 完全相同对象的比较
- 部分属性相同的比较
- 所有属性都不同的比较
3.3 Lambda表达式写法
C++11后，可以直接在sort调用处使用lambda表达式：
sort(stu+1, stu+1+n, [](const Stu &a, const Stu &b) { return tie(b.s, a.k) < tie(a.s, b.k); });这里使用了tie创建临时元组进行比较，代码更简洁但可能影响可读性。
4. 实战技巧与平台差异
不同在线评测平台对排序的实现可能有细微差别，需要注意：
4.1 OpenJudge的特殊情况
在OpenJudge上提交时，以下几点需要特别注意：
- 某些老题可能使用较旧编译器版本
- 内存限制可能比洛谷更严格
- 输出格式要求可能更精确
4.2 洛谷的优化建议
洛谷的现代评测环境支持C++17特性，可以这样优化：
struct Stu { int k, s; auto tied() const { return tuple(-s, k); } }; ... sort(stu+1, stu+1+n, [](const Stu &a, const Stu &b){ return a.tied() < b.tied(); });4.3 调试技巧
当排序结果不符合预期时，可以：
- 打印中间排序结果
- 检查比较函数的所有可能分支
- 使用小规模测试数据验证
- 对比stable_sort和sort的结果差异
5. 其他排序方法对比
除了标准库的排序算法，选手也可以考虑其他实现方式：
5.1 冒泡排序实现
虽然时间复杂度较高(O(n²))，但在小数据量(如n≤1000)时足够使用：
for(int i=1; i<=n-1; ++i) for(int j=1; j<=n-i; ++j) if(s[j]<s[j+1] || (s[j]==s[j+1]&&k[j]>k[j+1])) swap(s[j],s[j+1]), swap(k[j],k[j+1]);5.2 计数排序+插入排序
当成绩范围有限时(如0-100分)，可以采用：
vector<int> score[101]; // 每个分数对应一个编号列表 for(int i=0; i<n; ++i) { int k, s; cin >> k >> s; // 使用lower_bound保持插入有序 auto it = lower_bound(score[s].begin(), score[s].end(), k); score[s].insert(it, k); }5.3 性能对比表格
| 方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 代码复杂度 |
|---|---|---|---|---|
| std::sort+cmp | O(nlogn) | O(1) | 取决于cmp | 中等 |
| std::stable_sort | O(nlogn) | O(n) | 稳定 | 简单 |
| 冒泡排序 | O(n²) | O(1) | 稳定 | 简单 |
| 计数+插入排序 | O(n+k) | O(n+k) | 稳定 | 较高 |
6. 常见问题解答
Q：为什么我的排序结果在本地和OJ上不一样？
A：可能原因包括：
- 比较函数不符合严格弱序
- 使用了未定义行为（如越界访问）
- 不同平台STL实现差异
Q：什么时候必须用stable_sort？
A：当且仅当：
- 需要保持相等元素的原始顺序
- 采用多趟排序策略时
- 题目明确要求稳定排序
Q：自定义比较函数导致TLE怎么办？
A：优化建议：
- 改用引用传递参数
- 简化比较逻辑
- 避免在cmp中调用复杂函数
在实际刷题过程中，我发现很多选手会在类似分数线划定这样的基础题目上意外失分。有一次在帮学弟调试代码时，发现他的排序结果总是偶尔出错，最终排查发现是比较函数没有处理好所有边界情况。这也提醒我们，看似简单的排序问题往往隐藏着不少陷阱，需要我们在平时练习中就养成严谨的编码习惯。
