信息学奥赛实战：从结构体排序到多关键字稳定排序的算法演进-拓冰建站

1. 结构体排序：信息学奥赛的入门必修课

参加信息学奥赛的同学一定对结构体排序不陌生，这是竞赛中最基础也最常考的知识点之一。记得我第一次参加NOI选拔赛时，第一道编程题就是要求对学生的成绩进行排序。当时我手忙脚乱地写了个冒泡排序，结果因为没处理好同分情况被扣了不少分。

结构体排序的核心在于理解"比较规则"。比如我们要处理的学生成绩排序问题，每个学生有姓名和分数两个属性。在C++中，我们可以这样定义结构体：

struct Student { string name; int score; };

这个简单的结构体包含了我们需要处理的所有数据。但关键在于，计算机并不知道该如何比较两个Student对象的大小关系。这就是我们需要自定义比较函数的原因。在竞赛中，常见的比较规则包括：

按分数从高到低排序
分数相同时按姓名字典序排序
特殊情况处理（如缺考记为0分等）

2. 单条件排序的三种实现方式

2.1 冒泡排序：最直观的理解方式

虽然冒泡排序效率不高（时间复杂度O(n²)），但它能帮助我们最直观地理解排序过程。在成绩排序问题中，冒泡排序的实现是这样的：

void bubbleSort(Student stu[], int n) { for(int i=0; i<n-1; i++) { for(int j=0; j<n-i-1; j++) { if(stu[j].score < stu[j+1].score) { swap(stu[j], stu[j+1]); } } } }

这个基础版本只能按分数排序。在实际竞赛中，我们需要处理同分情况，这时比较条件就要更复杂些：

if(stu[j].score < stu[j+1].score || (stu[j].score == stu[j+1].score && stu[j].name > stu[j+1].name)) { swap(stu[j], stu[j+1]); }

2.2 插入排序：小规模数据的高效选择

当数据量较小时（n≤1000），插入排序往往比更复杂的算法表现更好。它的实现也很直观：

void insertionSort(Student stu[], int n) { for(int i=1; i<n; i++) { Student key = stu[i]; int j = i-1; while(j>=0 && (stu[j].score < key.score || (stu[j].score == key.score && stu[j].name > key.name))) { stu[j+1] = stu[j]; j--; } stu[j+1] = key; } }

插入排序的优势在于它对近乎有序的数据排序非常高效，时间复杂度可以达到O(n)。在竞赛中，如果题目暗示数据可能部分有序，插入排序是个不错的选择。

2.3 STL sort函数：竞赛中的利器

C++标准库中的sort函数是竞赛选手的最佳伙伴。它采用混合排序算法（通常是快速排序+插入排序），平均时间复杂度为O(nlogn)。使用起来非常简单：

bool cmp(const Student &a, const Student &b) { return a.score > b.score || (a.score == b.score && a.name < b.name); } sort(stu, stu+n, cmp);

这里要注意比较函数的写法。返回true表示a应该排在b前面。对于多关键字排序，我们需要用逻辑或(||)连接多个条件。

3. 多关键字排序的两种策略

3.1 方法一：整合条件法

这是最直观的方法，把多个排序条件整合到一个比较函数中。比如先按分数降序，再按姓名升序：

bool cmp(const Student &a, const Student &b) { if(a.score != b.score) return a.score > b.score; else return a.name < b.name; }

这种方法的优点是直观易懂，一次排序就能得到正确结果。但它要求排序算法是稳定的（即相等元素的相对顺序保持不变）。虽然STL的sort不保证稳定，但在实际应用中通常表现良好。

3.2 方法二：多趟稳定排序法

更可靠的做法是使用稳定的排序算法进行多趟排序。这里的关键是排序顺序：应该先排次要关键字，再排主要关键字。例如：

// 先按姓名排序 stable_sort(stu, stu+n, [](const Student &a, const Student &b){ return a.name < b.name; }); // 再按分数排序 stable_sort(stu, stu+n, [](const Student &a, const Student &b){ return a.score > b.score; });

这种方法虽然需要多次排序，但能确保最终结果的正确性。在OpenJudge的很多题目中，明确要求使用稳定排序，这时就必须采用这种方法。

4. 算法选择与性能优化

4.1 根据数据规模选择算法

在竞赛中，我们需要根据题目给出的数据范围选择合适的算法：

n ≤ 1,000：冒泡、插入等O(n²)算法都可以
1,000 < n ≤ 100,000：必须使用O(nlogn)算法如STL sort
n > 100,000：可能需要考虑基数排序等线性算法

4.2 输入输出优化

对于大规模数据排序，IO往往成为瓶颈。可以使用以下技巧加速：

ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

4.3 内存访问优化

对于非常大的结构体数组，频繁交换元素会很耗时。这时可以使用指针数组或索引数组来排序：

Student stu[MAXN]; int idx[MAXN]; // 初始化idx数组 iota(idx, idx+n, 0); // 排序索引数组 sort(idx, idx+n, [&](int a, int b){ return stu[a].score > stu[b].score || (stu[a].score == stu[b].score && stu[a].name < stu[b].name); });

5. 实战案例分析

让我们看一个OpenJudge上的经典题目：NOI 1.10 03:成绩排序。题目要求先按分数降序排列，分数相同的按输入顺序排列。

这个题目有两个关键点：

需要稳定排序来保持同分学生的原始顺序
输入规模可能很大（n≤100,000）

最优解法是使用stable_sort：

#include <bits/stdc++.h> using namespace std; struct Student { string name; int score; int id; // 记录原始顺序 }; bool cmp(const Student &a, const Student &b) { return a.score > b.score || (a.score == b.score && a.id < b.id); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<Student> stu(n); for(int i=0; i<n; i++) { cin >> stu[i].name >> stu[i].score; stu[i].id = i; } stable_sort(stu.begin(), stu.end(), cmp); for(const auto &s : stu) { cout << s.name << " " << s.score << "\n"; } return 0; }

这个解法在保证正确性的同时，时间复杂度是O(nlogn)，能够处理最大规模的数据。