冒泡排序

⚡ 30 秒速记

• 相邻比较、逆序就换，每轮把剩下里最大的「冒」到末尾，最多 n-1 轮
• 平均 / 最坏 O(n²)，加 swapped 提前退出后最好 O(n)；空间 O(1)
• 稳定的前提是相等不换：比较写 >，写成 >= 就不稳定了
• 两个必加优化：一轮没交换就 break、内层边界减掉已排好的 i
• 双向冒泡（鸡尾酒排序）一轮正反各扫一遍，小元素在末尾时更快，但上界还是 O(n²)

冒泡就是相邻两个比，逆序就换，每一轮把剩下里最大的那个推到最后。 平均最坏都是 O(n²)，但只要加一个 swapped 标记，某一轮一次都没换就直接退出，已经有序的数组扫一遍就完，最好情况是 O(n)。还有个很隐蔽的点是比较只能用 >，写成 >= 相等的也会换，稳定性就没了。工程里没人手写它，面试问它其实是看你能不能讲清稳定性和最好最坏情况。

思路：相邻两个元素比较，逆序就交换。每一轮把当前未排序区间里最大的元素"冒"到末尾，n-1 轮后有序。

指标	值
时间复杂度	平均/最坏 O(n²)，最好 O(n)（已有序且做了提前退出优化）
空间复杂度	O(1)（原地）
稳定性	稳定（相等时不交换）

必须加的两个优化：

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let swapped = false                       // ① 提前退出
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {              // ② 用 > 而不是 >=，保证稳定
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        swapped = true
      }
    }
    if (!swapped) break                       // 这一轮没换过 → 已经有序
  }
  return arr
}

• 提前退出：没有它，已排好序的数组仍然要跑满 O(n²)。加上之后最好情况降到 O(n)，这是面试官常追问的点。
• 比较用 > 不是 >=：相等时不交换才能保持稳定性 —— 写成 >= 就把稳定排序变成了不稳定的，这是个很隐蔽的错误。

为什么面试还问它？ 不是因为它实用（工程上没人手写冒泡），而是因为它是理解稳定性和最好/最坏情况差异最简单的载体。能主动说出"稳定性取决于相等时换不换"和"提前退出让最好情况变 O(n)"，比默写代码更有价值。

下面是具体实现：

通过相邻元素比较和交换，使得每一趟循环都能找到未排序的子数组。

实现

function bubbleSort(list) {
  var n = list.length
  if(!n) return []

  for(var i = 0; i < n; i++) {
    for(var j = 0; j < n - i - 1; j++) {
      if(list[j] > list[j + 1]) {
        var temp = list[j + 1]
        list[j + 1] = list[j]
        list[j] = temp
      }
    }
  }
  return list
}