排序

排序

1. 基础排序（选择 / 冒泡 / 插入）

• 思路简单
• 代码好写
• 但效率一般（通常是 $O(n^2)$）

当 $n$ 比较大（例如 $10^5$）时，基础排序会超时，此时应该使用 sort 或更高级的排序方法。

---



1.1 选择排序



核心思路：

• 每一轮在“未排序区间”里找到最小值
• 把它放到当前应该放的位置

例如从小到大排序：

• 第 $1$ 轮找最小值放到 a[1]
• 第 $2$ 轮找剩下最小值放到 a[2]
• ...

时间复杂度：

• $O(n^2)$



参考代码（数组下标从 $1$ 开始）



~~~cpp
for (int i = 1; i <= n; i++) {
int pos = i; // 最小值位置
for (int j = i + 1; j <= n; j++) {
if (a[j] < a[pos]) pos = j;
}
swap(a[i], a[pos]);
}

~~~

---



1.2 冒泡排序



核心思路：

• 每一轮不断比较相邻的两个元素
• 如果顺序不对就交换
• 一轮结束后，最大值会“冒泡”到最右侧

时间复杂度：

• $O(n^2)$



参考代码（数组下标从 $1$ 开始）



~~~cpp
for (int i = 1; i < n; i++) {
for (int j = 1; j <= n - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
}
}
}

~~~

---



1.3 插入排序



核心思路：

• 维护一个“已经排好序的前缀”
• 依次把下一个元素插入到合适位置

时间复杂度：

• $O(n^2)$（在接近有序时比较快）



参考代码（数组下标从 $1$ 开始）



~~~cpp

for (int i = 2; i <= n; i++) {
int x = a[i];
int j = i - 1;
while (j >= 1 && a[j] > x) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
}

}
~~~

---



2. 桶排序（Bucket Sort / 计数排序）



桶排序适合数据满足：

• 数字值域不大
• 待排序数字都是整数

常见形式是“计数排序”：

• cnt[x] 表示数字 $x$ 出现了多少次

时间复杂度：

• $O(n+V)$（$V$ 是值域大小）
• 桶排序在数字值域小的情况下复杂度十分优秀

---



2.1 基本思路



例如给你 $n$ 个数，且每个数满足：

• $0\le a[i]\le 100000$

可以用数组统计出现次数：

1) 读入数字 $x$，执行 cnt[x]++
2) 最后从小到大遍历所有值 $x$，输出 cnt[x] 次

---



2.2 参考代码（从小到大排序输出）



~~~cpp
const int MAXV = 100000;
const int N = 100005;
int cnt[MAXV + 5];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
cnt[x]++;
}
for (int x = 0; x <= MAXV; x++) {
while (cnt[x] > 0) {
cout << x << " ";
cnt[x]--;
}
}
return 0;
}
~~~

---



2.3 桶排序的优缺点



优点：

• 非常快（尤其是值域较小的时候）
• 思路很简单

缺点：

• 值域太大时开数组会爆内存
• 一般只适合整数，不适合小数

---



3. sort 排序



在信奥竞赛中，最常用的排序方式就是sort排序：

• sort(区间起点, 区间终点 + 1);

它的排序复杂度：

• $O(n\log n)$

通常可以轻松处理 $n=10^5$ 或更大。

---



3.1 基本用法



从小到大排序：

~~~cpp
sort(a + 1, a + n + 1);
~~~

从大到小排序：

~~~cpp
sort(a + 1, a + n + 1, greater<int>());
~~~





3.2 自定义比较规则



如果想从大到小：

~~~cpp
bool cmp(int x, int y) {//x在y左边时候返回true
return x > y; //降序排序希望x比y更大
}

sort(a + 1, a + n + 1,cmp);
~~~

这种写法叫“自定义比较函数”，也可以结合题目要求定义不同的比较函数。

---



4. 结构体排序



很多题不是排序一个数字，而是排序“一个人/一条记录”，比如：

• 学生：姓名、语文、数学、总分
• 选手：编号、得分、罚时
• 商品：价格、销量、评价

这种时候就要用结构体（struct）来存每条记录，然后排序。

---



4.1 结构体定义



例子：定义一个学生结构体

~~~cpp
struct Student {
int id;
int score;
};
~~~

如果你开数组：

~~~cpp
Student a[N];
~~~

---



4.2 结构体排序规则（自定义 cmp）



常见要求：

• 先按 score 从大到小
• 若 score 相同，再按 id 从小到大

对应的比较函数：

~~~cpp
bool cmp(Student x, Student y) {
if (x.score != y.score) return x.score > y.score;
return x.id < y.id;
}
~~~

---



4.3 参考代码



~~~cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

struct Student {
int id;
int score;
};

Student a[N];

bool cmp(Student x, Student y) {
if (x.score != y.score) return x.score > y.score; // 分数高的排前面
return x.id < y.id; // 分数相同，id 小的排前面
}

int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].id >> a[i].score;
}

sort(a + 1, a + n + 1, cmp);

for (int i = 1; i <= n; i++) {
cout << a[i].id << " " << a[i].score << "\n";
}
return 0;
}
~~~

---



4.4 结构体排序常见技巧总结



1) 优先级要写清楚
一般是“主要关键字优先，次要关键字再比较”。

2) cmp 的返回值含义
cmp(x, y) 返回 true 表示：x 应该排在 y 的前面。

3) 排序区间别写错
数组从 $1$ 开始一般用：

• sort(a + 1, a + n + 1, cmp);