sort排序 知识点讲解

概念

排序，就是把一堆乱糟糟的数据，按照某个规则（比如从小到大，或者从大到小）重新排好序。想象一下你手里有一副扑克牌，刚发下来时顺序是乱的，如果你要把它们按花色和点数排整齐，这个过程就是排序。在编程里，我们面对的是数组，比如 [5, 2, 9, 1, 5]，如果我们想把它变成 [1, 2, 5, 5, 9]，就需要用到排序算法。

对于零基础的同学，你可能会问：为什么要排序？直接一个个比不行吗？其实，如果数据量很大（比如一百万个），两两比较需要比 $10^{12}$ 次，这太慢了。排序之后，数据有了“单调性”（就是排好序后，前面的数一定小于等于后面的数），这种有序性能带来巨大的便利：比如我们可以用二分查找在 $O(\log n)$ 的时间内找到某个数，或者用双指针在 $O(n)$ 的时间内解决很多原本需要 $O(n^2)$ 才能解决的问题。可以说，排序是信息学竞赛里性价比最高的“预处理”手段之一。

触发清单（看到这些信号第一时间想到本知识点）

定义

sort 是 C++ 标准库 <algorithm> 头文件里提供的函数，它能把一段范围内的元素按照指定的规则重新排列。默认情况下，它把元素从小到大排（升序）。

为什么"排序"这么重要：排序之后，数组就有了单调性。单调性带来三个能力：

1. 可以用二分查找（lower_bound）；

2. 可以用双指针（一头一尾往中间收）；

3. 可以用贪心（"先处理最大的"这类策略）。

️ 很多人只会 sort(a, a+n) 这一句，一遇到"按成绩排，成绩相同按学号排"就懵了。这节的重点不是 sort 本身，而是 自定义比较器和多关键字排序 —— 这才是编程题里真正要考的东西。

四种最常用的写法：

自定义比较器 cmp 的铁律：

bool cmp(const Node& x, const Node& y) {
 // 返回 true 表示「x 应该排在 y 前面」
 return x.key < y.key; // 升序
}

记住一句话：cmp(x, y) 返回 true 的意思不是"x < y"，而是"x 排在 y 前面"。 理解了这一点，多关键字排序就不会写错。

多关键字排序的写法（成绩降序，相同时学号升序）：

bool cmp(const Node& x, const Node& y) {
 if (x.score != y.score) return x.score > y.score; // 第一关键字：降序
 return x.id < y.id; // 第二关键字：升序
}

口诀：第一关键字不同，就按第一关键字决出胜负；相同才看第二关键字。 依此类推。

sort 的两个性质：

• 不稳定：值相同的元素，排完后相对顺序不保证。要稳定就用 stable_sort；
• 复杂度 O(n log n)：n = 1e6 大约零点几秒，够用。

推演：为什么这些写法是对的（以及它们能用来干什么）

排序看似「调个函数」，但比较器和「排序后能干什么」才是考点。下面推三点。

推演 1 · 为什么比较器 return a.x < b.x 决定升序

sort 用「小于」定义顺序：返回 true 表示 a 应排在 b 前面。所以 a.x < b.x 就是「小的在前」= 升序；写反就是降序。C++ sort 要求比较器满足严格弱序，绝不能写 ≤（会出现自己和自己比较返回 true，导致未定义行为）。

用法：升序用 <，降序用 >，多关键字别漏 return 的三种分支。

推演 2 · 多关键字为什么「先比主、再比次」

比较器里写 if(a.x != b.x) return a.x < b.x; return a.y < b.y; 恰好表达「主不同看主，主相同看次」。顺序写反语义就错（比如先比次再比主，会变成「次关键字优先」）。

用法：题目说「先按总分，总分同按语文」，严格按这个顺序写两级 if。

推演 3 · 为什么排序能当「预处理」

排完序后，很多原本 O(n²) 的事变简单：相邻元素比较、O(1) 取最大 / 最小 / 中位数、相邻相同值去重、lower_bound 二分查找。所以很多题「先排序」之后，主干逻辑只剩一遍 O(n) 扫描。

用法：看到「去重 / 第 k 大 / 相邻配对」，先 sort 再扫，往往迎刃而解。

知识用法地图（先记这张表，后面每节都会回到它）

技巧速查表（背下来）

原讲义配图

例题

题目描述

分数排名

有 $n$ 名学生，每个学生有学号 id 和成绩 score。现在需要按照成绩从高到低排序，如果成绩相同，则按学号从小到大排序。请输出排序后的学号和成绩。

输入格式：

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 id 和 score。

输出格式：

$n$ 行，每行一个学生的学号和成绩，格式为 id score。

审题分析

1. 读题抓条件：

- 输入：$n$ 个学生的学号和成绩。

- 输出：按成绩降序，成绩相同按学号升序。

- 注意：学号是整数，成绩也是整数。

2. 定需求：

- 需要存储每个学生的学号和成绩，所以用结构体。

- 需要排序，且排序规则是“先按成绩降序，再按学号升序”，所以需要自定义比较函数。

3. 为什么能用本知识点：

- 题目明确要求排序，且排序规则是多关键字的，这正是 sort 配合自定义比较器的典型应用场景。

- 如果不用自定义比较器，只能用默认的升序，或者用 greater 只能实现单关键字降序，无法满足题目要求。

4. 如果不用会怎样：

- 如果只按成绩排序，成绩相同的学生顺序是随机的，可能导致输出错误。

- 如果按学号排序，成绩高的学生会排在后面，完全不符合题目要求。

解题思路

1. 定义一个结构体 Student，包含 id 和 score 两个成员。

2. 定义一个比较函数 cmp，实现“成绩降序，成绩相同按学号升序”的逻辑。

3. 使用 sort 函数，传入学生数组的起始地址和结束地址，以及比较函数 cmp。

4. 遍历排序后的数组，输出每个学生的学号和成绩。

C++ 完整参考代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 定义学生结构体
struct Student {
 int id; // 学号
 int score; // 成绩
};

// 自定义比较函数
// 返回 true 表示 a 应该排在 b 前面
bool cmp(const Student& a, const Student& b) {
 if (a.score != b.score) {
 // 第一关键字：成绩降序
 return a.score > b.score;
 }
 // 第二关键字：成绩相同时，学号升序
 return a.id < b.id;
}

int main() {
 int n;
 cin >> n;
 
 // 读取 n 个学生的信息
 vector<Student> students(n);
 for (int i = 0; i < n; i++) {
 cin >> students[i].id >> students[i].score;
 }
 
 // 使用 sort 进行排序，传入自定义比较函数
 sort(students.begin(), students.end(), cmp);
 
 // 输出排序后的结果
 for (int i = 0; i < n; i++) {
 cout << students[i].id << " " << students[i].score << endl;
 }
 
 return 0;
}

代码解读

1. 头文件引入：

- <iostream>：用于 cin 和 cout。

- <algorithm>：包含 sort 函数。

- <vector>：使用动态数组存储学生信息。

2. 结构体定义：

- Student 结构体包含两个整型成员 id 和 score。

3. 比较函数 cmp：

- 参数是两个常引用 const Student& a 和 const Student& b，避免拷贝。

- 首先比较成绩：如果 a.score != b.score，则返回 a.score > b.score（降序）。

- 如果成绩相同，则比较学号：返回 a.id < b.id（升序）。

- 这个逻辑完美实现了题目要求的排序规则。

4. 主函数逻辑：

- 读取学生数量 n。

- 创建大小为 n 的 vector<Student>，并逐个读取学生的学号和成绩。

- 调用 sort(students.begin(), students.end(), cmp)，利用自定义比较函数进行排序。

- 遍历排序后的数组，输出每个学生的学号和成绩。

运行结果示例：

输入：

5
101 85
102 90
103 85
104 95
105 90

输出：

104 95
102 90
105 90
101 85
103 85

解释：

• 成绩最高的是 104 号（95 分），排第一。
• 成绩 90 分的有 102 号和 105 号，按学号从小到大排，102 在前。
• 成绩 85 分的有 101 号和 103 号，按学号从小到大排，101 在前。

例题复盘总结

分数线划定（NOIP 2009 普及组）：按成绩从高到低排序，成绩相同按报名号从小到大；然后划出面试分数线。

struct Node { int id, score; };
bool cmp(const Node& a, const Node& b) {
 if (a.score != b.score) return a.score > b.score; // 成绩降序
 return a.id < b.id; // 报名号升序
}
sort(v.begin(), v.end(), cmp);

int m = (int)v.size();
int line_idx = (int)(m * 0.6) - 1; // 前 60% 进入面试
int line = v[line_idx].score; // 分数线 = 第 line_idx 名的成绩
int cnt = 0;
for (auto& x : v) if (x.score >= line) cnt++; //  分数相同的人要一起算进来
printf("%d %d\n", line, cnt);

这道题的两个关键点：

① cmp 里 成绩相同时按报名号 —— 多关键字排序的标准写法；

② 划完线后分数等于分数线的人要全部算进来（不是只取 60% 个人）—— 这是题目最容易读漏的一句。

写法总表

分工说明：触发清单告诉你「什么时候想到排序」，速查表告诉你「排序后能做什么」，写法总表告诉你「具体怎么实现」。

常见错误

1. cmp 的返回值含义搞反。 cmp(a, b) 返回 true = "a 排在 b 前面"，不是 "a < b"。写反了结果是完全倒过来的。

2. cmp 不满足"严格弱序"→ 运行时崩溃（RE）。 最常见的错误写法：

```cpp

bool cmp(int a, int b) { return a >= b; } // 用了 >= 而不是 >

```

相等时返回 true 会让 sort 内部的比较逻辑自相矛盾，可能越界崩溃。 所有比较必须是 < 或 >，绝不能出现 <= 或 >=（除非你额外处理了相等的情况）。

3. sort 在比较器里改变了被比较的值（比如 cmp 里做了 swap）—— 也会崩溃。

4. 忘了 sort 是不稳定的，却依赖"相同元素的原始顺序"→ 结果随机不对。改用 stable_sort。

5. 结构体加了自己写的比较器后，忘了改用 cmp 版本。 比如写了 operator< 又传了 cmp，行为可能互相矛盾。

6. sort 的区间写成 sort(a, a + n - 1)。 第二个参数是开区间末尾，应该是 a + n。少一个元素不报错，只是答案错。

7. 排序后忘记"原来的下标"没了。 如果需要知道每个元素原来在哪，要在结构体里存下原下标。

自测

1. cmp(a, b) 返回 true 的含义是什么？和"a < b"有什么区别？

2. 写出"成绩降序、成绩相同按学号升序"的比较器。

3. 为什么 cmp 里不能写 >=？会有什么后果？

4. 什么时候必须用 stable_sort 而不能用 sort？

5. sort(a, a + n) 的第二个参数为什么是 a + n 而不是 a + n - 1？

6. 拿到一道题，判断"能不能排序"要看什么？

7. 排序关键字想不出来的时候，通常说明什么问题？

举一反三 · 审题流水线

拿到一道排序题，别急着敲代码，先让「审题流水线」跑一遍：

1. 看能不能排 —— 题目有没有要求保持原顺序？有没有要求输出原下标？如果有，直接对原数组排序就是死路，得考虑排下标数组或存原下标。

2. 定关键字 —— 一句"我要按 ___ 排"写出来。写不出说明还没想清楚；多关键字就按题目顺序写 if 链。

3. 想后果 —— 排完干什么？扫描？双指针？二分？取前 k 个？如果排完只是输出，那 sort 就是终点；如果排完还要处理，那排序只是预处理。

4. 查稳定 —— 题目说"相同按输入顺序"吗？是的话必须 stable_sort 或在 cmp 里加原下标兜底。

5. 验严格 —— cmp 里有没有 <= / >=？有没有在比较器里改值？有没有漏掉 return 分支？这些是 RE 的高发区。

练手题

练手题 1：按绝对值排序

给定 $n$ 个整数，按绝对值从小到大排序，如果绝对值相同，按原数值从小到大排序。

输入：

5
-3 4 -2 5 -1

输出：

-2 -1 3 4 5

练手题 2：字符串排序

给定 $n$ 个字符串，按字符串长度从小到大排序，如果长度相同，按字典序从小到大排序。

输入：

4
apple banana cat dog

输出：

cat dog apple banana