排序

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

基础排序包括选择排序，冒泡排序，插入排序，它们的共同特点是：

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

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

---

1.1 选择排序

核心思路：

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

例如从小到大排序：

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

时间复杂度：

• $O(n^2)$

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

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$ 开始）

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$ 开始）

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 参考代码（从小到大排序输出）

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 基本用法

从小到大排序：

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

从大到小排序：

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

3.2 自定义比较规则

如果想从大到小：

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 结构体定义

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

struct Student {
    int id;
    int score;
};

如果你开数组：

Student a[N];

---

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

常见要求：

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

对应的比较函数：

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

---

4.3 参考代码

#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);

【前置知识点】
1、函数

【后置衔接知识点】
1、递归
2、贪心

【思维导图】

【题目知识点分类】