本课时有配套视频讲解，购买后即可观看（永久有效）
冒泡排序
一、课上练习
编程练习
二、知识总结
✨ 冒泡排序的核心思想
对一组线性存储的数据进行排序。
冒泡排序通过不断重复比较相邻元素的大小关系，将顺序错误的元素进行交换，从而实现排序。每一轮遍历都会将未排序部分中的最值元素"冒泡"到末尾。冒泡排序是使用了贪心法的排序算法。
✨ 冒泡排序的原理
冒泡排序的执行步骤如下：
- 初始化：标记已排序部分为空
- 从第一个元素开始遍历未排序部分：
- 逐对比较相邻元素大小
- 交换顺序错误的两个元素
- 更新已排序部分（每轮结束后，最后一个元素已就位）
- 重复步骤 2-3，直到所有元素都已排序
冒泡排序还可以通过设置 flag 标记来优化：如果某一轮遍历中没有发生任何交换，说明数组已经有序，可以提前结束。
从小到大排序
冒泡排序从小到大代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[1005] = {};
5
6int main() {
7 int n;
8 cin >> n;
9 for (int i = 0; i < n; ++i) {
10 cin >> arr[i];
11 }
12 for (int i = 0; i < n - 1; ++i) {
13 bool flag = true;
14 for (int j = 0; j < n - 1 - i; ++j) {
15 if (arr[j] > arr[j + 1]) {
16 swap(arr[j], arr[j + 1]);
17 flag = false;
18 }
19 }
20 if (flag) {
21 break;
22 }
23 }
24 for (int i = 0; i < n; ++i) {
25 cout << arr[i] << (i + 1 == n ? "\n" : " ");
26 }
27 return 0;
28}从大到小排序
只需将比较条件从 > 改为 <，每次将较小的元素向后移动：
冒泡排序从大到小代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[1005] = {};
5
6int main() {
7 int n;
8 cin >> n;
9 for (int i = 0; i < n; ++i) {
10 cin >> arr[i];
11 }
12 for (int i = 0; i < n - 1; ++i) {
13 bool flag = true;
14 for (int j = 0; j < n - 1 - i; ++j) {
15 if (arr[j] < arr[j + 1]) {
16 swap(arr[j], arr[j + 1]);
17 flag = false;
18 }
19 }
20 if (flag) {
21 break;
22 }
23 }
24 for (int i = 0; i < n; ++i) {
25 cout << arr[i] << (i + 1 == n ? "\n" : " ");
26 }
27 return 0;
28}✨ 冒泡排序的复杂度分析
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n^2) |
| 空间复杂度 | O(1) |
| 稳定性 | 稳定排序 |
冒泡排序的时间复杂度为 O(n^2)，因为需要两层嵌套循环。空间复杂度为 O(1)，只需要常数级别的额外空间用于交换。冒泡排序是稳定的排序算法，因为只在严格大于（或小于）时才交换，相等元素的相对顺序不会改变。
✨ 冒泡排序的执行示例
以数组 [5, 3, 8, 1, 2] 为例，展示从小到大的冒泡排序完整过程：
第1轮（i=0）：比较 4 次，把最大值"冒泡"到末尾
| 比较位置 | 比较 | 是否交换 | 数组状态 |
|---|---|---|---|
| j=0 | 5 > 3? 是 | 交换 | [3, 5, 8, 1, 2] |
| j=1 | 5 > 8? 否 | 不交换 | [3, 5, 8, 1, 2] |
| j=2 | 8 > 1? 是 | 交换 | [3, 5, 1, 8, 2] |
| j=3 | 8 > 2? 是 | 交换 | [3, 5, 1, 2, 8] |
第1轮结束：8 已到达正确位置 → [3, 5, 1, 2, 8]
第2轮（i=1）：比较 3 次
| 比较位置 | 比较 | 是否交换 | 数组状态 |
|---|---|---|---|
| j=0 | 3 > 5? 否 | 不交换 | [3, 5, 1, 2, 8] |
| j=1 | 5 > 1? 是 | 交换 | [3, 1, 5, 2, 8] |
| j=2 | 5 > 2? 是 | 交换 | [3, 1, 2, 5, 8] |
第2轮结束：5 已到达正确位置 → [3, 1, 2, 5, 8]
第3轮（i=2）：比较 2 次
| 比较位置 | 比较 | 是否交换 | 数组状态 |
|---|---|---|---|
| j=0 | 3 > 1? 是 | 交换 | [1, 3, 2, 5, 8] |
| j=1 | 3 > 2? 是 | 交换 | [1, 2, 3, 5, 8] |
第3轮结束：3 已到达正确位置 → [1, 2, 3, 5, 8]
第4轮（i=3）：比较 1 次
| 比较位置 | 比较 | 是否交换 | 数组状态 |
|---|---|---|---|
| j=0 | 1 > 2? 否 | 不交换 | [1, 2, 3, 5, 8] |
没有发生交换，flag 仍为 true，提前结束。
排序完成：[1, 2, 3, 5, 8]
观察规律：
- 第 k 轮比较 n-1-k 次（因为末尾 k 个元素已经有序）
- 每轮结束后，未排序部分的最大值一定"冒泡"到了最右边
✨ 冒泡排序的解题步骤
例题：按日期排序
给定若干个日期（年/月/日），按照时间先后排序。
分析过程：
- 选择排序算法：冒泡排序可以完成此任务
- 设计比较规则：先比较年，年相同比较月，月相同比较日
- 修改冒泡排序的比较条件：
1struct Date {
2 int year, month, day;
3};
4
5// 判断 a 是否应该排在 b 后面（a 的日期晚于 b）
6bool isLater(Date a, Date b) {
7 if (a.year != b.year) return a.year > b.year;
8 if (a.month != b.month) return a.month > b.month;
9 return a.day > b.day;
10}
11
12// 冒泡排序
13for (int i = 0; i < n - 1; ++i) {
14 bool flag = true;
15 for (int j = 0; j < n - 1 - i; ++j) {
16 if (isLater(dates[j], dates[j + 1])) {
17 swap(dates[j], dates[j + 1]);
18 flag = false;
19 }
20 }
21 if (flag) break;
22}关键思路： 冒泡排序只关心"相邻两个元素谁应该在前"，将复杂的比较逻辑封装成一个函数，排序框架不用改。
✨ 冒泡排序的常见错误
- 内层循环上界写错：应该是
j < n - 1 - i，而不是j < n - 1或j < n。写成j < n - 1虽然结果正确，但每轮都会多做无用比较；写成j < n会导致arr[j+1]数组越界 - 比较条件写反：从小到大排序应该用
arr[j] > arr[j+1]时交换，写成<就变成从大到小了 - flag 优化位置错误：flag 应在每轮开始时重置为 true，在交换时设为 false。如果放在循环外面初始化就只能优化第一轮
- 相等时也交换：比较时应使用严格大于
>，不要用>=。使用>=会导致相等元素也被交换，破坏冒泡排序的稳定性 - 误以为冒泡排序一定需要 n-1 轮：加上 flag 优化后，如果数据已经有序，第1轮就不会发生交换，可以直接结束