深蓝黑背景品牌封面：左侧大标题「快速排序为什么快」，副标题「最坏情况怎么救」；右侧原创装饰——一排数组方块，中间一枚紫色方块标注「基准」，左侧青色小方块、右侧灰色大方块以箭头划向两边，示意按基准把数组一分为二；左上标注「经典题解析 · 算法」，右上标注「Day 01 · 10-09」 图 1：本文封面，点明题目与「基准划分」这个核心动作。

先说明属性：这是一篇经典题解析，题目出自本地历史面试资料，与任何公司的当前招聘无关。快速排序是排序题里的常青树——人人会背 O(n log n)，但面试官真正想听的是：它为什么快、什么时候不快、不快了怎么救。

想象面试现场，面试官说：「讲讲快速排序的思想、时间复杂度，再写写实现，说说怎么优化。」

第一步，讲清思想：分治加划分。

快排每轮做一件事：从数组里选一个基准（pivot），把比它小的挪到左边，比它大的挪到右边，基准就落在了最终位置上。然后对左右两段分别递归重复这个动作，直到每段只剩一个元素。这就是分治：把一个大问题切成两个独立的同类小问题。

第二步，讲清它为什么快。

快在「每次划分都把问题规模砍一刀」。理想情况下基准恰好把数组平分成两半，递归深度是 log n 层，每层划分要扫一遍当前段的全部元素，合起来就是 O(n log n)。类比折纸：每次对折，纸的厚度翻倍，次数是对数级。快排的平均时间复杂度 O(n log n)、原地交换不需要大额外数组，是它压过归并排序成为工程默认选择的原因。

第三步，讲清最坏情况：退化成 O(n²)。

如果基准每次都选到当前段的最值——比如数组已经有序，而你固定取最后一个元素做基准——划分的结果就是一边是 0 个元素、一边是 n-1 个元素。规模一点没砍小，递归变成 n 层，总比较次数退化为 O(n²)，跟冒泡一个量级。更隐蔽的代价是递归深度也变成 n 层，数据量大时直接把调用栈撑爆。

第四步，讲救治方案，全部围绕「让划分更均衡」。

方案一，随机选基准。每次随机抽一个位置当基准，最坏情况出现的概率被压到极低，是最常用的修法。方案二，三数取中。取首、中、尾三个元素的中位数做基准，对有序输入直接免疫，实现成本极低。方案三，三路划分。数组里有大量重复元素时，传统划分会把等于基准的元素也卷进递归；三路划分把「小于、等于、大于」分成三段，等于基准的集中处理、不再递归，重复元素越多收益越大。

第五步，写出可运行的代码并实测。

下面这份实现给出固定基准与随机基准两个版本，并用比较次数和栈溢出实测「有序数组让固定基准退化」这个论断。用 Node.js 22.15.0 直接运行（node quicksort.js）即可：

'use strict';

// 共享的 Lomuto 划分：以 arr[hi] 为基准，返回基准最终位置
function partition(arr, lo, hi, stat) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    stat.cmp++;
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

// 固定取末尾元素做基准
function quicksortLastPivot(arr, lo = 0, hi = arr.length - 1, stat = { cmp: 0 }) {
  if (lo >= hi) return stat.cmp;
  const p = partition(arr, lo, hi, stat);
  quicksortLastPivot(arr, lo, p - 1, stat);
  quicksortLastPivot(arr, p + 1, hi, stat);
  return stat.cmp;
}

// 随机选基准：把随机位置交换到末尾再划分，子问题递归同样走随机基准
function quicksortRandomPivot(arr, lo = 0, hi = arr.length - 1, stat = { cmp: 0 }) {
  if (lo >= hi) return stat.cmp;
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[r], arr[hi]] = [arr[hi], arr[r]];
  const p = partition(arr, lo, hi, stat);
  quicksortRandomPivot(arr, lo, p - 1, stat);
  quicksortRandomPivot(arr, p + 1, hi, stat);
  return stat.cmp;
}

const n = 2000;
const randomArr = Array.from({ length: n }, () => Math.floor(Math.random() * n));
const sortedArr = Array.from({ length: n }, (_, i) => i);

console.log(`随机数组（n=${n}），固定基准比较次数：${quicksortLastPivot([...randomArr])}`);
console.log(`有序数组（n=${n}），固定基准比较次数：${quicksortLastPivot([...sortedArr])}`);
console.log(`有序数组（n=${n}），随机基准比较次数：${quicksortRandomPivot([...sortedArr])}`);

// 退化还有第二个后果：递归深度变成 n 层，直接栈溢出
const big = Array.from({ length: 100000 }, (_, i) => i);
try {
  quicksortLastPivot([...big]);
  console.log('十万元素有序数组，固定基准：成功');
} catch (e) {
  console.log(`十万元素有序数组，固定基准：${e.name}: ${e.message}`);
}
console.log(`十万元素有序数组，随机基准：成功，比较次数 ${quicksortRandomPivot([...big])}`);

实测输出如下（随机基准的数字每次运行略有波动，但量级稳定）：

随机数组（n=2000），固定基准比较次数：24223
有序数组（n=2000），固定基准比较次数：1999000
有序数组（n=2000），随机基准比较次数：24114
十万元素有序数组，固定基准：RangeError: Maximum call stack size exceeded
十万元素有序数组，随机基准：成功，比较次数 1961849

第二行和第三行把问题与答案同时摆上了台面：同样是两千个元素，有序输入让固定基准的比较次数从两万多次暴涨到近两百万次（O(n²) 量级），换成随机基准立刻回落到两万多次；而十万规模的有序数组，固定基准直接栈溢出，随机基准平稳跑完。

解法结构图：上部是快排主流程——选基准、把小于基准的放左、大于基准的放右、左右两段递归，平均每次划分砍半，复杂度 O(n log n)。中部是退化路径——输入已有序且固定取端点做基准时，每次划分得到 0 与 n-1 两段，递归深度变成 n 层，退化为 O(n²)。下部是三种救治方案并排：随机选基准、三数取中、三路划分（大量重复元素时把等于基准的集中处理），底部标注核心结论：快排的快来自均衡划分，优化全部围绕让划分更均衡 图 2：快排的主流程、退化路径与三种救治方案。

可能的追问与易错点。

「快排稳定吗？」不稳定——划分时元素会跨过相等的同类元素。「和归并排序比呢？」归并稳定且严格 O(n log n)，但要 O(n) 额外空间；快排原地、缓存友好，是多数语言内置排序的主力或混合方案的一部分。易错点主要有三：一是只会背复杂度，讲不出退化的具体场景；二是写随机基准时只打乱第一层、子问题递归忘了继续随机（本文第一版代码就犯过这个错）；三是忘了交代递归深度风险，被「有序数组一百万个元素会怎样」问住。

回到面试现场，建议的答题节奏：先讲分治与划分动作，给平均复杂度并解释「砍半」直觉，主动交代最坏 O(n²) 与触发条件，再依次给随机基准、三数取中、三路划分三张牌，最后能落笔写出划分函数。这个节奏展示的是对「均衡」的理解，而不是背题。

「划分—递归」这套思维在 AI 工程里也用得很多：候选集粗排、特征分桶、样本切分，本质都是同一个动作，分区点选得好不好直接决定性能稳不稳。你在快排这道题上被追问到第几层过？欢迎分享。