【算法图解】冒泡排序：最容易理解的排序

冒泡排序（Bubble Sort）常被吐槽：

慢
过时
面试只会问“你知道它很慢吗”

但它仍然值得学。

原因很简单：它是最容易把“比较排序”讲清楚的算法。

学会冒泡，你会更容易理解：

交换排序的思路
“稳定性”到底是什么意思
为什么 $O(n^2)$ 在数据量大时会崩

1. 冒泡的直觉：大的往后沉

把数组想成一排人，冒泡排序每次只做一件事：

从左到右看相邻两个人
如果顺序不对就交换

这样一轮走完，最大的元素就会被“冒”到最右边。

2. 最基础实现（可运行）

function bubbleSort(arr) {
  const a = arr.slice()
  const n = a.length

  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        const t = a[j]
        a[j] = a[j + 1]
        a[j + 1] = t
      }
    }
  }

  return a
}

console.log(bubbleSort([5, 1, 4, 2, 8]))

两层循环是它慢的根源。

3. 为什么复杂度是 O(n²)？

外层循环跑 $n-1$ 轮
第 1 轮比较 $n-1$ 次
第 2 轮比较 $n-2$ 次
...

总比较次数大约是：

$$ (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2} $$

所以时间复杂度是 $O(n^2)$。

空间复杂度是 $O(1)$（原地交换）。

4. 重要性质：稳定性

“稳定排序”指：

如果两个元素相等
排序后它们的相对顺序不变

冒泡排序是稳定的（因为它只在 > 时交换，不会把相等元素打乱）。

稳定性在工程里很重要：例如按“主键排序”后再按“次键排序”。

5. 一个小优化：如果一轮没交换，直接结束

很多时候数组本来就接近有序，没必要跑满 $n$ 轮。

function bubbleSortOptimized(arr) {
  const a = arr.slice()
  const n = a.length

  for (let i = 0; i < n - 1; i++) {
    let swapped = false

    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        const t = a[j]
        a[j] = a[j + 1]
        a[j + 1] = t
        swapped = true
      }
    }

    if (!swapped) break
  }

  return a
}

这个优化能把“接近有序”的情况变得更快。

6. 面试怎么答？

你可以这样说：

冒泡排序通过相邻比较与交换，让最大元素每轮冒到末尾。
时间复杂度平均/最坏 $O(n^2)$，最好（已排序 + 早停）可到 $O(n)$。
空间复杂度 $O(1)$，稳定排序。

总结

冒泡排序是理解排序的最好起点。
慢是因为两层循环带来的 $O(n^2)$。
它稳定、原地，但不适合大规模数据。