冒泡排序

⚡ 30 秒速记

• 思路：相邻比较、逆序交换，每轮把最大值"冒"到末尾，n-1 轮后有序
• 复杂度：平均/最坏 O(n²)，加了提前退出后最好情况 O(n)；空间 O(1)
• 稳定——但前提是相等时不交换（比较用 > 而不是 >=），写错就变成不稳定
• 两个必加优化：swapped 标志位提前退出、内层循环边界减去已排好的 i
• 面试价值不在实用性，而在于它是理解"稳定性"和"最好/最坏差异"最简单的载体

冒泡排序就是反复比较相邻元素并交换逆序项，每轮把未排序区间的最大值推到末尾。 它平均和最坏是 O(n²)，空间是 O(1)；加上 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
}