手写快排及复杂度分析｜好未来前端面经解析

60 秒回答模板

快速排序的核心是 partition：选一个 pivot，把数组原地区分成小于、等于和大于 pivot 的区间，再只递归小于区间和大于区间。递归边界是区间长度小于 2。每一层 partition 会线性扫描当前区间，pivot 比较均衡时递归树高度约 logn，所以平均时间是 O(nlogn)；如果每次 pivot 都落在最小或最大值，递归会退化成 n 层，时间变成 O(n²)。空间上 partition 本身是 O(1)，递归栈平均 O(logn)、最坏 O(n)，可以通过随机 pivot、三数取中和优先递归较短区间降低退化和爆栈风险。快排通常不稳定，因为交换会改变相等元素的原始相对顺序。

考点 核心机制与工程取舍

难度 中高频面试题

回答目标 按定义、机制、场景讲清楚

深入解析

函数契约和递归边界

手写时先定义 quickSort(arr, l, r) 表示原地排序闭区间 [l, r]。当 l >= r 时直接返回，覆盖空区间、单元素区间和递归越界。对外层 quickSort(arr)，空数组、非数组或长度小于 2 都可以直接返回原数组。

partition 的关键是不变量

三路分区维护四段不变量：[l + 1, lt] < pivot、[lt + 1, i - 1] == pivot、[i, gt] 未处理、[gt + 1, r] > pivot。小于 pivot 就扩大小于区，大于 pivot 就换到右侧且 i 不前进，等于 pivot 才直接前进。

递归只处理未有序两侧

partition 返回等于 pivot 的连续区间 [lt, gt] 后，这一段已经处在最终相对分区位置，不需要再排。递归只处理 [l, lt - 1] 和 [gt + 1, r]，大量重复值时比普通二路分区更稳。

复杂度从递归树推导

每次 partition 对当前区间做线性扫描，单层所有子问题合计处理 O(n) 个元素。pivot 均衡时递归树高度约 logn，T(n)=2T(n/2)+O(n)=O(nlogn)；pivot 极端时 T(n)=T(n-1)+O(n)=O(n²)。

空间复杂度分清口径

原地 partition 只需要常数个指针和交换变量，是 O(1) 额外数据空间；完整递归实现还要算调用栈，均衡划分时平均 O(logn)，极端不均衡时最坏 O(n)。

重复元素、pivot 和稳定性

大量重复元素时三路快排能把等于 pivot 的元素一次性归位。随机 pivot 能降低输入形态对复杂度的影响，三数取中能缓解已排序或近似有序数组。常见原地快排不稳定，因为 partition 交换可能改变相等元素相对顺序。

javascript

三路快排最小实现

function quickSort(arr) {
  if (!Array.isArray(arr) || arr.length < 2) return arr;
  sort(arr, 0, arr.length - 1);
  return arr;
}

function sort(a, l, r) {
  while (l < r) {
    const [lt, gt] = partition3(a, l, r);

    if (lt - l < r - gt) {
      sort(a, l, lt - 1);
      l = gt + 1;
    } else {
      sort(a, gt + 1, r);
      r = lt - 1;
    }
  }
}

function partition3(a, l, r) {
  const pivotIndex = l + Math.floor(Math.random() * (r - l + 1));
  swap(a, l, pivotIndex);

  const pivot = a[l];
  let lt = l;
  let i = l + 1;
  let gt = r;

  while (i <= gt) {
    if (a[i] < pivot) {
      swap(a, ++lt, i++);
    } else if (a[i] > pivot) {
      swap(a, i, gt--);
    } else {
      i++;
    }
  }

  swap(a, l, lt);
  return [lt, gt];
}

function swap(a, i, j) {
  if (i !== j) [a[i], a[j]] = [a[j], a[i]];
}

大于 pivot 时右侧换回来的元素还未检查，所以 i 不能前进。
优先递归较短区间能降低递归栈风险，但最坏时间仍可能是 O(n²)。

易错点

递归边界写成 l > r，导致单元素区间继续 partition。
三路分区后还递归 [lt, gt]，让大量重复值场景失去优化效果。
大于 pivot 时从右侧换回未知元素却 i++，跳过未检查元素。
只说平均 O(nlogn)，不说明固定 pivot 在有序或逆序数组上可能退化到 O(n²)。
把原地快排空间复杂度直接说成 O(1)，漏掉递归栈平均 O(logn)、最坏 O(n)。
把快排答成稳定排序，忽略 partition 交换会改变相等元素相对顺序。

面试官追问

数组已经有序，快排一定是 O(nlogn) 吗？

不一定。如果固定选首元素或尾元素做 pivot，已排序数组会每次切出一个空区间和一个 n - 1 区间，递归式是 T(n)=T(n-1)+O(n)，最坏 O(n²)。

大量重复元素怎么处理？

推荐三路快排，把 < pivot、= pivot、> pivot 分成三段，等于 pivot 的中间段不再递归。重复值越多，子问题缩小越明显。

为什么 partition 一趟是 O(n)？

每个元素在当前区间内至多被扫描和交换常数次。三路分区里 i 向右推进或 gt 向左收缩，每轮都会缩小未知区间 [i, gt]。

空间复杂度到底是 O(1) 还是 O(logn)？

partition 过程只用几个指针和临时变量，是 O(1) 额外数据空间；完整递归实现还要算调用栈，平均 O(logn)，最坏 O(n)。

快排稳定吗？

常见原地快排不稳定。partition 会交换元素，相等元素可能因为和 pivot 或其他元素交换而改变原始相对顺序。