反复比较相邻两个数，谁大谁就往后挪——最大的数会像气泡一样，一轮一轮"冒"到最后面。
冒泡排序的规则只有一句话：从左到右，挨个比较相邻的两个数，如果前面的比后面的大，就交换它们的位置。把这个规则从数组开头扫到结尾，叫做"一轮"——一轮扫完，整个数组里最大的那个数一定会被"挤"到最后一位，就像气泡从水底一点点"冒"到水面，这正是"冒泡"这个名字的来源。
排完一轮还不够——还需要再扫几轮，每一轮都能确定一个新的"最大值"归位到正确的位置上，直到整个数组都排好为止。
用数组 {5, 2, 8, 1, 9} 来演示。外层循环控制"扫几轮"，内层循环负责"这一轮挨个比较相邻的数"：
| 1 | void BubbleSort(int arr[], int n) |
| 2 | { |
| 3 | for (int i = 0; i < n - 1; i++) // 一共扫 n-1 轮 |
| 4 | { |
| 5 | for (int j = 0; j < n - 1 - i; j++) // 范围逐轮缩小 |
| 6 | { |
| 7 | if (arr[j] > arr[j + 1]) |
| 8 | { |
| 9 | int temp = arr[j]; |
| 10 | arr[j] = arr[j + 1]; |
| 11 | arr[j + 1] = temp; |
| 12 | } |
| 13 | } |
| 14 | } |
| 15 | } |
n - 1 - i）？第 1 轮结束后，最大值已经"冒"到了最后一位，第 2 轮就不需要再比到最后一位了（它肯定不需要再动）；第 2 轮结束后，第二大的值也归位了，第 3 轮的范围又能再缩小一点。每轮少比一位，省下来的比较次数会逐渐累积。n-1=4 轮就能全部排好。看第 4 轮——从头比到尾，一次交换都没有发生。这说明数组已经排好了，剩下的轮次都是在白跑。可以在每轮开始前设一个"这一轮有没有发生交换"的标记，如果一轮下来都没有交换过，直接提前结束，不用傻乎乎地把 n-1 轮都跑完。
| 1 | void BubbleSort(int arr[], int n) |
| 2 | { |
| 3 | for (int i = 0; i < n - 1; i++) |
| 4 | { |
| 5 | bool hasSwapped = false; // 这一轮有没有发生过交换 |
| 6 | for (int j = 0; j < n - 1 - i; j++) |
| 7 | { |
| 8 | if (arr[j] > arr[j + 1]) |
| 9 | { |
| 10 | int temp = arr[j]; |
| 11 | arr[j] = arr[j + 1]; |
| 12 | arr[j + 1] = temp; |
| 13 | hasSwapped = true; |
| 14 | } |
| 15 | } |
| 16 | if (!hasSwapped) break; // 这一轮没交换过，说明已经排好了 |
| 17 | } |
| 18 | } |
break 跳出——不加这个判断的话，还要白白扫完剩下 3 轮，多做 6 次没有意义的比较。数组越接近"已经排好"，这个优化省下来的就越多；如果数组本来就很混乱，这个优化基本不会带来什么帮助（最坏情况仍然要扫完所有轮次）。| 情况 | 比较次数 | 时间复杂度 |
|---|---|---|
| 最坏情况（完全逆序） | 约 n²/2 次 | O(n²) |
| 最好情况（已经排好，加了提前结束） | 约 n 次 | O(n) |
n 轮，内层平均要比 n/2 次，总共大约 n²/2 次比较，这正是 2.1 节"枚举的效率问题"里提到过的嵌套循环增长方式。冒泡排序很少在正式比赛里直接拿来对大数据排序（数据量大时跑不动），但它的"相邻比较交换"思想，会在后面学到的冒泡式判重、相邻关系处理等场景里反复出现，并且是理解后面更快排序算法（插入、快排）的一个很好的起点。