30 秒速记

• 相邻两个比，前面大就交换，每一轮把剩下的最大值「冒」到右边
• 第 i 轮结束，右边 i 个元素已经在最终位置
• 加 swapped 标记：一轮没交换就提前结束，有序输入最好 O(n)
• 平均、最坏 O(n²)，原地 O(1)；只在严格 > 时交换才稳定
• 生产代码别手写冒泡，直接用 Array.prototype.sort，从 ES2019 起规范要求它稳定

冒泡排序就是相邻两个数比大小，前面大就换，一轮下来最大的数会被一路推到最右边，像气泡浮上来一样。 所以每过一轮，右边就多一个排好的元素，下一轮不用再管它。我写的时候会加一个 swapped 标记，一整轮都没交换说明已经有序，直接退出，这样有序输入只要 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
}
bubbleSort([5, 3, 2, 4, 1]) // [1, 2, 3, 4, 5]

30 秒速记

• 从头开始比相邻两项，前大后小就交换，否则不动
• 一轮下来，未排序区的最大值一定被推到区间最右边
• 第 round 轮结束后，最后 round 个元素归位，下轮不用再碰
• 内层只比到 j < n - 1 - round，访问 arr[j] 和 arr[j + 1]
• 外层其实跑 n - 1 轮就够，剩最后一个时它自然就位

冒泡的思路就一句话：一直比相邻两个，前面大就换，每一轮能确定一个当前最大值的位置。 为什么最大值一定会到最右边？因为它不管从哪开始，往右遇到的都比它小，每次比较都会被换过去，一路换到底。所以 n 个数最多 n - 1 轮就排完了，而且每轮的扫描范围都可以缩短一格。说清这个「右侧已排好区间」的不变量，比背代码重要，面试官追问边界时全靠它。

30 秒速记

• 以 [5, 3, 2, 4, 1] 为例：第一轮 5 一路换到末尾 → [3, 2, 4, 1, 5]
• 第二轮 4 归位 → [2, 3, 1, 4, 5]，第三轮 3 归位 → [2, 1, 3, 4, 5]
• 第四轮 2 和 1 交换后整体有序 → [1, 2, 3, 4, 5]
• 不交换的比较也算一步（比如 3 和 4 比完不换），演示时别漏
• 基础写法有序了也不会停，要靠 swapped 才能提前结束

手推冒泡的关键是看每一轮结束时，右边多了哪个排好的数。 拿 [5, 3, 2, 4, 1] 来说，第一轮 5 连换四次到了末尾，变成 [3, 2, 4, 1, 5]，这时候只是 5 归位了，整体还是乱的。第二轮 4 归位，第三轮 3 归位，第四轮把 2 和 1 一换就全有序了。基础写法这时候不会停，还会接着比，这就是后面要加标记优化的原因。