排序算法系列 02：冒泡排序——最笨但最好懂的排序
冒泡排序大概是所有人学排序时接触的第一个算法。名字很形象：大的数字像气泡一样，一轮一轮地往数组末尾"冒"。
说实话，冒泡排序在实际开发中几乎不会用到。但它作为理解排序思想的起点，确实没有比它更合适的了。
核心思想
就一句话：相邻的两个元素比一比，顺序反了就换过来。每一轮结束，当前最大的那个一定到了最后。
text
原始数组：5, 2, 9, 1, 7
第一轮结束：2, 5, 1, 7, 9
第一轮跑完，9 已经归位。下一轮就不用管它了，继续处理前面的。
你可以想象一排人按身高站队——从左到右，两两比较，高的往右挪。一轮下来，最高的那个肯定被推到了最右边。
走一遍过程
用 [5, 2, 9, 1, 7] 跑一遍：
第一轮：
text
5 和 2 比 → 交换 → 2, 5, 9, 1, 7
5 和 9 比 → 不动 → 2, 5, 9, 1, 7
9 和 1 比 → 交换 → 2, 5, 1, 9, 7
9 和 7 比 → 交换 → 2, 5, 1, 7, 9
9 归位。
第二轮：
text
2 和 5 比 → 不动 → 2, 5, 1, 7, 9
5 和 1 比 → 交换 → 2, 1, 5, 7, 9
5 和 7 比 → 不动 → 2, 1, 5, 7, 9
7 归位。
继续重复，最终得到 1, 2, 5, 7, 9。
代码实现
javascript
function bubbleSort(arr) {
const result = [...arr];
for (let i = 0; i < result.length - 1; i++) {
for (let j = 0; j < result.length - 1 - i; j++) {
if (result[j] > result[j + 1]) {
const temp = result[j];
result[j] = result[j + 1];
result[j + 1] = temp;
}
}
}
return result;
}
console.log(bubbleSort([5, 2, 9, 1, 7]));
// [1, 2, 5, 7, 9]
两层循环：
- 外层控制轮数——总共需要
n - 1轮 - 内层做相邻比较和交换——每轮比较范围会缩小，因为尾部已经排好了
result.length - 1 - i 就是这个意思：第 i 轮之后，后面 i 个元素已经就位，不用再碰了。
一个小优化
如果某一轮里一次交换都没发生，说明数组已经有序了，直接收工。
javascript
function bubbleSortOptimized(arr) {
const result = [...arr];
for (let i = 0; i < result.length - 1; i++) {
let swapped = false;
for (let j = 0; j < result.length - 1 - i; j++) {
if (result[j] > result[j + 1]) {
const temp = result[j];
result[j] = result[j + 1];
result[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
return result;
}
加了个 swapped 标志位，这样如果输入本身就有序，只跑一轮就结束，时间复杂度降到 O(n)。
复杂度
| 情况 | 时间复杂度 |
|---|---|
| 最好（已有序） | O(n) |
| 平均 | O(n²) |
| 最坏（完全逆序） | O(n²) |
空间复杂度 O(1)——只用了几个临时变量，没有额外数组。
稳定性：稳定。相等的元素不会交换位置，相对顺序保持不变。
说点实话
冒泡排序的优点就一个：好理解。
缺点也很明显：慢。O(n²) 意味着数据翻一倍，时间变四倍。1000 条数据还凑合，10000 条就明显卡了。
所以它的定位很清楚：学习用，不是生产用。 理解了"相邻交换"和"每轮确定一个最大值"这两个概念，冒泡排序的使命就完成了。
下一篇来看选择排序——同样是 O(n²)，但思路完全不同。
系列导航