【算法图解】排序算法可视化：冒泡、快排、归并

排序算法最常见的背诵模式就是这样：

• 冒泡：$O(n^2)$
• 快排：平均 $O(n\log n)$
• 归并：稳定 $O(n\log n)$

但一到“解释过程”，就会卡壳。

这篇我们不先背复杂度，先看“动作”：

• 冒泡看 交换
• 快排看 分区
• 归并看 合并

理解动作后，复杂度和适用场景自然就顺了。

1. 冒泡排序：相邻交换，把最大值“顶”到后面

示例数组：[5, 1, 4, 2, 8]

第一轮比较过程（只看关键状态）：

1. 比较 5 和 1，交换 → [1, 5, 4, 2, 8]
2. 比较 5 和 4，交换 → [1, 4, 5, 2, 8]
3. 比较 5 和 2，交换 → [1, 4, 2, 5, 8]
4. 比较 5 和 8，不交换

第一轮结束后，最大值 8 已经在最终位置。

function bubbleSort(nums: number[]) {
  const arr = [...nums]
  const n = arr.length

  for (let i = 0; i < n - 1; i++) {
    let swapped = false
    for (let j = 0; j < n - 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^2)$

2. 快速排序：选基准，做分区

快排的本质不是“快”，而是递归地把问题切小。

示例数组：[6, 3, 8, 5, 2, 7, 4, 1]

以最后一个元素 1 为 pivot：

• 扫描一遍后，所有 < 1 的元素放左边，>= 1 的放右边
• pivot 落到最终位置
• 对左右两段继续做同样动作

function quickSort(nums: number[]) {
  const arr = [...nums]

  function partition(left: number, right: number) {
    const pivot = arr[right]
    let i = left

    for (let j = left; j < right; j++) {
      if (arr[j] < pivot) {
        ;[arr[i], arr[j]] = [arr[j], arr[i]]
        i++
      }
    }

    ;[arr[i], arr[right]] = [arr[right], arr[i]]
    return i
  }

  function sort(left: number, right: number) {
    if (left >= right) return
    const p = partition(left, right)
    sort(left, p - 1)
    sort(p + 1, right)
  }

  sort(0, arr.length - 1)
  return arr
}

要点：

• 平均复杂度 $O(n\log n)$，最坏会退化到 $O(n^2)$
• 常见优化：随机 pivot、三数取中、三路快排
• 原地排序，额外空间主要是递归栈

3. 归并排序：先拆再合，合并时有序

归并的动作模型是：

1. 把数组对半拆到单个元素
2. 两两合并成有序数组

示例：[5, 2, 4, 7, 1, 3, 2, 6]

• 拆分：[5,2,4,7] 与 [1,3,2,6]
• 继续拆到长度 1
• 合并时每次取两段的较小值，形成有序段

function mergeSort(nums: number[]) {
  if (nums.length <= 1) return nums

  const mid = Math.floor(nums.length / 2)
  const left = mergeSort(nums.slice(0, mid))
  const right = mergeSort(nums.slice(mid))

  const result: number[] = []
  let i = 0
  let j = 0

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++])
    } else {
      result.push(right[j++])
    }
  }

  return result.concat(left.slice(i), right.slice(j))
}

要点：

• 时间复杂度稳定 $O(n\log n)$
• 稳定排序
• 需要 $O(n)$ 额外空间

4. 排序算法对比与选型

稳定性为什么重要：若排序关键字相同，稳定排序保证原相对顺序不变。

例如：按分数排序学生，分数相同时要保持名单原顺序。

5. 面试常见深化题

题 5.1：快排何时退化成 $O(n^2)$？

当 pivot 每次都选到极值（最小或最大值），导致每次只切掉 1 个元素而不是平分。

防守方案：

• 随机 pivot：pivot = arr[Math.random() * len | 0]
• 三数取中：median(first, mid, last)
• 切换算法：元素很少时用插入排序

题 5.2：什么时候要选归并而不是快排？

1. 需要保证稳定排序（比如数据库排序）
2. 最坏情况也必须是 $O(n\log n)$（金融计算对上界敏感）
3. 外排（数据量超过内存）——很适合归并的外排思想

题 5.3：堆排序在工程中为什么用得少？

虽然原地、$O(n\log n)$ 稳定，但：

• CPU 缓存不友好（访问模式随机）
• 常数系数大（很多交换）
• 不稳定（某些场景问题）

通常只在"Top K 问题"用堆（维护大小为 K 的堆）。

总结

排序不是单纯地记公式，而是掌握思想与权衡：

• 冒泡：交换视角，理解排序最基础的操作
• 快排：分治视角，工业界最常用但要防退化
• 归并：拆合视角，稳定性与上界稳定的保证
• 深化：稳定性、常数系数、缓存友好度——这些决定工程选型

当你能在 5 分钟内写出一个排序、讨论它的陷阱与优化，就达到面试水平。