Appearance
第7章 排序算法
🎯 本章学习目标
通过本章的学习，你将能够：
- 理解排序概念：知道排序的含义，区分内部排序和外部排序
- 掌握稳定性定义：理解排序稳定性的含义，能判断算法是否稳定
- 手写冒泡排序：熟练编写冒泡排序代码，理解其优化方式
- 手写选择排序：熟练编写选择排序代码，理解为什么不稳定
- 手写插入排序：熟练编写插入排序代码，理解向前插入的过程
- 分析时间复杂度：能推导三种排序的最好、最坏、平均时间复杂度
- 理解空间复杂度：知道三种排序都是 O(1) 原地排序
- 掌握大O表示法：能分析代码片段的时间复杂度
- 根据数据规模选算法：根据 n 的范围判断哪种复杂度的算法能通过
- 使用STL sort：会用 sort 函数排序，知道其稳定性
🗺️ 本章知识图谱
排序算法
├── 基础概念
│ ├── 排序的定义（升序/降序）
│ ├── 内部排序 vs 外部排序
│ └── 稳定性（相等元素相对顺序）
├── 三大基础排序
│ ├── 冒泡排序
│ │ ├── 相邻比较交换
│ │ ├── 每轮确定一个最大值
│ │ ├── 标志位优化
│ │ └── 稳定，O(n²)
│ ├── 选择排序
│ │ ├── 每轮选最小值
│ │ ├── 交换到已排序末尾
│ │ ├── 不稳定
│ │ └── 始终 O(n²)
│ └── 插入排序
│ ├── 从后向前插入
│ ├── 元素后移
│ ├── 稳定
│ └── 最好O(n)，最坏O(n²)
├── 复杂度分析
│ ├── 大O表示法
│ ├── 时间复杂度（最好/最坏/平均）
│ ├── 空间复杂度
│ ├── 常见复杂度排序
│ └── 数据规模反推
├── STL排序
│ ├── sort 函数
│ ├── stable_sort
│ ├── 自定义比较函数
│ └── sort 不稳定
└── 应用场景
├── 排行榜
├── 查找预处理
├── 去重
└── 数据展示一、排序的基本概念
1.1 什么是排序
排序（Sorting）是将一组数据按照特定顺序（升序或降序）重新排列的过程。
- 升序（从小到大） ：如
[5, 2, 8, 1]→[1, 2, 5, 8] - 降序（从大到小） ：如
[5, 2, 8, 1]→[8, 5, 2, 1]
排序后的数据满足：对任意 i < j，有 a[i] ≤ a[j]（升序）或 a[i] ≥ a[j]（降序）。
⚠️ 易错点： 排序不改变数据本身，只改变数据的排列顺序。排序前后元素集合完全相同，一个不多一个不少。
1.2 排序的应用场景
| 应用场景 | 说明 | 示例 |
|---|---|---|
| 查找预处理 | 排序后可使用二分查找，效率从 O(n) 提升到 O(log n) | 电话簿按姓氏排序便于查找 |
| 排行榜 | 按分数、销量等指标排名 | 游戏积分榜、考试成绩排名 |
| 数据展示 | 用户更习惯查看有序数据 | 商品按价格从低到高展示 |
| 去重 | 排序后相同元素相邻，去重只需扫描一遍 | 统计不重复数字的个数 |
1.3 内部排序 vs 外部排序
| 分类 | 定义 | 特点 | 举例 |
|---|---|---|---|
| 内部排序 | 数据全部存放在内存中进行排序 | 速度快，适合数据量不大 | 冒泡、插入、选择、快排 |
| 外部排序 | 数据量大，无法全部放入内存，需借助外存（硬盘） | 速度慢，涉及磁盘读写 | 归并排序用于大文件排序 |
📌 GESP四级聚焦： 四级考纲只要求掌握比较类内部排序——即冒泡排序、插入排序、选择排序。非比较排序和外部排序在更高级别才会涉及。
二、算法稳定性
2.1 稳定性的定义
排序稳定性： 如果排序后，序列中值相等的元素保持了它们在排序前的相对先后顺序，则称该排序算法是稳定的；否则是不稳定的。
用数学语言描述：对于任意两个值相等的元素 a[i] 和 a[j]（i < j），排序后若 a[i] 仍在 a[j] 前面，则该排序是稳定的。
2.2 举例说明
假设有一组扑克牌，按花色+点数区分每张牌，但我们只按点数排序：
| 排序前（输入） | 排序后（稳定） | 排序后（不稳定） | |||
|---|---|---|---|---|---|
| 牌 | 点数 | 牌 | 点数 | 牌 | 点数 |
| ♠5 | 5 | ♥3 | 3 | ♥3 | 3 |
| ♥3 | 3 | ♠5 | 5 | ♣5 | 5 |
| ♣5 | 5 | ♣5 | 5 | ♠5 | 5 |
| ♥7 | 7 | ♥7 | 7 | ♥7 | 7 |
- 稳定排序：两张 5 点牌中，♠5 原本在 ♣5 前面，排序后 ♠5 仍在 ♣5 前面 ✅
- 不稳定排序：两张 5 点牌的先后顺序可能被颠倒 ❌
2.3 稳定性为什么重要？
稳定性在多关键字排序时尤为重要。
场景：
学生成绩表，先按班级排序，再按成绩排序。
排序前： 先按班级排序后： 再按成绩排序（稳定）：
张三 1班 90 张三 1班 90 李四 1班 95
李四 1班 95 李四 1班 95 张三 1班 90
王五 2班 85 赵六 1班 80 赵六 1班 80
赵六 1班 80 王五 2班 85 王五 2班 85如果第二次排序（按成绩）是稳定的，那么成绩相同的学生会保持按班级排好的顺序。稳定排序可以逐关键字叠加排序效果。
🔥 高频考点： GESP判断题常考稳定性的定义。记住：稳定性只关注相等元素的相对顺序，和排序是否正确、数据是否丢失没有任何关系！
2.4 三种排序的稳定性归类
| 稳定性 | 排序算法 | 说明 |
|---|---|---|
| 稳定 ✅ | 冒泡排序 | 相邻比较，相等元素不交换 |
| 稳定 ✅ | 插入排序 | 从后向前插入，相等元素不后移 |
| 不稳定 ❌ | 选择排序 | 跨位置交换可能打乱相等元素顺序 |
下面讲解每种算法时，会从代码层面详细分析为什么稳定或不稳定。
三、冒泡排序（Bubble Sort）
3.1 核心原理
冒泡排序的思想非常直观：重复遍历数组，比较相邻两个元素，如果顺序错误就交换它们。每一轮遍历结束后，当前未排序部分的最大元素会像气泡一样"浮"到末尾。
具体过程：
- 从数组开头开始，依次比较相邻元素
a[j]和a[j+1] - 如果
a[j] > a[j+1]（升序），则交换它们 - 一轮结束后，最大元素被放到数组末尾
- 对剩余未排序部分重复以上过程，直到没有任何交换发生
3.2 图示过程
以数组 [5, 3, 8, 1, 2] 升序排序为例：
初始: [5, 3, 8, 1, 2]
第1轮（比较4次，最大8冒到末尾）:
5>3 交换 → [3, 5, 8, 1, 2]
5<8 不换 → [3, 5, 8, 1, 2]
8>1 交换 → [3, 5, 1, 8, 2]
8>2 交换 → [3, 5, 1, 2, 8] ← 8已就位
第2轮（比较3次，次大5冒到倒数第二）:
3<5 不换 → [3, 5, 1, 2, 8]
5>1 交换 → [3, 1, 5, 2, 8]
5>2 交换 → [3, 1, 2, 5, 8] ← 5已就位
第3轮（比较2次）:
3>1 交换 → [1, 3, 2, 5, 8]
3>2 交换 → [1, 2, 3, 5, 8] ← 3已就位
第4轮（比较1次）:
1<2 不换 → [1, 2, 3, 5, 8] ← 无交换，排序完成记忆口诀： 相邻比较，大的后移；每轮少比一个，n-1轮搞定。
3.3 完整代码（含 flag 优化）
cpp
#include <iostream>
using namespace std;
// 冒泡排序（升序），含flag优化
void bubbleSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false; // 标记本轮是否发生交换
// 每轮比较到 n-1-i，因为末尾i个元素已有序
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swapped = true;
}
}
if (!swapped) break; // 本轮无交换，已有序，提前结束
}
}
int main() {
int a[] = {5, 3, 8, 1, 2};
int n = 5;
bubbleSort(a, n);
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
// 输出: 1 2 3 5 8
return 0;
}⚠️ 易错点： 内层循环边界是
j < n - 1 - i，不是j < n - 1。因为每轮结束后末尾已有i个元素排好序，不需要再比较。写成j < n - 1虽然结果正确，但会做多余比较。
3.4 复杂度与稳定性分析
| 指标 | 值 | 说明 |
|---|---|---|
| 最好时间复杂度 | O(n) | 数组已有序 + flag优化，一轮即可结束 |
| 最坏时间复杂度 | O(n²) | 数组完全逆序，需 n-1 轮，比较 n(n-1)/2 次 |
| 平均时间复杂度 | O(n²) | 随机数据 |
| 空间复杂度 | O(1) | 仅用了几个辅助变量，原地排序 |
| 稳定性 | 稳定 ✅ | 相等元素不交换（a[j] > a[j+1] 才交换） |
🔥 高频考点： 冒泡排序的稳定性取决于比较条件。使用
>（严格大于）时，相等元素不会交换，排序稳定；如果写成>=，相等元素也会交换，就变成不稳定排序了。
四、选择排序（Selection Sort）
4.1 核心原理
选择排序的思想：每一轮从未排序部分中找到最小（升序）元素，将其与未排序部分的第一个元素交换，放到已排序部分的末尾。
具体过程：
- 在未排序区间
[i, n-1]中找到最小值的下标minIdx - 将
a[i]与a[minIdx]交换 - 已排序区间扩展为
[0, i] - 重复以上过程 n-1 轮
4.2 图示过程
以数组 [5, 3, 8, 1, 2] 升序排序为例：
初始: [5, 3, 8, 1, 2]
第1轮（在[0,4]找最小）:
最小值1在位置3，交换a[0]和a[3]
→ [1, 3, 8, 5, 2] ← 1已就位
第2轮（在[1,4]找最小）:
最小值2在位置4，交换a[1]和a[4]
→ [1, 2, 8, 5, 3] ← 2已就位
第3轮（在[2,4]找最小）:
最小值3在位置4，交换a[2]和a[4]
→ [1, 2, 3, 5, 8] ← 3已就位
第4轮（在[3,4]找最小）:
最小值5在位置3，无需交换
→ [1, 2, 3, 5, 8] ← 排序完成对比记忆： 冒泡排序是"边比边换"，选择排序是"先找后换"——每轮只在最后做一次交换。
4.3 完整代码
cpp
#include <iostream>
using namespace std;
// 选择排序（升序）
void selectionSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i; // 假设未排序部分第一个元素最小
// 在未排序区间 [i+1, n-1] 中找最小值下标
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIdx]) {
minIdx = j; // 更新最小值下标
}
}
// 将最小值交换到未排序部分的起始位置
if (minIdx != i) {
swap(a[i], a[minIdx]);
}
}
}
int main() {
int a[] = {5, 3, 8, 1, 2};
int n = 5;
selectionSort(a, n);
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
// 输出: 1 2 3 5 8
return 0;
}⚠️ 易错点：
minIdx的初始值必须是i（未排序部分的起始位置），不是0！每轮开始时，假设a[i]是最小的，然后从i+1开始比较更新。
4.4 复杂度与稳定性分析
| 指标 | 值 | 说明 |
|---|---|---|
| 最好时间复杂度 | O(n²) | 即使已有序，仍需逐轮比较找最小值 |
| 最坏时间复杂度 | O(n²) | 始终比较 n(n-1)/2 次 |
| 平均时间复杂度 | O(n²) | 与数据分布无关 |
| 空间复杂度 | O(1) | 原地排序 |
| 稳定性 | 不稳定 ❌ | 跨位置交换可能改变相等元素的相对顺序 |
🔥 高频考点： 选择排序的时间复杂度始终是 O(n²)，无论数据是否有序，因为它每轮都必须遍历未排序部分来找最小值，无法像冒泡那样用 flag 提前终止。
4.5 为什么选择排序不稳定？
举一个反例。数组 [5(a), 5(b), 2]，其中 5(a) 和 5(b) 值相等：
第1轮：在[0,2]找最小值2（位置2），交换a[0]和a[2]
→ [2, 5(b), 5(a)]
排序后 5(b) 在 5(a) 前面，原来 5(a) 在 5(b) 前面，
相对顺序发生了改变，所以选择排序不稳定！根本原因： 选择排序的交换是"跨越式"的，最小值可能隔着多个元素与前面交换，这一跃迁就可能越过相等元素，打乱它们的相对顺序。
五、插入排序（Insertion Sort）
5.1 核心原理
插入排序的思想类似整理手中的扑克牌：将数组分为"已排序"和"未排序"两部分，每次取出未排序部分的第一个元素，在已排序部分中从后向前中找到合适位置插入。
具体过程：
- 将
a[0]视为已排序部分（只有一个元素） - 取出未排序部分的第一个元素
a[i]（即key） - 从已排序部分末尾
a[i-1]开始向前比较 - 如果
a[j] > key，将a[j]后移一位 - 重复直到找到
a[j] <= key或到达数组开头 - 将
key插入到j+1的位置
5.2 图示过程
以数组 [5, 3, 8, 1, 2] 升序排序为例：
初始: [5 | 3, 8, 1, 2] （|左边已排序，右边未排序）
第1轮：取key=3，与5比较，5>3后移
[_, 5, 8, 1, 2] → 3插入位置0
→ [3, 5 | 8, 1, 2]
第2轮：取key=8，与5比较，5<8，不移动
→ [3, 5, 8 | 1, 2]
第3轮：取key=1，与8比较，8>1后移
[3, 5, _, 8, 2] → 与5比较，5>1后移
[3, _, 5, 8, 2] → 与3比较，3>1后移
[_, 3, 5, 8, 2] → 到达开头，1插入位置0
→ [1, 3, 5, 8 | 2]
第4轮：取key=2，与8比较，8>2后移
[1, 3, 5, _, 8] → 与5比较，5>2后移
[1, 3, _, 5, 8] → 与3比较，3>2后移
[1, _, 3, 5, 8] → 与1比较，1<2，停止，2插入位置1
→ [1, 2, 3, 5, 8] ← 排序完成5.3 完整代码
cpp
#include <iostream>
using namespace std;
// 插入排序（升序）
void insertionSort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i]; // 取出未排序部分的第一个元素
int j = i - 1; // 已排序部分的末尾下标
// 从后向前扫描已排序部分，将大于key的元素后移
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j]; // 元素后移
j--;
}
a[j + 1] = key; // 插入key到正确位置
}
}
int main() {
int a[] = {5, 3, 8, 1, 2};
int n = 5;
insertionSort(a, n);
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
// 输出: 1 2 3 5 8
return 0;
}⚠️ 易错点： 后移操作是
a[j+1] = a[j]，方向是从后往前逐个覆盖。注意最后插入位置是j+1，因为 while 循环结束时j已经多减了一次（或者到达了 -1）。
🔥 高频考点： while 循环条件
j >= 0 && a[j] > key的顺序不能写反！必须先判断j >= 0，否则当j = -1时访问a[-1]会越界。这是 C++ 逻辑与&&的"短路求值"特性。
5.4 复杂度与稳定性分析
| 指标 | 值 | 说明 |
|---|---|---|
| 最好时间复杂度 | O(n) | 数组已有序，每轮只需比较1次，不移动 |
| 最坏时间复杂度 | O(n²) | 数组完全逆序，每轮需比较并移动 i 次 |
| 平均时间复杂度 | O(n²) | 随机数据 |
| 空间复杂度 | O(1) | 仅用 key 和 j 等辅助变量 |
| 稳定性 | 稳定 ✅ | 从后向前比较，a[j] > key（严格大于）才后移 |
对比冒泡： 插入排序和冒泡排序最好情况都是 O(n)，但插入排序在实际应用中通常比冒泡排序更快，因为它的移动操作更高效（冒泡需要三次赋值的交换，插入只需一次赋值的后移）。
六、三种排序对比总结
| 对比项 | 冒泡排序 | 选择排序 | 插入排序 |
|---|---|---|---|
| 核心思想 | 相邻比较，大的后移 | 找最小值，交换到前面 | 取出元素，插入正确位置 |
| 最好时间 | O(n) | O(n²) | O(n) |
| 最坏时间 | O(n²) | O(n²) | O(n²) |
| 平均时间 | O(n²) | O(n²) | O(n²) |
| 空间复杂度 | O(1) | O(1) | O(1) |
| 稳定性 | ✅ 稳定 | ❌ 不稳定 | ✅ 稳定 |
| 交换次数 | 较多（每次逆序都交换） | 较少（每轮最多1次） | 无交换（后移覆盖） |
| 适用场景 | 教学演示、小数据量 | 交换代价高的场景 | 小数据量、基本有序的数据 |
⚡ 考试速记：
- 最好 O(n) 的：冒泡（带 flag）、插入
- 始终 O(n²) 的：选择
- 稳定的：冒泡、插入
- 不稳定的：选择
七、C++ 标准库 sort 函数
📚 拓展 · 超纲：四级考纲「排序算法」只要求手写冒泡、插入、选择三种排序，并未把
sort/stable_sort等 STL 函数列入考点（STL 容器与算法属更高级别）。本节作为"拓展"介绍——实际竞赛与工程中常用，但在四级考试中手写三种排序才是得分点，请务必分清主次。
GESP四级允许直接使用 C++ 标准库的 sort 函数，实际编程中最常用。
7.1 基本用法
cpp
#include <iostream>
#include <algorithm> // sort 函数所在头文件
using namespace std;
int main() {
int a[6] = {5, 2, 8, 1, 9, 3};
int n = 6;
// sort(起始地址, 结束地址的下一位)
// 默认升序排列
sort(a, a + n);
cout << "升序: ";
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
// 输出: 升序: 1 2 3 5 8 9
// 降序排列：使用 greater<int>()
sort(a, a + n, greater<int>());
cout << "降序: ";
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
// 输出: 降序: 9 8 5 3 2 1
return 0;
}⚠️ 易错点：
sort的第二个参数是结束地址的下一位，不是最后一个元素的地址。对长度为 n 的数组，正确写法是sort(a, a + n)，不是sort(a, a + n - 1)。
7.2 sort 与 stable_sort
| 函数 | 底层实现 | 稳定性 | 速度 |
|---|---|---|---|
sort | 快速排序（优化版） | 不稳定 ❌ | 快 |
stable_sort | 归并排序 | 稳定 ✅ | 略慢 |
🔥 高频考点：
sort是不稳定的！如果题目要求排序后相等元素保持原顺序，必须使用stable_sort。
八、算法复杂度估算
前面分析三种排序时，我们反复提到 O(n)、O(n²) 这些符号。它们到底是什么意思？怎么算出来的？这一节系统讲解。
8.1 为什么要分析复杂度？
同一个问题，往往有多种解法。比如对 10000 个数排序：
- 冒泡排序大约需要比较 1 亿次
- 快速排序大约需要比较 14 万次
差距高达 700 多倍 ！复杂度分析帮我们：
- 衡量算法效率 ——不实际运行代码，也能比较算法快慢
- 预测运行时间 ——根据数据规模 n，估算程序会不会超时
- 选择更优算法 ——在多种方案中做出合理选择
核心思想： 我们不关心具体跑了几毫秒，而是关心当输入规模 n 增大时，运行时间增长的趋势——这叫"渐近分析"。
8.2 大O表示法
大O表示法（Big-O Notation）用于描述算法运行时间随输入规模 n 增长的变化趋势。
例如，某算法的精确操作次数为 3n² + 5n + 2，我们记为 O(n²) 。
两条简化规则：
| 规则 | 说明 | 示例 |
|---|---|---|
| 忽略常数系数 | 常数不影响增长趋势 | O(3n) → O(n)，O(2n²) → O(n²) |
| 忽略低阶项 | n 很大时，高阶项主导增长 | O(n² + n) → O(n²) |
3n² + 5n + 2
│ │
│ └─ 低阶项和常数，去掉
└─ 最高阶项，保留系数变1
结果：O(n²)⚠️ 易错点： 写 O(2n)、O(3n²) 在考试中算错误！大O表示法必须忽略常数系数。
8.3 常见复杂度直观理解
| 复杂度 | 名称 | n=10 | n=100 | n=1000 | 增长速度 |
|---|---|---|---|---|---|
| O(1) | 常数 | 1 | 1 | 1 | 不增长 |
| O(log n) | 对数 | ~3 | ~7 | ~10 | 极慢 |
| O(n) | 线性 | 10 | 100 | 1000 | 慢 |
| O(n log n) | 线性对数 | ~33 | ~664 | ~9966 | 中等 |
| O(n²) | 平方 | 100 | 10000 | 1000000 | 快 |
| O(n³) | 立方 | 1000 | 1000000 | 10⁹ | 很快 |
| O(2ⁿ) | 指数 | 1024 | ~10³⁰ | ~10³⁰¹ | 爆炸 |
记忆口诀：常数 < 对数 < 线性 < 线性对数 < 平方 < 立方 < 指数
🔥 高频考点： 这个排序必须倒背如流！考试常考"以下复杂度从小到大排列正确的是"。
O(1)：常数复杂度
执行时间与输入规模 n 完全无关 。
cpp
// 无论 n 多大，以下操作都只执行固定次数
int a = 10, b = 20;
int c = a + b; // 算术运算 O(1)
cout << arr[500] << endl; // 数组随机访问也是 O(1)O(log n)：对数复杂度
每次操作将问题规模减半，效率极高。
cpp
// 二分查找 —— O(log n)
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// n=1000 时只需约 10 次比较！O(n)：线性复杂度
操作次数与 n 成正比 。
cpp
// 遍历数组求最大值 —— O(n)
int maxVal = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > maxVal) maxVal = arr[i];
}O(n²)：平方复杂度
操作次数与 n² 成正比 ，三种基础排序都是 O(n²)。
cpp
// 两层嵌套循环 —— O(n²)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << i + j << " ";
}
}8.4 多项式复杂度 vs 指数复杂度
多项式复杂度
形如 O(nᵏ)（k 为常数），如 O(n)、O(n²)、O(n³)。n 增大时，增长速度相对可控。
指数复杂度
形如 O(2ⁿ)、O(n!)，增长速度极其惊人：
| n | 2ⁿ | 大约值 |
|---|---|---|
| 10 | 1024 | ~1千 |
| 20 | 1,048,576 | ~1百万 |
| 30 | 1,073,741,824 | ~10亿 |
| 40 | ~1万亿 | 计算机需要数秒到数分钟 |
| 50 | ~1千万亿 | 计算机需要数千年 |
关键结论： 指数复杂度的算法，n 每增加 1，运行时间就翻倍。n=30 时 2³⁰ ≈ 10 亿次操作已接近极限；n=40 以上基本无法运行。
cpp
#include <iostream>
using namespace std;
// 朴素斐波那契递归 —— O(2ⁿ)
long long fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
cout << fib(10) << endl; // 55，瞬间出结果
cout << fib(30) << endl; // 832040，约0.1秒
// fib(40) ≈ 1亿次调用，需要好几秒！
// fib(50) 就需要数千年了！
return 0;
}📌 GESP四级要求： 不需要你写出指数算法的优化方案，但必须能识别出哪些代码是指数复杂度，并知道它在数据规模稍大时会超时。
8.5 空间复杂度
空间复杂度衡量算法运行过程中额外占用的内存空间中随 n 增长的趋势。
| 空间复杂度 | 含义 | 典型示例 |
|---|---|---|
| O(1) | 只用几个辅助变量 | 冒泡排序、选择排序、插入排序 |
| O(n) | 使用了与 n 等大的额外空间 | 归并排序（需要辅助数组） |
| O(n²) | 使用了二维数组 | 动态规划表格 |
cpp
// 空间复杂度 O(1)：只用了几个变量
int sum(int arr[], int n) {
int s = 0;
for (int i = 0; i < n; i++) s += arr[i];
return s;
}⚠️ 易错点： 时间和空间复杂度是两个不同维度，不要混淆。一个算法可以时间 O(n²)、空间 O(1)（如冒泡排序）。递归函数还要考虑递归调用栈的空间。
九、复杂度分析实战
9.1 三种排序的复杂度推导
冒泡排序复杂度推导
外层循环 i 从 0 到 n-2，共 n-1 轮
内层循环第 i 轮比较 n-1-i 次
总比较次数 = (n-1) + (n-2) + ... + 1
= n(n-1)/2
≈ n²/2
→ O(n²)（最坏/平均）最好情况：
数组已有序，第1轮无交换（flag优化），直接退出，只需 n-1 次比较 → O(n) 。
选择排序复杂度推导
外层循环 i 从 0 到 n-2，共 n-1 轮
内层循环第 i 轮比较 n-1-i 次（无论数据如何）
总比较次数 = (n-1) + (n-2) + ... + 1
= n(n-1)/2
→ O(n²)（最好/最坏/平均，始终如此）选择排序无法提前终止——即使数组已有序，仍需逐轮扫描找最小值，因此三种情况都是 O(n²)。
插入排序复杂度推导
外层循环 i 从 1 到 n-1，共 n-1 轮
第 i 轮最多比较 i 次、移动 i 次
最坏情况（完全逆序）：
总次数 = 1 + 2 + 3 + ... + (n-1)
= n(n-1)/2
→ O(n²)
最好情况（已有序）：
每轮只比较1次，不移动
总次数 = n-1 → O(n)9.2 代码片段复杂度判断
例1：两层嵌套
cpp
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << i * j << " ";
}
}答：O(n²)
。两层嵌套，每层 n 次。
例2：内层循环次数与外层相关
cpp
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
cout << i + j << " ";
}
}答：O(n²)
。总次数 = 0+1+2+...+(n-1) = n(n-1)/2 ≈ n²/2。
例3：对数级循环
cpp
for (int i = 1; i < n; i *= 2) {
cout << i << " ";
}答：O(log n)
。i 每次翻倍（1, 2, 4, 8, ...），执行 log₂n 次。
例4：线性 × 对数
cpp
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j *= 2) {
cout << i + j << " ";
}
}答：O(n log n)
。外层 n 次，内层 log₂n 次，相乘得 n log n。
技巧： 串联循环是相加取高阶（O(n)+O(n)=O(n)），嵌套循环是相乘（O(n)×O(n)=O(n²)）。
9.3 根据数据规模反推复杂度
每秒大约能执行 10⁸ （1亿）次简单操作：
| 数据规模 n | 可接受的复杂度 | 说明 |
|---|---|---|
| n ≤ 20 | O(2ⁿ) | 刚好 100 万左右 |
| n ≤ 500 | O(n³) | 1.25×10⁸ |
| n ≤ 5000 | O(n²) | 2.5×10⁷ |
| n ≤ 10⁶ | O(n log n) | ~2×10⁷ |
| n ≤ 10⁷ | O(n) | 10⁷ |
🔥 高频考点： 考试常给 n 的范围问"哪个算法能通过"。记住：n ≤ 1000 → O(n²) 没问题；n ≤ 100000 → 必须 O(n log n) 或更快。
十、常见易错点汇总
| 易错点 | 错误理解 | 正确理解 |
|---|---|---|
| 稳定性 = 数据不丢失 | "排序后数据不丢失就是稳定" | 稳定性专指相等元素的相对顺序不变 |
| 所有排序都稳定 | "排序算法都是稳定的" | 选择排序就是不稳定的 |
| 冒泡内层边界 | j < n - 1 | 应为 j < n - 1 - i |
| 选择排序最小值索引 | minIdx = 0 | 应为 minIdx = i（每轮重置） |
| 插入排序后移方向 | 从前向后移 | 必须从后向前移，否则覆盖未读数据 |
sort 参数 | sort(a, a+n-1) | 应为 sort(a, a+n)（尾后地址） |
sort 稳定性 | "sort是稳定的" | sort 不稳定，需稳定用 stable_sort |
| 大O保留系数 | O(2n)、O(3n²) | 必须简化为 O(n)、O(n²) |
| 递归复杂度 | 看到递归就以为 O(n) | 朴素斐波那契递归是 O(2ⁿ) |
| 选择排序最好情况 | "已有序时选择排序是O(n)" | 选择排序始终 O(n²)，无法提前终止 |
十一、📝 实战练习
练习题 1（单选题）
题目： 对序列 (5, 3, 5, 2) 进行升序排序，排序结果为 (2, 3, 5, 5)。已知排序前第一个5记为5a，第三个5记为5b，排序后5a在5b前面。关于该排序算法的稳定性，以下说法正确的是（ ） A. 该排序算法一定是稳定的
B. 该排序算法一定是不稳定的
C. 仅凭这一次排序结果，无法确定该算法是否稳定
D. 该排序算法有时稳定有时不稳定
🔑 点击查看答案与解析
答案： C
解析： 稳定性是排序算法的固有属性，需要从算法原理上证明，不能仅凭一次排序结果判断。即使这次5a在5b前面，换一组数据可能顺序就颠倒了。只有从算法逻辑上保证"相等元素永远不交换"，才能称为稳定排序。
练习题 2（单选题）
题目： 对数组 [6, 3, 8, 3, 1] 进行选择排序（升序），第2轮结束后，（i=1执行完后）数组是什么？（ ） A. [1, 3, 8, 3, 6]
B. [1, 3, 3, 6, 8]
C. [1, 3, 8, 6, 3]
D. [1, 3, 3, 8, 6]
🔑 点击查看答案与解析
答案： A
解析：
初始: [6, 3, 8, 3, 1]
第1轮(i=0): 在[0,4]找最小值1在位置4，交换a[0]和a[4]
→ [1, 3, 8, 3, 6]
第2轮(i=1): 在[1,4]找最小值3（a[1]=3，无需交换）
→ [1, 3, 8, 3, 6]选 A。同时注意：两个值为3的元素最终相对顺序可能改变，说明选择排序不稳定。
练习题 3（单选题）
题目： 以下代码的时间复杂度是（ ）
cpp
for (int i = 1; i < n; i *= 2) {
for (int j = 0; j < n; j++) {
cout << i + j << " ";
}
}A. O(n)
B. O(n²)
C. O(n log n)
D. O(log n)
🔑 点击查看答案与解析
答案： C
解析： 外层循环 i 每次翻倍（1, 2, 4, 8, ...），执行 log₂n 次；内层循环每次执行 n 次。总操作次数 = n × log₂n，因此复杂度为 O(n log n) 。
练习题 4（单选题）
题目： 某题数据范围为 n ≤ 100000，以下哪个复杂度的算法最有可能在 1 秒内通过？（ ） A. O(n²)
B. O(n³)
C. O(n log n)
D. O(2ⁿ)
🔑 点击查看答案与解析
答案： C
解析：
- O(n²) = (10⁵)² = 10¹⁰ = 100 亿次，超时 ❌
- O(n³) = 10¹⁵ 次，严重超时 ❌
- O(n log n) = 10⁵ × 17 ≈ 170 万次，轻松通过 ✅
- O(2ⁿ) 完全不可行 ❌
选 C。
练习题 5（单选题）
题目： 以下关于排序的说法，正确的有（ ）
① 冒泡排序和插入排序都是稳定排序 ② 选择排序的最好、最坏、平均时间复杂度都是 O(n²) ③ sort 函数默认升序，且是稳定排序 ④ 插入排序在数组已有序时，时间复杂度为 O(n) ⑤ 对规模 n≤1000 的数据，O(n²) 的排序算法通常可以在1秒内完成 A. ①②④
B. ①②④⑤
C. ①②③④
D. ①②③④⑤
🔑 点击查看答案与解析
答案： B
解析：
- ① 正确 ✅：冒泡（
>比较不交换相等元素）和插入（>比较不后移相等元素）都是稳定的。 - ② 正确 ✅：选择排序每轮必须遍历找最小值，三种情况均为 O(n²)。
- ③ 错误 ❌：
sort默认升序没错，但底层是快速排序，不稳定，需要稳定应用stable_sort。 - ④ 正确 ✅：已有序时每轮只比较1次不移动，共 n-1 次比较 → O(n)。
- ⑤ 正确 ✅：n=1000 时 n² = 100万 < 1亿，通常可以在1秒内完成。
选 B（①②④⑤）。
练习题 6（单选题）
题目： 对数组 [8, 3, 6, 2, 5] 进行升序插入排序，第 3 轮（i=3 处理完后）数组的状态是？（ ） A. [2, 3, 6, 8, 5]
B. [2, 3, 5, 6, 8]
C. [3, 6, 8, 2, 5]
D. [2, 3, 8, 6, 5]
🔑 点击查看答案与解析
答案： A
解析：
插入排序第 i 轮处理第 i 个元素（i 从 1 开始），将其插入到前面已排序序列的正确位置。
初始：[8, 3, 6, 2, 5]
- 第 1 轮（i=1，处理 3）：3 插入到 8 前面 →
[3, 8, 6, 2, 5] - 第 2 轮（i=2，处理 6）：6 插入到 3 和 8 之间 →
[3, 6, 8, 2, 5] - 第 3 轮（i=3，处理 2）：2 插入到最前面 →
[2, 3, 6, 8, 5]
选 A。
💡 插入排序的特点：前 i 个元素始终是有序的。每轮把一个新元素"插入"到正确的位置，就像打扑克牌时整理手牌。
练习题 7（判断题）
题目： 如果一个排序算法是稳定的，那么排序后数据不会丢失。（ ）
🔑 点击查看答案与解析
答案： 错误 ❌
解析： 稳定性的定义是：相等元素的相对顺序在排序后保持不变，和"数据是否丢失"没有关系。任何正确的排序算法都不会丢失数据（元素个数不变），但稳定和不稳定的区别在于相等元素的先后顺序是否保持。
🍎 生活比喻：就像排队——按身高排队，如果两个人一样高，稳定排序会让原来站前面的人还站前面；不稳定排序可能让他们交换位置。但人一个都不会少。
练习题 8（编程题）
题目： 输入 n 个学生的姓名和成绩，按成绩从高到低排序输出。成绩相同的按姓名字典序从小到大排序。
输入：第一行 n，接下来 n 行每行姓名和成绩
输出：排序后的 n 行，每行姓名和成绩
🔑 点击查看答案与解析
参考答案：
cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
struct Student {
string name;
int score;
};
// 比较函数：成绩降序，成绩相同则姓名升序
bool cmp(const Student& a, const Student& b) {
if (a.score != b.score)
return a.score > b.score; // 成绩高的在前
return a.name < b.name; // 姓名字典序小的在前
}
int main() {
int n;
cin >> n;
Student stu[105];
for (int i = 0; i < n; i++) {
cin >> stu[i].name >> stu[i].score;
}
sort(stu, stu + n, cmp);
for (int i = 0; i < n; i++) {
cout << stu[i].name << " " << stu[i].score << endl;
}
return 0;
}解析：
这是排序的经典题型——结构体多关键字排序。核心是自定义比较函数 cmp：
- 先比较成绩，成绩高的排前面（降序）
- 成绩相同时，比较姓名，字典序小的排前面（升序）
sort 函数的第三个参数是比较函数，返回 true 表示第一个参数应该排在第二个参数前面。
💡 记忆技巧：cmp(a, b) 返回 true → a 排在 b 前面。想要降序就
a > b，想要升序就a < b。
十二、📊 考点总结表
| 考点 | 重要程度 | 出题形式 | 易错点 |
|---|---|---|---|
| 排序定义与内/外排序 | ⭐⭐ | 选择/判断 | 混淆内部排序和外部排序的适用场景 |
| 稳定性的概念 | ⭐⭐⭐⭐⭐ | 判断/选择（高频） | 把稳定性和数据是否丢失混淆 |
| 冒泡排序原理与代码 | ⭐⭐⭐⭐⭐ | 代码填空/程序阅读 | 内层循环边界 j < n-1-i |
| 选择排序原理与代码 | ⭐⭐⭐⭐⭐ | 代码填空/程序阅读 | minIdx 每轮要重置为 i |
| 插入排序原理与代码 | ⭐⭐⭐⭐⭐ | 代码填空/程序阅读 | 从后向前插入，元素后移方向 |
| 三种排序稳定性 | ⭐⭐⭐⭐⭐ | 选择/判断题 | 选择排序不稳定，冒泡和插入稳定 |
| 三种排序复杂度对比 | ⭐⭐⭐⭐⭐ | 选择/判断题 | 选择排序最好也是O(n²)，冒泡插入最好O(n) |
| 大O表示法与简化 | ⭐⭐⭐⭐ | 选择/判断 | 要去掉系数和低阶项 |
| 循环代码复杂度分析 | ⭐⭐⭐⭐⭐ | 选择/程序阅读 | 嵌套乘，串联取最高阶 |
| 数据规模反推复杂度 | ⭐⭐⭐⭐ | 选择 | n≤1000→O(n²)，n≤10⁵→O(nlogn) |
| sort 与 stable_sort | ⭐⭐⭐ | 判断/选择 | sort不稳定，stable_sort稳定 |
⭐ 必背速记卡
┌─────────────────────────────────────────────┐
│ 排序算法 · 必背速记卡 │
├─────────────────────────────────────────────┤
│ 1. 稳定性：相等元素排序后相对顺序不变 │
│ 2. 冒泡排序：相邻比较交换，稳定，O(n²) │
│ 3. 冒泡优化：已有序时O(n)，用标志位 │
│ 4. 选择排序：每轮选最小交换，不稳定，O(n²) │
│ 5. 插入排序：从后向前插入，稳定，最好O(n) │
│ 6. 选择排序始终O(n²)，无法提前终止 │
│ 7. 三种排序空间复杂度都是 O(1)（原地排序） │
│ 8. 稳定：冒泡+插入；不稳定：选择+sort │
│ 9. 大O表示法：去掉系数和低阶项 │
│ 10. 嵌套循环相乘，串联循环取最高阶 │
│ 11. O(1) < O(logn) < O(n) < O(nlogn) < O(n²)│
│ 12. 每秒约1亿次操作，据此估算能通过的n │
│ 13. n≤1000 → O(n²)没问题；n≤10⁵ → O(nlogn) │
│ 14. sort函数：头文件algorithm，参数为首尾地址│
│ 15. sort默认升序，自定义cmp返回true=排前面 │
└─────────────────────────────────────────────┘