快速排序全攻略：核心思路、递归与非递归实现及优化-平芜编程栈

标题就说三个字：快排。但凡是认真准备过算法题或者实际写过排序的开发者，应该都清楚这三个字背后起码藏着三种思路、五种写法、一堆边界条件。这道题在面试和日常工程里都特别常见，可很多人第一反应是“这题我会”，一上机写又容易栽在边界和性能上。

今天就围绕【算法题】快排，完整梳理一遍快排的核心思路、递归与非递归实现、常见优化手段，以及我踩过的那些坑。从完全没接触过的新手，到需要应付手写算法的求职者，都能从这里拿到一套可以直接复现的方案。

1. 快排思路拆解：从“分而治之”到“原地交换”

1.1 快排到底在排什么

先明确一个问题：我们聊的快排，全称是快速排序（Quicksort），核心思想是“分而治之”。它做的事情很朴素——每次从待排序区间里挑一个基准值，通过一趟扫描，把比基准值小的元素放到它左边，比它大的放到右边，然后基准值就回到了它最终应该在的位置。剩下的工作就是对左右两个子区间继续做同样的事，直到区间里只剩一个元素或者没有元素。

这种“拆大问题为小问题”的思路，带来的是平均时间复杂度 O(n log n)。为什么不是 O(n) 也不是 O(n²)？因为每趟 partition 花费 O(n) 时间，递归树的高度在理想情况下是 log n，乘起来就是 O(n log n)。这个复杂度比冒泡、插入这类 O(n²) 算法在数据量大的时候有明显优势，所以快排在很多场景下都被当作默认排序方案。

但这里有一个地方需要说透：快排并不是所有情况下都稳赢。它的最坏情况是 O(n²)，比如每次都选到当前区间的最小值或最大值作为基准值，递归树直接退化成一条链。这个特性在刷题、面试、甚至线上性能排查时都非常重要，后面第 2、3 节会专门讲怎么规避。

另外，快排还是“原地排序”的一个代表。所谓原地，就是不需要额外的、与数据规模成正比的内存来存放临时数组。整个排序过程主要靠交换元素完成，额外空间主要是递归调用带来的栈空间，期望为 O(log n)。这一点让它在内存敏感的场景下特别有吸引力。

1.2 单趟排序的三个关键角色：基准值、左指针、右指针

快排的单趟排序，也就是 partition，是整个算法的核心。一句话概括：通过两个指针从区间的两端往中间走，把不符合“左小右大”的元素交换掉，最终让基准值落在它该在的位置。

用一个简单例子走一遍，比如数组 [5, 1, 4, 2, 8]，选最左边的 5 作为基准值。

左指针 i 从最左边开始，右指针 j 从最右边开始。
先从右往左找比基准值小的元素，找到 2，把它拿到左侧空出来的位置。
再从左往右找比基准值大的元素，找到 8，把它拿到右侧空出来的位置。
两指针继续靠拢，直到相遇，把基准值 5 放回相遇点。

一趟完成后，数组变成 [2, 1, 4, 5, 8]，5 左边全是小于等于它的元素，右边全是大于等于它的元素。接下来对左侧 [2, 1, 4] 和右侧 [8] 递归排序。这个过程就像是先通过一趟粗筛，把整个数组的“中心轴”立起来，再分别处理左右两部分。

这里最容易忽视的一点是：一趟 partition 做完之后，基准值的位置是确定的，但左右两个区间内部还是乱序的。所以快排不是一趟搞定，而是不断递归缩小问题规模。只要每次都能把区间大概切半，总的排序效率就会非常高。

2. 核心实现：从递归代码到三种 partition 风格

2.1 挖坑法递归实现：最直观的写法

面试手写快排的时候，我最推荐“挖坑法”。它最符合人脑直觉，代码也不容易出错。思路是：先把基准值从数组里“取出来”，于是这个位置变成一个“坑”，然后从右往左找小的填坑，填完左边出新坑，再从左往右找大的填坑，循环往复。

def quicksort(nums, left, right): if left >= right: return pivot = nums[left] i, j = left, right while i < j: while i < j and nums[j] >= pivot: j -= 1 nums[i] = nums[j] while i < j and nums[i] <= pivot: i += 1 nums[j] = nums[i] nums[i] = pivot quicksort(nums, left, i - 1) quicksort(nums, i + 1, right)

这段代码接口是quicksort(nums, 0, len(nums) - 1)。有两个细节需要反复确认：

循环里的等号不能丢。nums[j] >= pivot和nums[i] <= pivot里的等号，是为了让等于基准值的元素也能被越过，避免出现两指针卡死导致的死循环。
递归边界是left >= right，不是left == right。因为当基准值在某一段区间的最边上时，递归子区间会出现left > right的情况。

从执行过程来看，这种写法每趟把基准值“埋”进正确位置，代码量只有十几行，适合作为标准答案。实际跑一个长度为十万的随机数组，递归版在默认递归深度内完全没有问题，表现也很稳定。

2.2 Lomuto 分区与 Hoare 分区：换一种姿势

除了挖坑法，还有两种常见分区写法：Lomuto 和 Hoare。它们各有适用场景，笔试或讨论时可以顺手写出来展示你对算法的理解。

Lomuto 分区一般把基准值选在区间最右边，用一个慢指针 i 标记“小于基准值的区域的边界”，快指针 j 从头扫到尾。遇到比基准值小的元素，就把它和 i 位置的元素交换。代码长这样：

def partition_lomuto(nums, left, right): pivot = nums[right] i = left for j in range(left, right): if nums[j] < pivot: nums[i], nums[j] = nums[j], nums[i] i += 1 nums[i], nums[right] = nums[right], nums[i] return i

Lomuto 非常好写，逻辑透明，但它在“大量重复元素”的场景下交换次数偏多。Hoare 分区则是经典教科书里最早的一版，基准值通常取中间位置或最左侧，两个指针分别从左和右出发，左边找大于等于基准值的，右边找小于等于基准值的，找到后交换，直到两指针交错。Hoare 的平均交换次数更少，但边界判断更微妙，新手写起来容易在指针越界和死循环之间反复横跳。

我的建议是：平时练习以挖坑法为准，它兼具 Lomuto 的直观和 Hoare 的效率，理解和记忆成本最低。之后再去读 Lomuto，用不用的上另说，至少聊到 partition 变体时不会露怯。

2.3 随机化基准值与三数取中：摆脱最坏情况

快排最大的敌人是有序数组加固定选基准。比如数组已经是升序，再选最左边的元素当基准，每次分区都只会把区间切成 1 和 n-1，递归深度变成 n，时间复杂度退化成 O(n²)。这种情况在工程上不是理论问题，完全有可能发生。

一个简单有效的补救是随机化基准值：在[left, right]范围内随机选一个下标，先把它和nums[left]交换，再继续原来的挖坑流程。随机化之后，遇到最坏情况的概率低到几乎可以忽略，这才是工程里真正使用的快排姿态。

import random def quicksort_random(nums, left, right): if left >= right: return rand_index = random.randint(left, right) nums[left], nums[rand_index] = nums[rand_index], nums[left] pivot = nums[left] i, j = left, right while i < j: while i < j and nums[j] >= pivot: j -= 1 nums[i] = nums[j] while i < j and nums[i] <= pivot: i += 1 nums[j] = nums[i] nums[i] = pivot quicksort_random(nums, left, i - 1) quicksort_random(nums, i + 1, right)

如果不想依赖随机数，也可以用“三数取中”：取区间的左端、右端、中间三个位置的元素，选出中间值作为基准值。这个方法比随机化更稳定，因为它在选基准时直接排除了最大或最小值的极端情况。很多标准库的排序实现里，快速排序部分的 pivot 选择就会用到类似策略。

3. 实操过程：让快排在工程里真正落地

3.1 迭代版快排：不用对递归深度提心吊胆

递归版快排写起来漂亮，但有一个隐藏风险：当数组特别大，而且基准值选得不巧时，递归深度可能达到 n。比如一个倒序数组配合固定选左端为基准，递归深度就是 n，在 Python 里直接触发 RecursionError，在 C 语言栈上也可能爆栈。我在实际处理百万级数据时遇到过这类问题，处理办法是改成显式栈的迭代版本。

思路很简单：既然递归本质是维护一个待处理区间栈，那我们就用一个 list 手工维护左右边界。每次从栈中弹出一个区间，执行同样的 partition，再把切出来的两个子区间压回栈中。

def quicksort_iterative(nums): if not nums: return nums stack = [(0, len(nums) - 1)] while stack: left, right = stack.pop() if left >= right: continue pivot = nums[left] i, j = left, right while i < j: while i < j and nums[j] >= pivot: j -= 1 nums[i] = nums[j] while i < j and nums[i] <= pivot: i += 1 nums[j] = nums[i] nums[i] = pivot stack.append((left, i - 1)) stack.append((i + 1, right)) return nums

这个版本在最坏情况下，栈的最大长度也是 O(n)，但因为是在堆上分配，不会像函数递归那样迅速打爆线程栈。压栈顺序不需要特别讲究，左右子区间谁先处理都行，不影响最终结果。不过我习惯先压左区间再压右区间，这样下一轮会先处理右区间，逻辑上和递归版本的顺序保持一致，调试更方便。

迭代版还有一个额外好处：你可以通过日志观察每个区间的处理顺序，对理解递归过程非常有帮助。如果手头有工具画一下栈的变化，其实就是把递归树里每个节点的处理过程按深度优先顺序走了一遍。

3.2 小数组切换与快排的稳定性问题

快排在工程里落地时，还有一个经典优化：小数组不再继续递归，而是切换成插入排序。原因很实在——快排的递归开销和 partition 操作在数据量很小的时候并不划算，插入排序在 n 小于 10 到 20 时往往更快。很多标准库的实现里都有这个阈值，比如某些实现里设成 16。

这个优化在算法题里通常不需要写出来，但在性能敏感的场景里效果很明显。我一个规模约 20 万的全随机整数测试里，加上小数组切换后，总耗时比纯递归快排肉眼可见地降低，虽然整体复杂度没变，但常数因子更小。

另一个常被问到的点是快排的稳定性。快排是不稳定排序，因为交换操作会把相等的元素相对顺序打乱。比如一个数组里有两条记录，第一条的 key 是 3，第二条的 key 也是 3，排序后两条记录的顺序可能会反过来。所以如果业务上要求稳定排序，应该选归并排序或 TimSort，而不是快排。理解这一点对面试和实际选型都很重要——不是快排不好，而是工具要匹配场景。

另外，快排的 partition 思想本身也能迁移到很多问题上。比如找第 K 大的元素，不用把整个数组排完；求最小的 K 个数，也可以通过分区快速淘汰多余元素。这些都是快排影响面远超排序本身的地方，学的时候多往这方面想一想，比死记代码更有价值。

4. 常见问题与排查技巧实录

4.1 死循环、指针越界与等号处理

我见过最多的快排翻车现场，就是等号处理错误导致的死循环或指针越界。拿挖坑法举例，内层循环必须用>=和<=，如果去掉等号，在数组存在大量重复元素时，两个指针可能一直互相寻找“严格小于/严格大于”的元素，结果谁都找不到，i 和 j 无法正常推进。

还有一种越界情况：右指针从右往左找小时，循环条件里必须先判断i < j，再访问nums[j]。如果颠倒顺序，当所有元素都大于等于基准值时，j 可能一路走到 -1，直接数组越界。这种问题在大小写不同的测试用例里特别容易暴露。

指针交错问题更多出现在 Hoare 分区。Hoare 返回的分界点不是基准值的最终位置，而是两指针交叉的位置，递归处理时对边界非常敏感。我见过有人把 Hoare 的返回值直接套进挖坑法的递归边界里，结果区间重复处理，无限递归。排查方法也不难：在递归入口打印left和right，如果某次区间没有变小，立刻就能定位到是边界写错了。

4.2 性能对比与现场优化清单

如果遇到有人问“快排是不是一定比归并快”，答案是不一定。实际表现取决于数据特征、基准值策略、缓存利用和编程语言实现。下面这个表总结了我常用的对比视角：

维度	快排	归并排序	备注
平均时间复杂度	O(n log n)	O(n log n)	常数因子快排更小
最坏时间复杂度	O(n²)	O(n log n)	快排可优化规避
额外空间	O(log n) 期望	O(n)	归并不能严格原地
稳定性	不稳定	稳定	有稳定需求时选归并
缓存友好度	高	一般	快排局部性好