sort函数

讲义主线

sort 是 C++ 里最常用的排序函数。
这一讲只记三件事：怎么写、排哪里、怎么自定义规则。

本页看什么

1. sort 的基本格式
2. 从小到大和从大到小怎么写
3. 最常见的 4 个坑

---

1. sort 是做什么的

sort 可以把一段数据按规则排好。
默认是从小到大排序。

它比手写冒泡、选择、插入排序更快。
比赛里只要题目允许，通常优先考虑 sort。

一句话理解

sort = 把一段区间重新排成有序状态。

---

2. 基本写法

sort(起始位置, 结束位置);

这里最重要的是：

• 起始位置要写到第一个元素
• 结束位置要写到最后一个元素的下一个位置

记忆句

sort(a + 1, a + n + 1) 才是给 a[1] 到 a[n] 排序。

数组示例

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
 
    sort(a.begin() + 1, a.begin() + n + 1);
 
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " \n"[i == n];
    }
    return 0;
}

普通数组写法

int a[105];
sort(a + 1, a + n + 1);

vector 写法

vector<int> a(n);
sort(a.begin(), a.end());

---

3. 从小到大和从大到小

从小到大

这是默认规则。

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

从大到小

可以加一个比较规则：

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

课堂记忆

不写第三个参数，默认升序。
写 greater<int>()，就是降序。

---

4. 自定义排序规则

有些题不是单纯比数字大小。
比如：

• 先按分数从大到小排
• 分数相同，再按学号从小到大排

这时要自己写比较函数。

例子

#include <bits/stdc++.h>
using namespace std;
 
struct Student {
    int id;
    int score;
};
 
bool cmp(Student a, Student b) {
    if (a.score != b.score) return a.score > b.score;
    return a.id < b.id;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<Student> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].id >> a[i].score;
    }
 
    sort(a.begin(), a.end(), cmp);
 
    for (int i = 0; i < n; i++) {
        cout << a[i].id << " " << a[i].score << "\n";
    }
    return 0;
}

比较函数在做什么

cmp(a, b) 返回 true，表示 a 应该排在 b 前面。

---

5. 常见坑

最容易写错的地方

1. 结束位置少写了 +1
2. 把升序和降序写反
3. 比较函数没有处理“相等时怎么办”
4. 只想排一部分数据，却把整段都排了

坑 1：区间写错

如果你想排 a[1] 到 a[n]，要写：

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

不是：

sort(a + 1, a + n);

因为后一个位置本身不会被排进去。

坑 2：比较函数乱写

比较函数要稳定表达“谁应该在前”。
不要一会儿按这个规则，一会儿按那个规则。

---

6. 什么时候用 sort

适合直接用 sort 的情况：

• 给一串数从小到大排序
• 排名次
• 去重前先排序
• 按多个关键字排序

不适合直接只靠 sort 解决的情况：

• 题目要求你手写某种基础排序
• 数据是动态变化的，边修改边查询

---

7. 课上先记这几行

核心代码卡片

升序：

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

降序：

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

vector：

sort(a.begin(), a.end());

---

8. 小练习

1. 输入 n 个整数，用 sort 从小到大输出。
2. 输入 n 个整数，用 sort 从大到小输出。
3. 输入若干学生的学号和分数，按“分数高的在前，学号小的在前”排序。

课堂收束

sort 不是让你记很长的代码。
真正要记住的是：区间怎么写，规则怎么写。