通过 JavaScript 示例理解快速排序

快速排序是一种分治排序算法：它选取一个基准元素（pivot），对数组进行分区，使较小的元素落在左侧、较大的元素落在右侧，然后原地递归地对两侧分别排序。

我们大多数人第一次接触它，都是在有人盯着看的白板前，而分区循环往往正是让人信心崩塌的地方。它的平均时间复杂度为 O(n log n)，无需分配第二个数组即可完成排序，也是面试官要求你「手写一个排序」时最常想到的算法。

本文涵盖三部分内容：一个便于建立直觉的可读版本、一次手工推演的分区过程（让你真正看到元素如何移动），以及你在面试中实际会写的原地实现，另外还包括关于复杂度、基准选择和稳定性的说明。

快速排序算法是如何工作的？

快速排序通过围绕选定的基准元素反复切分数组来完成排序。一次分区过程会重排元素，使所有小于基准的元素位于其之前、所有大于基准的元素位于其之后；此时基准元素就处在它最终的有序位置上。对左右两个子区间重复同样的步骤，整个数组便完成了排序。

它与归并排序共享分治的结构，但两者的权衡不同。快速排序和归并排序的平均复杂度都是 O(n log n)，但快速排序是原地排序，仅需 O(log n) 的辅助空间，而归并排序需要 O(n) 的额外空间；同时归并排序是稳定的，快速排序则不是。快速排序以放弃稳定性保证为代价，换取了更低的内存开销和优秀的实际运行速度。

先看可读版本（filter 与展开运算符）

最易读的快速排序用 filter 进行分区，并用展开运算符重建数组。这是理解递归结构最快的方式，也是不错的教学工具，但它在每次调用时都会分配新数组，因此并非真正的原地排序，会占用额外内存。

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const [pivot, ...rest] = arr;
  const left = rest.filter((x) => x < pivot);
  const right = rest.filter((x) => x >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

quickSort([3, 7, 2, 5, 1, 4, 6, 8]); // [1, 2, 3, 4, 5, 6, 7, 8]

基线情况（length <= 1）终止递归，因为零元素或单元素数组本身就是有序的。每次调用都会构建三个新数组，所以这个版本的内存占用会随输入规模增长，而非保持常量。需要解释思路时用它；当内存或面试要求更重要时，请使用下面的原地版本。

分区是如何工作的？

分区是快速排序的引擎，因此值得仔细观察一次完整的分区过程。Lomuto 方案取最后一个元素作为基准，用扫描索引 j 遍历整个区间，并维护一个边界索引 i，标记下一个「小于基准」的元素应该放在哪里。每当 arr[j] 小于基准时，就交换 arr[i] 和 arr[j]，并让 i 前进。最后将基准交换到位置 i。

以 [7, 2, 1, 8, 6, 3, 5, 4] 为例，基准为 4（最后一个元素），初始 i = 0：

基准 4 落在索引 3 处，左侧是 [2,1,3]，右侧是 [6,7,5,8]。两侧都还未排序，但基准已经永久就位，两侧现在成为彼此独立的子问题。

function partition(arr, lo, hi) {
  const pivot = arr[hi];          // last element as pivot
  let i = lo;                     // boundary for elements < pivot
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]]; // move pivot into place
  return i;
}

面试中你会写的原地快速排序

接近生产形态的快速排序保留上面的分区辅助函数，并在索引区间（lo、hi）上递归，而不是构建新数组。当有人要求你实现快速排序时，就应该拿出这个版本：它只修改一个数组，额外空间仅来自递归栈。

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
  return arr;
}

quickSort([7, 2, 1, 8, 6, 3, 5, 4]); // [1, 2, 3, 4, 5, 6, 7, 8]

每次调用先对自身区间分区，然后对基准两侧的子区间递归。lo < hi 这个守卫条件就是基线情况：长度为零或一的区间本身已经有序。如果不允许使用递归（这是常见的面试追问），同样的逻辑可以改成迭代版本——把 lo/hi 对压入一个显式栈，替代调用栈即可。

复杂度、基准选择与稳定性

快速排序的开销几乎完全由基准决定。在切分均衡的情况下，每层递归会把每个元素处理一次，共约 log n 层，得到 O(n log n)。当切分持续严重失衡时，递归深度增长到 n，开销退化为 O(n²)。在原地实现中，对于均衡输入，递归栈占用 O(log n) 空间。

经典陷阱：选择第一个或最后一个元素作为基准，会让快速排序在输入已排序时命中 O(n²) 最坏情况，因为每次分区只剥离出一个元素。要避免已排序输入导致的最坏情况，可以选择中间元素、使用三数取中，或选取随机基准。三数取中会对第一个、中间和最后一个元素排序并取其中位数，这种方式能同时抵御正序和逆序的对抗性输入：

function medianOfThree(arr, lo, hi) {
  const mid = Math.floor((lo + hi) / 2);
  if (arr[mid] < arr[lo]) [arr[lo], arr[mid]] = [arr[mid], arr[lo]];
  if (arr[hi]  < arr[lo]) [arr[lo], arr[hi]]  = [arr[hi], arr[lo]];
  if (arr[hi]  < arr[mid]) [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  // median now sits at mid; move it to hi so Lomuto uses it as the pivot
  [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  return arr[hi];
}

有一项特性是任何基准策略都换不回来的：快速排序不是稳定排序，因此相等元素相对于其原始位置可能被重新排列。 当你按次要键排序记录，并期望主键顺序得以保留时，这一点就很关键。

JavaScript 内置的 sort 是快速排序吗？

不是。虽然快速排序算法不稳定，但 JavaScript 内置的 Array.prototype.sort 自 ES2019（该语言标准的第十版） 起就被保证是稳定的。自 v7.0 和 Chrome 70 起，V8 使用 Timsort 对数组排序：这是一种归并排序，能利用数据中已有序的连续片段（run），并保持相等元素原有的相对顺序。规范对其他所有主流引擎也提出了同样的稳定性要求。所以「快速排序不稳定」描述的是算法本身，而非任何现代浏览器中的内置 sort。

快速排序的声誉来自紧凑的分区循环、原地操作以及 O(n log n) 的平均速度——前提是你别让基准落在数组的两端。用三数取中或随机基准实现上面的原地版本，再拿一个已排序的输入跑一遍以确认它不会失控，你就既能写出快速排序，也能随时讲清它的各种权衡。

常见问题

我应该在什么时候用快速排序而不是归并排序？

当内存受限、你希望原地排序时使用快速排序，因为它只需要 O(log n) 的递归栈辅助空间，而归并排序需要 O(n) 的额外数组。两者平均都是 O(n log n)，但在典型数据上快速排序的实际速度更快。当你需要稳定性保证或需要保证 O(n log n) 的最坏情况时，请选择归并排序，因为快速排序可能退化到 O(n 的平方)。

为什么快速排序在已排序数组上会退化到 O(n 的平方)？

固定选取第一个或最后一个元素作为基准，在已排序输入上会退化为 O(n 的平方)，因为每次分区都会把基准放在某一端，产生一个空子区间和一个包含 n 减 1 个元素的区间。这会导致 n 层递归而不是 log n 层，且每层都做线性量的工作。解决办法是选取中间元素、使用三数取中，或选择随机基准，这些方法都能在已排序数据上恢复均衡切分。

JavaScript 的 Array.prototype.sort 是用快速排序实现的吗？

不是。现代引擎的内置 sort 不使用快速排序。自 v7.0 和 Chrome 70 起，V8 使用 Timsort，这是一种归并排序，能利用数据中已有序的连续片段，并保持相等元素的顺序。自 ES2019 起，ECMAScript 规范要求 Array.prototype.sort 必须稳定，所有主流引擎都提供了稳定排序。所以快速排序这个算法是不稳定的，但内置的 sort 并不是快速排序，且被保证稳定。

Lomuto 与 Hoare 分区方案有什么区别？

Lomuto 使用单个扫描索引，通常取最后一个元素作为基准，把较小的元素向一个边界索引处交换；它更容易编写和推演。Hoare 使用两个指针从两端向内移动，通常执行更少的交换，因此在实践中更快。两者都是原地分区并返回一个切分点，但 Hoare 返回的索引不像 Lomuto 那样把基准放在其最终位置上。

如何把递归版快速排序改写成迭代版本？

用一个显式的索引区间栈替代调用栈。先压入初始的 lo 和 hi 这一对值，然后在栈非空时循环：弹出一个区间，对其分区得到基准索引 p，再把两个子区间 lo 到 p 减 1、以及 p 加 1 到 hi 在其包含多于一个元素时压回栈中。这样能在避免递归的同时得到相同结果，这也是常见的面试追问。