有人觉得快速排序是八股文里的“背背就行”，有人一面试就手抖，还有人真到生产环境才发现：明明书上说平均 O(n log n)，怎么线上一个有序数组直接卡成 O(n²)？快速排序之所以稳坐“十大排序算法”前三，不只是因为它快，而是它背后的分治思想几乎贯穿了所有高级数据结构和系统设计。这篇文章不讲虚的，直接拆开快排的每一层：从分治原理到分区实现，从退化陷阱到三路划分，从手写代码到工程源码里的真实快排。

我尽量按一个“被线上问题反复教育过”的程序员口吻来写，保证每个结论都有实操依据，不是教科书复读。

1. 快排的核心思路：分治不玄乎，关键是“比大小挪位置”

先用一句大白话概括快速排序：随便挑一个元素当“基准”，把比它小的放左边，比它大的放右边，然后左右两边各自重复这个过程，直到所有区间都只剩一个元素。这个“重复”就是递归，而“挑基准、分两边”就是分治里的“治”。

很多人背快排时只背了三句话（选基准、分区、递归），但面试官深挖一层就露馅：为什么这个流程能保证最终有序？答案在于每一次分区都做了一件无法撤销的事情——把基准元素放到了它最终该待的位置。左边都小于它，右边都大于它，那无论后续怎么折腾左右子区间，这个基准都不会再挪地方了。这叫“分治的减治性”，每次操作至少把一个元素固定到位，递归下去就不会死循环。

1.1 分治递归的三个基本要素

经典快排的递归结构长这样（伪代码视角）：

1. 从区间[low, high]中选一个基准值pivot；
2. 通过分区函数，让pivot落到它排序后的正确位置p，且保证[low, p-1]都小于等于pivot，[p+1, high]都大于等于pivot；
3. 对[low, p-1]和[p+1, high]递归执行同样的操作；
4. 递归出口：区间长度小于等于 1。

这里有个初学者最容易忽略的点：你在写递归的时候，需要关心的是“出口”和“状态不变量”，而不是“一步步推演结果”。快排的出口就是区间里只剩一个元素或空区间，因为一个元素天然有序，不用再排。状态不变量就是“每次分区后，基准的最终位置确定”，只要这个不变量不被破坏，最终一定能排完，而且不需要像插入排序那样再额外做一次全局“收尾”。

1.2 时间复杂度为什么平均是 O(n log n)

把一次分区看作“把数组中每个元素跟基准比较一遍”，所以单次分区的开销是O(n)。关键在于分了几层：如果每次基准都能把数组大致对半分，那递推式就是T(n) = 2 * T(n/2) + O(n)，解出来就是著名的O(n log n)。

如果每次基准都恰好是当前区间的最大值或最小值，一边区间是空的，另一边是n-1个元素，递推式变成T(n) = T(n-1) + O(n)，这个往下一路累加就是O(n²)。快排的性能上限和下限都被基准决定，不是被数组大小决定。这就是为什么后面会花大篇幅讲“基准选择”——它才是真正决定快排能不能快起来的命门。

空间复杂度也一样被递归深度支配。理想情况下递归深度log n，也就是栈空间O(log n)；极端退化时递归深度达到n，栈空间直接变成O(n)，小数组还好，百万级数据直接爆栈给你看。

2. 两种主流分区实现：教科书 vs 工程源码的分水岭

网上讲快排的代码五花八门，但归根结底就两种分区算法：Lomuto 分区和Hoare 分区。前者是几乎所有教材最爱讲的版本，因为好写、好理解；后者是 C 语言标准库qsort的底层思路，也是很多面试官心里默认的“标准答案”。两者差距不是一点点。

2.1 Lomuto 分区：最易读但也最容易踩坑的版本

Lomuto 分区的思路是：选定最后一个元素（或任意元素）作为基准，用一个慢指针i维护“小于等于基准的边界”，另一个快指针j遍历数组，遇到比基准小的就把它换到i+1位置。

def lomuto_partition(arr, low, high): pivot = arr[high] # 直接取最后一个元素当基准 i = low - 1 # i 是“小于区”的右边界 for j in range(low, high): if arr[j] < pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1

这个版本的优势就一个：不容易写错。你只需要记住i从low-1开始，遇到小于基准的，i先加一再交换。最后把基准换到i+1的位置，返回。

但它有个隐藏问题：交换次数偏多。每碰到一个比基准小的元素就要交换一次，即使两个元素原本已经在正确区域，也可能被白白交换。更重要的是，如果数组里有大量重复元素，Lomuto 分区会退化得很严重：所有等于基准的元素全部被分到同一边，分区的平衡性瞬间被打破。经典场景就是全等数组——每一趟只排好一个元素，时间复杂度稳稳定在O(n²)。

2.2 Hoare 分区：双指针扫描，交换次数更少也更经典

Tony Hoare 论文里的原始版本其实不是很多教材写的那样，它用了两个指针分别从左、从右往中间扫描：

def hoare_partition(arr, low, high): pivot = arr[(low + high) // 2] # 取中间元素作基准 i, j = low, high while True: while arr[i] < pivot: i += 1 while arr[j] > pivot: j -= 1 if i >= j: return j arr[i], arr[j] = arr[j], arr[i] i += 1 j -= 1

核心逻辑是：左指针往右找第一个大于等于基准的，右指针往左找第一个小于等于基准的，找到就交换。注意这里的边界条件：一旦i >= j就停止，返回j而不是i+1。很多人在这一步翻车，因为怕写错，干脆把while arr[i] < pivot写成<=，结果两个指针直接走进死循环——当数组里有两个相等的基准值时，交换完索引没推进，i和j永远不交叉，然后就卡死在while True里。

2.3 我手头项目的选择逻辑

我在工作中手写排序的场景其实不多，绝大多数时候直接调标准库。但有一类情况必须手写：对一组结构体按多字段排序，且要求特定字段优先级。这时候我会选 Hoare 分区，理由量化一下：

特别强调：Hoare 分区虽然代码更绕，但它天然把等于基准的元素分到左右两侧，面对大量重复数据时，反而能维持平衡。这也是它被 C 标准库和许多工业级排序采用的根本原因。如果你在面试现场，我建议写 Hoare——面试官看到这个版本，就知道你不是只会背代码的，是真理解指针怎么收敛的。

3. 最坏情况、退化和基准选择的补救：三数取中为什么成默认

有句话我特别认同：快排最怕的不是乱数据，而是看着特别规律、实际上对基准极不友好的一类数据。固定取第一个元素当基准时，一个已经有序的数组就是最坏输入。每趟分区只挑出最前面那一个元素，左区间为空，右区间长度n-1，递归深度直接拉满。

3.1 退化的两个经典来源

• 已有序（或逆序）数组：基准取第一个 / 最后一个时，每次去掉一个极端值，卡在 O(n²)。
• 大量重复元素：固定取最后一个元素时，所有等于基准的都被堆在右侧，左右严重不平衡，也是 O(n²)。

网上很多教程会轻描淡写一句“最坏情况是 O(n²)”，但我在真实现场见过后果：一批 50 万行的日志数据，按时间戳字符串排序，因为恰好是倒序，归并排序 0.3 秒跑完，手写快排跑了 11 秒。原因就是这个退化，不是机器慢。

3.2 三数取中：花极小代价遏制最坏情况

三数取中（median-of-three）的思路是：从区间的头部、中间、尾部各取一个数，选出其中值居中的那个当基准。比如数组[3, 7, 1, 9, 5]，头部 3、中间 1、尾部 5，中值是 3，那基准就拿 3。这样处理的最直接效果是：

• 对付“基本有序”的数组：头部和尾部正好是一个小值一个大值，中值不容易取到最极端值；
• 对付“逆序”数组：效果同理，基准大概率落在中间区域；
• 代价只有三次比较和少量交换，对于大数组可以忽略。

代码实现也很简单，在分区函数开头做一次“三数排序并让中值落在某个约定位置”即可。实际操作时，我习惯让中值落到high-1位置（如果后续用 Lomuto）或直接交换到区间中间（Hoare），避免额外判断。

def median_of_three(arr, low, high): mid = (low + high) // 2 if arr[low] > arr[mid]: arr[low], arr[mid] = arr[mid], arr[low] if arr[low] > arr[high]: arr[low], arr[high] = arr[high], arr[low] if arr[mid] > arr[high]: arr[mid], arr[high] = arr[high], arr[mid] # 此刻 arr[mid] 是中值 return arr[mid]

3.3 随机化基准：救急可以，但别当成万能药

另一条路是随机选基准。理论上，随机化能让任何输入的期望复杂度变成O(n log n)，因为最坏情况被转化为一个概率极低的事件。工程上我很少单纯依赖随机化，原因有两个：

• 随机数生成有开销，在几十万以下的小数组上无所谓，在千万级别时，rand() 的调用成本会占 3%~5% 的整体耗时；
• 线上环境很难保证随机源的质量，极端情况下随机分布不均匀，依然退化。

所以更稳妥的组合拳是：三数取中 + 小数组切插入排序。前者把退化概率压到极低，后者干脆不让快排处理那些已经“近乎有序”的小尾巴。很多知名库就是这么干的。

4. 递归深度、爆栈风险和尾递归优化

快排的递归栈深度等同于分区递归的深度。理想是log n，退化会到n。对 10 万级以下的数据，即使退化也未必能引爆栈；到了千万级甚至亿级，递归一深，栈直接溢出。而且这个栈不是你分析代码时“哦有个递归”那么简单，它在系统里是真的占用线程栈内存的，默认 8MB 左右，一个深度十万的递归轻轻松松击穿。

4.1 尾递归优化：短代码里的大智慧

尾递归优化听起来高级，它的思想其实一句能讲完：哪边区间长，就先把短的那边留到本地下一轮处理，长的那边用迭代循环继续跑，而不是用递归调用。因为递归栈深度由“最长递归链路”决定，我们主动把“短边”先递归掉，让“长边”留在栈帧里，栈深度就能被严格压到O(log n)。

标准写法长这样：

def quick_sort_tail(arr, low, high): while low < high: p = partition(arr, low, high) if p - low < high - p: quick_sort_tail(arr, low, p - 1) low = p + 1 else: quick_sort_tail(arr, p + 1, high) high = p - 1

哪边短先递归哪边，长的部分用while循环继续。这样一来，递归深度最多等于短的链路深度，理论最长log n。这个技巧在生产级快排里几乎是标配，C 标准库qsort和许多 JVM 语言标准库都用了类似手段。

4.2 什么时候你不该用递归快排

有两类场景，我会明确放弃递归：

• 太大且分布极不规律的数组：即便用了三数取中和平滑基准，最坏概率确实压到了千万分之一，但线上偶发一次就是事故。我会直接把数组交给标准库的归并排序或内置排序，它们通常针对大规模数据做了更周密的内存管理；
• 内存受限的嵌入式环境：递归栈本来就是稀缺资源，用迭代版本或换归并排序更稳妥。

另外提醒一个容易忽略的细节：分区函数返回的 p 可能等于 low 或 high，如果处理不当，quick_sort_tail会陷入死循环。我踩过这个坑，原因是分区返回的位置恰好是区间端点，递归调用(low, p-1)时出现了low > high的空区间，而while low < high没退出，也没有推进low，直接卡死。解决方法是把p-1、p+1的边界判断写清楚，并在递归前确保区间长度严格缩减。

5. 稳定性误区、重复元素处理和“三路快排”的必要性

很多初学排序的人会问一个很关键的问题：快排是稳定的吗？答案明确：不是。原因在于分区时的交换操作是无差别位置互换，两个相同键值的记录可能在分区过程中相对顺序被颠倒。如果你排序的对象是简单数值，稳定性无关痛痒；如果排序对象是结构体且你希望保持原始顺序中的稳定性，快排直接出局，只能用归并。

5.1 重复元素才是工业级快排的最大考验

经典快排在“全部元素都相等”的输入上表现极其糟糕：Lomuto 分区固定选最后一个，在比较数组时会发现所有其他元素都不小于基准，分区后右区间还是整个数组，等于每一趟只处理一个元素，复杂度O(n²)。

Hoare 分区面对全等数组其实表现得不错——左右指针因为基准相等会快速交叉，分区结果几乎等分。但如果用普通双指针版本再碰到“几乎全等、偶尔几个异类”的数组，效果也不稳定。这时候就得请出三路快排。

5.2 三路快排：把“等于基准”单独收拢

三路快排的思路是用三个区域维护：小于基准区、等于基准区、大于基准区。一趟分区之后，等于基准的中间段直接固定不动，只递归左右两边。它对付重复元素多的输入，复杂度直接降到O(n log n)，几乎不再退化。

def quick_sort_3way(arr, low, high): if low >= high: return lt, i, gt = low, low, high pivot = arr[low] while i <= gt: if arr[i] < pivot: arr[lt], arr[i] = arr[i], arr[lt] lt += 1 i += 1 elif arr[i] > pivot: arr[i], arr[gt] = arr[gt], arr[i] gt -= 1 else: i += 1 quick_sort_3way(arr, low, lt - 1) quick_sort_3way(arr, gt + 1, high)

画个重点：arr[i] > pivot时，i不前进，因为换过来的arr[gt]还没跟基准比较过；只有< pivot或== pivot时i才加一。这个细节无数人写错过，一错就是死循环或漏排。三路快排的经典应用场景是：数据库里按重复率极高的字段排序、对大量重复枚举值做分组。工程上很多标准排序在面对大量重复数据时也会自动切换类似策略。

5.3 双轴快排的一点补充

Java 标准库的Arrays.sort()对基本类型走的是双轴快排（Dual-Pivot QuickSort），思路是选两个基准，把数组分成三段区间，而不是两段。双轴快排对比三路快排的优势在于：两个基准能把区间切得更细，平均分区后每个子区间更小，常数开销更低；但代码复杂度直线上升。我个人观点是：除非你真的在做语言标准库，否则不必手写双轴快排，三路快排已经能覆盖绝大多数重复数据场景。

6. 从手写快排到工程级快排：实测数据、代码细节和调优心得

聊了这么多原理，最后分享一点“真刀真枪”的实践数据和个人调优经验，让大家感受一下从算法到工程的差距。

6.1 一个有效但低调的优化：小数组切插入排序

快排递归到末尾时，区间里只剩十几个元素，再用分治反而浪费函数调用。所以工程实现几乎都会加一个“阈值判断”：区间长度小于CUTOFF（常见取 7~20），不再递归，改用插入排序。原因很简单：插入排序在小规模近乎有序数组上的常数极小，而且没有递归栈开销。这招在 C 标准库qsort、很多 JAVA 标准库排序、Go 的排序实现里都在用。

我用一组 200 万元素的随机整数数组做过对比：

差距看着不算夸张，但放到千万级、亿级数据源上，每一层省下来的常数都会被放大。

6.2 手写快排时最容易写的 3 个 Bug

这三个 Bug 我都在真实代码或别人提交的 code review 里见过，写出来让大家避雷：

1. 分区循环里数组越界：Hoare 双指针扫描时，如果没有给内层 while 加边界判断while i < j and arr[i] < pivot，i可能一路扫出界。虽然语言层面可能不报错，但拿到的是脏数据。
2. 递归边界不一致：分区返回j（Hoare 风格）后，递归左区间用了(low, p)，右区间用了(p+1, high)，结果元素p被同时处理或漏处理，导致排序结果偶尔错乱。要牢记左闭右开区间里 Hoare 的返回位置和 Lomuto 的返回位置语义不同。
3. 随机基准拿了没换位置：选了pivot = arr[random_idx]但没把它换到端点，然后分区时又以端点元素为基准，等于随机了个寂寞，退化问题原封不动。

6.3 性能测试的复盘思路

我测性能的习惯是：构造退化数据比构造随机数据更重要。测试集至少包含四类：

• 完全乱序：模拟日常数据；
• 已有序 / 逆序数组：验证基准策略是否扛得住最坏情况；
• 大量重复元素数组（比如全 1、少量 2）：验证分区平衡性；
• 小数组（几十个元素）：验证 CUTOFF 是否合理。

每一类都跑多次，记录中位数而不是平均值，避免系统抖动干扰。快排这种指数量级的性能差异，用中位数比平均值更能暴露退化问题。

6.4 工程里快排不是万能的

最后说个方向性问题。快排在内存排序里很快，但一旦涉及外部排序（数据量超过内存），比如对几十 GB 日志排序，快排就不好用了，得用归并排序的思路做外部归并。另外，对于链表排序，快排的随机访问特性直接失效；对于要求稳定的场景，快排不行。选排序算法的顺序应该是：标准库内置排序优先，数据特征匹配时自定义排序，最后才是手写快排。明白它的原理，是用来理解系统行为、排查性能瓶颈、面试写白板的，而不是让你在业务代码里从零再造轮子。

我自己的体会：快排是少有的“你越深入，越发现自己之前根本没掌握”的算法。从能默写代码，到理解基准选择的概率论本质，再到五路分区的工程实现细节，每一步都在刷新对“分治”这个词的理解。如果你准备面试，不要只背代码，多想想为什么有序数组是快排的死穴，为什么工程实现都在加各种防退化机制——这些思考才是真正值钱的东西。