你有没有想过，怎么把一堆乱糟糟的数字按顺序排好？比如把 [5, 3, 8, 4, 2] 变成 [2, 3, 4, 5, 8]？今天我们要学的冒泡排序，就是最简单的排序方法之一，3分钟就能入门！
什么是冒泡排序？¶
想象一下，水中的气泡会从水底慢慢浮到水面。冒泡排序的名字就来源于这个“气泡上浮”的过程：每一次遍历数组，都会让最大的元素像气泡一样“冒”到数组的末尾，最终完成排序。
举个例子：如果我们要把数字从小到大排序，冒泡排序会让大的数字“往后跑”，小的数字“往前挤”，就像气泡在水里上浮一样。
冒泡排序的核心思想¶
- 重复比较相邻元素：从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素比后一个大，就交换它们的位置。
- “气泡”逐步上浮：每完成一轮遍历，最大的元素会“冒”到数组的最后一个位置（正确位置），所以下一轮可以少比较一次（不需要再管最后一个元素）。
- 提前结束条件：如果某一轮遍历中没有发生任何交换，说明数组已经完全有序，排序可以提前结束。
具体步骤（以 [5, 3, 8, 4, 2] 为例）¶
我们用一个数组 [5, 3, 8, 4, 2] 演示排序过程，目标是从小到大排列。
第1轮：让最大的数“冒”到末尾¶
- 从第一个元素开始比较：
- 比较
5和3：5 > 3，交换 →[3, 5, 8, 4, 2] - 比较
5和8：5 < 8，不交换 → 不变 - 比较
8和4：8 > 4，交换 →[3, 5, 4, 8, 2] - 比较
8和2：8 > 2，交换 →[3, 5, 4, 2, 8] - 结果：最大的数
8已“冒”到末尾，数组变为[3, 5, 4, 2, 8]。
第2轮：让第二大的数“冒”到倒数第二位置¶
- 因为
8已排好，所以这一轮只需比较前4个元素： - 比较
3和5：3 < 5，不交换 - 比较
5和4：5 > 4，交换 →[3, 4, 5, 2, 8] - 比较
5和2：5 > 2，交换 →[3, 4, 2, 5, 8] - 结果：第二大的数
5已“冒”到倒数第二位置，数组变为[3, 4, 2, 5, 8]。
第3轮：让第三大的数“冒”到倒数第三位置¶
- 只需比较前3个元素：
- 比较
3和4：3 < 4，不交换 - 比较
4和2：4 > 2，交换 →[3, 2, 4, 5, 8] - 结果：第三大的数
4已“冒”到倒数第三位置，数组变为[3, 2, 4, 5, 8]。
第4轮：让第四大的数“冒”到倒数第四位置¶
- 只需比较前2个元素：
- 比较
3和2：3 > 2，交换 →[2, 3, 4, 5, 8] - 结果：第四大的数
3已“冒”到倒数第四位置，数组变为[2, 3, 4, 5, 8]。
第5轮：检查是否有序（提前结束）¶
- 此时数组
[2, 3, 4, 5, 8]已经完全有序，若再遍历一次： - 比较
2和3、3和4、4和5、5和8，均无交换。 - 结论：排序完成。
关键优化：提前结束¶
如果某一轮遍历中没有发生任何交换，说明数组已经有序，不需要继续排序。例如，如果数组本身接近有序（如 [1, 3, 2, 4, 5]），冒泡排序会在第二轮就提前结束，减少不必要的比较。
时间复杂度与空间复杂度¶
- 时间复杂度：最坏情况下（数组完全逆序）需要
n²次比较和交换，平均情况也是O(n²)（n为数组长度）。 - 空间复杂度：仅需要常数级额外空间（如交换用的临时变量），所以是
O(1)。
总结¶
冒泡排序的精髓在于“比较相邻元素并交换”，像气泡一样逐步将大元素“冒”到末尾。它简单易懂、容易实现，是理解排序算法的绝佳入门工具。虽然效率较低（适合小规模数据），但通过它你能掌握排序的核心逻辑，为学习更复杂的算法（如快速排序、归并排序）打下基础。
试着手动实现一个冒泡排序，从数组 [6, 1, 7, 3, 2] 开始，相信你很快就能上手！