快速排序的 partition 为什么是分治关键？如何避免退化？

简化版

快速排序的核心是 partition：选一个基准值，把小于基准的放左边，大于基准的放右边。

分区完成后，基准位置已经确定，再递归排序左右两边。

平均时间复杂度是 O(n log n)，但如果基准选得很差，可能退化到 O(n^2)；随机选 pivot 或三数取中可以降低风险。

详细版

快排也是分治：先通过 partition 把数组分成两个子问题，再递归处理。

partition 的目标不是完全排序，而是让 pivot 左侧都不大于它，右侧都不小于它。这样 pivot 的最终位置就确定了。

如果每次分区都接近均匀，递归深度是 log n，每层 partition 总成本是 O(n)，平均 O(n log n)。

如果每次 pivot 都是最小或最大，递归会变成一条链，复杂度退化为 O(n^2)。

完整版教学

一、partition 到底解决了什么

快排不是先把左右子数组排好再合并，而是先把 pivot 放到正确位置。partition 后，pivot 左侧元素都不大于它，右侧元素都不小于它。此时 pivot 已经不用再动，剩下只需要递归处理左右区域。

记忆钩子：归并排序是“先递归后合并”，快速排序是“先分区后递归”。

二、分治结构如何体现

快速排序的递归结构是：

sort(nums, l, r)
先 partition 得到 p
再 sort(nums, l, p-1)
再 sort(nums, p+1, r)

左右子问题之间没有交叉，因为 pivot 已经把数组分成了两个互不影响的部分。这个分治结构非常干净，唯一风险在于子问题规模是否均衡。

三、Lomuto 分区代码

常见写法如下：

function partition(nums, l, r) {
  const pivot = nums[r]
  let i = l
  for (let j = l; j < r; j++) {
    if (nums[j] <= pivot) {
      ;[nums[i], nums[j]] = [nums[j], nums[i]]
      i++
    }
  }
  ;[nums[i], nums[r]] = [nums[r], nums[i]]
  return i
}

这里 [l, i) 是不大于 pivot 的区域，[i, j) 是大于 pivot 的区域。扫描结束后把 pivot 放到 i。

四、复杂度为什么可能退化

如果每次 pivot 都把数组分成接近两半，递归树高度是 log n。如果数组已经有序，而每次都选最后一个元素作为 pivot，那么每次只能分出一个空区间和一个长度减一的区间。

分区情况	递归高度	总复杂度
接近均匀	`log n`	`O(n log n)`
极端不均匀	`n`	`O(n^2)`
随机 pivot	期望 `log n`	期望 `O(n log n)`

快排性能的关键就是 pivot 质量。

五、如何降低退化风险

常见策略有随机 pivot、三数取中、对小数组改用插入排序、递归较小区间以减少栈深度。随机 pivot 最容易解释：随机选一个位置和末尾交换，再执行 partition。这样输入是否有序就不再系统性影响 pivot 选择。

const p = l + Math.floor(Math.random() * (r - l + 1))
;[nums[p], nums[r]] = [nums[r], nums[p]]

这不能保证绝不退化，但能让退化概率非常低。

六、常见误区与追问

误区：partition 后左右两边已经有序。 partition 只保证相对 pivot 的大小关系，左右内部仍需递归排序。
误区：认为快排最坏也是 O(n log n)。 基准极差时会退化到 O(n^2)。
误区：重复元素多时不处理。 二路 partition 在大量重复值时可能不均衡，三路快排更合适。
追问：快排稳定吗？ 常规原地快排不稳定，因为交换可能改变相等元素的相对顺序。
追问：为什么工程里快排仍常用？ 原地、缓存友好、平均性能好，配合随机化和优化很强。

这些追问都能从 partition 的语义和 pivot 质量展开。

七、加强记忆

快排记成“pivot 定位，左右递归”。partition 只做一件事：把 pivot 放到最终位置，并按 pivot 分区。复杂度好坏取决于分区是否均衡；随机 pivot、三数取中和三路分区都是为了让递归树别长歪。和归并排序对比记忆，会更牢。

简化版

详细版