【算法图解】快速排序：面试必问的排序

快速排序（Quick Sort）是面试高频题：

你不一定手写得完美
但你必须讲清楚它的核心：分区（partition）

快排的“快”不是魔法，而是结构：

分治
原地
平均 $O(n\log n)$

但它也有一个致命点：最坏 $O(n^2)$。

这篇文章让你既能讲清楚，也能写出可靠版本。

1. 快排的直觉：找一个 pivot，把数组分成两边

给你一个 pivot：

所有比 pivot 小的放左边
所有比 pivot 大的放右边
pivot 放到它最终应该在的位置

然后递归排左右两边。

2. 核心：partition 怎么做？（Lomuto 版本）

Lomuto 分区更容易讲清楚：

选最后一个元素作为 pivot
用一个指针 i 维护“小于 pivot 的区域”末端
用 j 扫描数组

function partition(a, lo, hi) {
  const pivot = a[hi]
  let i = lo

  for (let j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      ;[a[i], a[j]] = [a[j], a[i]]
      i++
    }
  }

  ;[a[i], a[hi]] = [a[hi], a[i]]
  return i
}

partition 结束后：

i 就是 pivot 的最终位置

3. 递归实现（可运行）

function quickSort(arr) {
  const a = arr.slice()

  function sort(lo, hi) {
    if (lo >= hi) return
    const p = partition(a, lo, hi)
    sort(lo, p - 1)
    sort(p + 1, hi)
  }

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

console.log(quickSort([3, 6, 8, 10, 1, 2, 1]))

平均时间：$O(n\log n)$

空间（递归栈）：平均 $O(\log n)$。

4. 为什么最坏会变 O(n²)？

如果 pivot 每次都选到极端值：

例如数组已排序，pivot 选最后一个
每次分区都只划出一个元素

递推变成：

$$T(n)=T(n-1)+O(n)$$

所以最坏 $O(n^2)$。

5. 工程优化：让快排“稳”起来

5.1 随机 pivot

在进入 partition 前随机挑一个 pivot 与 hi 交换。

function randInt(lo, hi) {
  return lo + Math.floor(Math.random() * (hi - lo + 1))
}

随机化能把“被恶意构造输入”打回平均情况。

5.2 三数取中

从 lo/mid/hi 取中位数当 pivot，适合部分有序数据。

5.3 小数组切换插排

当子数组很小（比如 <= 16），插排更快（常数更小）。

5.4 尾递归优化 / 显式栈

在 JS 里你无法指望引擎做 TCO，递归深度过大可能爆栈。

常见做法：

每次先递归处理更小的一边
大的一边用循环继续（减少最大栈深度）

6. 稳定性与适用场景

快排通常不稳定（分区交换会打乱相等元素相对顺序）
适合内存敏感、希望原地排序的场景
如果需要稳定性且能接受 $O(n)$ 额外空间，归并是更稳的选择

7. 面试回答模板

快排是分治：partition 把 pivot 放到最终位置，递归处理左右。
平均时间 $O(n\log n)$，最坏 $O(n^2)$。
通过随机 pivot / 三数取中等方式避免退化。
空间主要来自递归栈，平均 $O(\log n)$。

总结

快排的灵魂是 partition。
最坏情况来自 pivot 选择退化。
随机化与小数组优化能让快排在工程里更可靠。

【算法图解】快速排序：面试必问的排序

相关标签