对一组线性存储的数据进行排序。
冒泡排序通过不断重复比较相邻元素的大小关系，将顺序错误的元素进行交换，从而实现排序。每一轮遍历都会将未排序部分中的最值元素"冒泡"到末尾。冒泡排序是使用了贪心法的排序算法。
冒泡排序的执行步骤如下：
冒泡排序还可以通过设置 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] 为例，展示从小到大的冒泡排序完整过程：
| 比较位置 | 比较 | 是否交换 | 数组状态 |
|---|---|---|---|
| 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]
| 比较位置 | 比较 | 是否交换 | 数组状态 |
|---|---|---|---|
| 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]
| 比较位置 | 比较 | 是否交换 | 数组状态 |
|---|---|---|---|
| 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]
| 比较位置 | 比较 | 是否交换 | 数组状态 |
|---|---|---|---|
| j=0 | 1 > 2? 否 | 不交换 | [1, 2, 3, 5, 8] |
没有发生交换，flag 仍为 true，提前结束。
排序完成：[1, 2, 3, 5, 8]
观察规律：
例题：按日期排序
给定若干个日期（年/月/日），按照时间先后排序。
分析过程：
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] 时交换，写成 < 就变成从大到小了>，不要用 >=。使用 >= 会导致相等元素也被交换，破坏冒泡排序的稳定性