聊到数据结构里的排序算法快速排序是永远绕不过去的名字。平均时间复杂度 O(n log n)实现代码短到离谱效果却好得惊人所以从教科书到工业级编程框架它几乎无处不在。可我发现一个很有意思的现象很多人看快排觉得“挺简单的”真让自己手写一遍却总是出现递归出不来、数据越界、排序结果不对这类问题。问题通常不出在思想上而出在分区函数的边界处理上。这篇文章我会把快速排序拆开揉碎讲一遍包括分治设计、Lomuto 和 Hoare 两种分区写法、时间复杂度到底怎么推、三路划分和插入排序混合优化以及一些只有实际写代码踩过坑才能总结出来的排查经验。适合正在学数据结构的学生、准备算法面试的开发者以及想在工程代码里用快排思路优化排序逻辑的人。我不打算只贴代码重点是让你理解为什么这么写、边界条件为什么这么处理、遇到异常时该从哪个方向查。1. 快速排序的整体设计与思路拆解1.1 分治三步与“整理书架”的直觉快速排序的思想其实特别生活化。你可以想象自己整理一个书架上顺序混乱的书先随手抽出一本书作为参照把书名首字母比它靠前的书放在左边比它靠后的放在右边。这样处理完一轮之后被抽出来的这本书已经处在它最终应该在的位置因为左边全部小于它、右边全部大于它。接下来只需要对左边那一堆和右边那一堆分别重复同样的操作直到每个区间只剩一本书或者为空。这就是典型的“分治”策略总共三步分解、递归解决、合并。有意思的是快速排序的“合并”几乎是零成本。因为每一轮分区之后基准元素已经固定到了最终位置左右两边也已经泾渭分明不需要像归并排序那样再额外做一次归并操作。也就是说快速排序把工作重心全压在了“分解”这一步骤上也就是分区函数 partition 怎么写得高效、怎么把边界控制好。理解了这一点你就明白为什么网上那么多讲快排的文章会花大量篇幅在 partition 上真正决定快排生死的就是这十几行代码。1.2 为什么工程环境偏爱快排而不是别的排序先看一组排序家族的对比感受一下快排的生态位排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定从表格看快速排序的平均复杂度达到了最优级别空间复杂度又是 O(log n) 级别的递归栈比归并排序 O(n) 的辅助空间省得多。更重要的是快速排序对 CPU 缓存极其友好。它操作的是同一个数组里的连续片段局部性原理让它在现代计算机上有非常低的内存访问开销。归并排序虽然稳定且最坏情况也是 O(n log n)但需要额外的临时数组来合并数据量大时内存开销和拷贝成本都不小。堆排序虽然也是原地排序但它的访问模式是跳跃的缓存不友好常数因子偏大。所以大多数编程语言内置的 sort 底层基本都会采用快排思路再搭配插入排序、堆排序做兜底。可以说快排是“默认情况下最不容易出错的通用排序方案”前提是你把基准选择和边界控制处理好。这也是为什么它既是数据结构课程的常客也是面试手写算法的高频考题。2. 核心细节分析与经典实现2.1 单边扫描分区Lomuto 分区方案先讲讲最容易理解、也最常出现在教科书里的 Lomuto 分区方案。它的思路很直白固定取区间最右边的元素作为基准值然后用一个指针 i 维护“已确认小于基准的区域边界”再用另一个指针 j 从头扫描到基准前一位。def quicksort(arr, lo, hi): if lo hi: return pivot arr[hi] i lo - 1 for j in range(lo, hi): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[hi] arr[hi], arr[i 1] pi i 1 quicksort(arr, lo, pi - 1) quicksort(arr, pi 1, hi)这段代码里最关键的点在循环的不变量每轮循环结束时区间 [lo..i] 内的元素都严格小于 pivot区间 [i1..j-1] 内的元素都大于等于 pivot区间 [j..hi] 是还没扫描的区域。当 j 从 lo 扫到 hi-1 时遇到一个小值就把它换到前面去i 也跟着往后挪。扫描结束后所有小于 pivot 的值都堆在左边剩下的都大于等于 pivot然后把基准值 arr[hi] 和 arr[i1] 交换基准就回到了它应该在的“分界线”位置。我建议你盯着递归那两行看quicksort(arr, lo, pi - 1)和quicksort(arr, pi 1, hi)。因为基准已经放到了最终位置 pi 上所以递归区间必须排除 pi否则基准元素就会无限参与排序导致递归无法收敛。这是新手最容易写错的地方。2.2 双边扫描分区Hoare 分区方案Lomuto 分区虽然好写但它的交换次数偏多而且当数组中出现大量重复元素时容易退化。另一种更快速、也是很多工业实现底层的方案是 Tony Hoare 最早提出的双边扫描分区一般叫 Hoare partition。def partition(arr, lo, hi): pivot arr[(lo hi) // 2] i lo - 1 j hi 1 while True: i 1 while arr[i] pivot: i 1 j - 1 while arr[j] pivot: j - 1 if i j: return j arr[i], arr[j] arr[j], arr[i] def quicksort(arr, lo, hi): if lo hi: return p partition(arr, lo, hi) quicksort(arr, lo, p) quicksort(arr, p 1, hi)这种写法和 Lomuto 有几个明显区别。第一基准值不一定选在端点可以选中间元素所以不存在“最后再交换基准”这一步骤分区结束后基准可能被交换到任意位置。第二返回的下标 p 并不等于基准位置它只是一个“中间切割点”满足左边区间 [lo..p] 内的元素都不大于右边区间 [p1..hi] 内的元素所以递归时左区间包含 p右区间从 p1 开始。新手最容易在这里犯迷糊为什么 Lomuto 递归是 [lo, pi-1] 和 [pi1, hi]而 Hoare 递归却是 [lo, p] 和 [p1, hi]原因就是 Lomuto 返回的 pi 必然是基准的最终位置而 Hoare 返回的 p 只是左右边界的切分点基准已经被混入了某个区间内部。写之前先想清楚自己用的是哪种分区方案不然递归区间一写错程序就会陷入死循环或者漏排元素。2.3 为什么“先动右边”不是玄学在写双边扫描时有一个操作顺序上的细节值得多说一句内层循环必须先让 j 从右往左找不大于 pivot 的元素再让 i 从左往右找不小于 pivot 的元素而不是反过来。这个顺序在后续元素和基准值交换时很重要。当你从左往右找第一个大于等于 pivot 的元素、从右往左找第一个小于等于 pivot 的元素两个指针相遇或者交错时你希望 i 和 j 交错点表示“右边保证是大于基准的区间”。如果反过来写最后切分的位置会多一个大于基准的元素在左边递归切割时就会出错还会导致排序不完全。这不是什么神秘规则纯粹是循环不变量决定的建议直接记住这个默认写法等理解透了再考虑改顺序的事。3. 复杂度分析与基准选择策略3.1 平均和最坏情况到底怎么算快速排序的时间复杂度完全取决于分区是否均衡。最理想的情况是每次分区都把数组一分为二递归深度只有 log n 层每层扫描的元素总数大约是 n所以总的比较次数是 n log n 这个量级。最不理想的情况是每次分区都只分割出一个元素比如数组本身已经有序而基准值又恰好选在最边缘。这时候递推关系变成 T(n) T(n-1) O(n)把每一层的 O(n) 扫描累加就是 n (n-1) (n-2) ... 1大约等于 n²/2复杂度自然退化成 O(n²)。平均情况的分析要稍微复杂一点。假设递归处理的是长度为 n 的区间基准值最终落在任意位置的概率相等那么递推式可以写成 T(n) (1/n) * Σ_{k0}^{n-1}(T(k) T(n-k-1)) O(n)。这个方程解出来是 T(n) O(n log n)。我见过很多初学者在这里纠结——为什么要记公式其实更重要的是形成直觉只要基准值不是总落在极端位置哪怕每次分区只是三七开递归深度也只是 log 级别的常数倍整体复杂度依然是 O(n log n)。这就是为什么随机化基准能救活快排的原因它把“总是倒霉”的概率降到极低但不改变“偶尔倒霉”的最坏可能。空间复杂度方面很多人以为快排是 O(1) 空间其实不是。递归调用需要压栈理想情况下栈深约 log n最坏情况下栈深达到 n所以空间复杂度是 O(log n)但在极端退化场景下会膨胀到 O(n)。这就直接关联到后面要讲的递归栈溢出问题。3.2 基准选择从固定值到随机化基准选择直接决定快排的生死。朴素的实现总是取 arr[hi] 作为基准这在随机数据上没毛病但在特定数据分布下会触发最坏情况。我整理了一个对照表格基准策略实现思路优点风险固定取端点直接取 arr[lo] 或 arr[hi]实现简单、无额外计算有序或逆序数据退化为 O(n²)随机选取随机下标做基准并交换到端点概率上避免最坏情况需要随机函数结果不稳定无法复现三数取中取 lo、mid、hi 三个位置的中位数对有序数据友好接近最优划分实现稍复杂仍需随机辅助中位数候选采样取若干样本的中位数几乎不会退化采样成本高工程上较少直接用我在实际代码里最推荐的是“三数取中 随机下标”结合。先随机选三个位置再取它们的中值作为 pivot效果上是两头下注随机化保证了对抗恶意数据的鲁棒性三数取中保证了有序数据也能分出均衡的两半。实现时有个小技巧先把中位数交换到 arr[hi]然后继续沿用 Lomuto 分区的写法改动量很小收益却很大。很多教科书代码里写的“快速排序对有序数组退化为冒泡”的说法本质就是基准策略没做好不是快排本身救不了。4. 工程实战中的快速排序优化4.1 小数组区间直接切到插入排序递归本身是有成本的。函数调用要压栈、要跳转当递归区间越来越小比如只剩 16 个元素时递归开销甚至可能超过排序本身的开销。而插入排序在元素个数很少时表现极好因为它的常数因子小对近乎有序的小数组更是友好。工程上的标准做法是设置一个阈值常见是 10 到 20 之间当待排序区间长度小于等于阈值时不再继续递归调用快排而是直接对该小区间执行插入排序。代码很简单def quicksort_opt(arr, lo, hi): if hi - lo 16: insertion_sort(arr, lo, hi 1) return pivot_pos partition(arr, lo, hi) quicksort_opt(arr, lo, pivot_pos - 1) quicksort_opt(arr, pivot_pos 1, hi)这个优化看起来很不起眼实测效果却非常明显。我试过用 Python 排序 100 万元素加上小区间插入排序后整体耗时能下降百分之二三十因为递归层数少了函数调用开销被大幅削减。如果所在语言对递归优化得好阈值可以稍微小一些但不能不设。具体阈值取 16 还是 20对性能影响不大取一个范围内的固定值就行真没必要强迫症似的来回调。4.2 三路划分解决重复数据的性能雪崩另一个工程里非常常见的坑是重复元素过多。想想看如果数组里有大量元素等于基准值在 Lomuto 分区中等于基准的值会被扔到“大于等于”区间里导致右区间依然很大极端情况下所有元素都相等每次分区只能剔除一个基准元素复杂度退化成 O(n²)。这就不是有序数组的锅了而是重复数据的锅。三路划分three-way partition的目标是把数组分成三块小于基准、等于基准、大于基准。等于基准的元素一次性就位下一轮递归完全不用碰它们。对于全部相等的数组三路划分只需要扫描一遍就能完成排序时间复杂度降为 O(n)。def quicksort3(arr, lo, hi): if lo hi: return lt, i, gt lo, lo, hi pivot arr[(lo hi) // 2] 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 quicksort3(arr, lo, lt - 1) quicksort3(arr, gt 1, hi)这个写法的核心循环不变量是区间 [lo..lt-1] 全部小于 pivot[lt..gt] 全部等于 pivot[gt1..hi] 全部大于 pivot[i..gt] 是待处理区域。每次循环分三种情况小于基准就把它交换到左边并让 lt 和 i 都前进大于基准就把它交换到右边并让 gt 后退此时 i 不前进因为交换过来的元素还没被检查过等于基准就只管 i 前进。最后递归只处理左右两侧的“小于”和“大于”区间。这段代码如果第一次看觉得绕建议自己在纸上画一个只有 10 个元素的数组手动跑一遍循环很快就会理解为什么 i 有时不前进。4.3 递归转迭代与显式栈面试和实际项目中都可能会遇到递归深度过大的问题。当数据规模达到几十万、且最坏情况下递归深度接近 n程序就可能爆栈。这时候有两种思路一是用显式栈模拟递归把待排序区间压入栈中循环弹出处理二是只递归短区间把长区间留在循环里继续分割也就是尾递归优化思路。显式栈版本的快排就像二叉树的非递归遍历核心是用一个栈保存 (lo, hi) 区间def quicksort_iter(arr): stack [(0, len(arr) - 1)] while stack: lo, hi stack.pop() if lo hi: continue p partition(arr, lo, hi) if (p - lo) (hi - p): stack.append((p 1, hi)) stack.append((lo, p)) else: stack.append((lo, p)) stack.append((p 1, hi))注意这里故意把较长的区间先压栈较短的区间后压栈这样栈的大小能保持在 log n 级别相当于用代码把递归深度控制住。理论上讲快排不是严格意义上的尾递归但通过“只递归小区间、循环处理大区间”的写法可以把最坏情况下的栈深度从 O(n) 压到 O(log n)。如果你在工程里遇到排序爆栈不用急着重写整个算法先加一层显式栈或随机基准往往就能解决。5. 常见问题排查与调试记录5.1 边界条件引发的死循环和越界我调过不少次快排印象最深的问题几乎都出在分区函数的内层循环缺少边界检查。比如这段错误写法while arr[j] pivot: j - 1如果 pivot 恰好是当前区间里的最小值j 会一路往前冲直到越出数组下标轻则访问异常重则死循环。正确写法里内层循环必须加上 i j 或者 j lo 这类边界条件。尤其是 Hoare 分区两个指针相向移动很容易一不留神就越界。排查这类问题我有一个习惯性思路一旦程序表现是“卡住不动”或者“数组下标越界”就单独打印每轮 partition 之后的 lo、hi、pivot 和返回下标 p把递归过程可视化问题基本一眼就能定位。另一个典型错误是递归区间包含了基准元素本身。上面 2.1 节强调过 Lomuto 的递归区间要排除 pi。如果写成了quicksort(arr, lo, pi)和quicksort(arr, pi, hi)基准元素会因为反复参与排序而让区间永远不会缩小最终导致栈溢出或死循环。这种错不太容易通过一轮数据测出来可能数据少的时候侥幸通过数据一多就崩溃特别坑人。5.2 有序数组与递归栈溢出还有一个高频问题是递归深度爆掉。现象很典型程序排序一个已经有序的大数组跑着跑着就报栈溢出错误。原因也很透明固定取端点基准时有序数组每次分区只会分割出一个元素递归深度正好等于 n。在一个递归深度限制只有几千的环境里给几十万元素排序就足够炸掉栈。解决思路不外乎三个层次。第一层优化基准选择用随机化或者三数取中让有序数组也能均衡分区。第二层引入小数组插入排序和显式栈减少递归深度。第三层如果数据规模和环境限制实在苛刻就换用堆排序或归并排序不要和快排死磕。事实上很多成熟语言的内置 sort 之所以不直接用纯快排也是因为需要在各种极端数据分布下保证不爆栈、不退化为 O(n²)。它们往往会混合使用快排和堆排序检测到递归深度过深就果断切换到堆排序。5.3 重复元素引发的性能抖动如果你遇到的现象不是崩溃而是“排序时间从毫秒级突然涨到秒级”那先别怀疑快排本身先统计一下数据里重复值的比例。很多排序性能问题都是隐藏的数据分布惹的祸。我处理过一起线上任务对一批用户标识做去重排序数据里有大量重复值普通快排跑得比预期慢了几十倍改成三路划分之后耗时立刻降回正常范围。原因就是重复元素让分区严重失衡等值元素堆积在“大于等于基准”的一侧每次递归只能削减极少一部分区间。排查这种性能抖动最好提前准备一组测试数据集覆盖五种典型情况随机数据、有序数据、逆序数据、全部相同数据、只有少数几种不同取值的数据。用相同基准策略分别跑一遍看耗时变化。如果“全部相同”和“少量唯一值”这两类数据明显超时基本就是分区方案没有处理等值元素的意识三路划分就是最直接的解药。5.4 快速排序的稳定性和使用边界还有一个经常被问到的点快排不稳定。比如按学号排序后想再按班级排序希望相同班级的学生保持学号顺序快排做不到因为交换操作可能打乱相等元素的原始相对顺序。如果你需要稳定性应该选择归并排序或者插入排序。这不是缺陷而是算法特性提前知道就能少踩一些“结果明明对但就是不符合需求”的坑。另外快排也不是在任何场景都是最优解。链表排序就不太适合因为链表没有随机访问能力快排需要频繁访问任意位置的基准值做起来很别扭归并排序天然适合链表数据量极大、内存放不下时外部排序基本都是归并的变体待排序的小规模数据插入排序反而最实用。所以我的经验是不要神化快排但也要意识到在大多数“数据在内存中、规模适中、需要通用排序”的典型场景里快排及其优化变体就是最均衡的选择。6. 我在实际使用中的几点体会快速排序最迷人的地方在于它表面只有十几行代码内里却塞满了工程权衡。从基础的分区思想到随机化、三数取中、插入排序混合、三路划分、显式栈每一步优化都对应着一个真实世界里会遇到的问题。如果你还在学数据结构可以先把 Lomuto 分区版本写到纯熟再一步步加上优化如果你已经在写工程代码我建议至少把三路划分和随机基准这一个组合背下来它能在绝大多数数据分布下交出体面的答卷。我自己调试快排时反复踩过一些坑最后形成的习惯是每次写 partition 之前先明确它返回的下标到底代表什么再决定递归区间怎么写每次做大规模排序前先跑一遍重复数据和有序数据确认不会出现性能雪崩一旦出现栈溢出先检查基准策略再考虑换成显式栈。曾经有个项目里我用普通快排处理一组几乎全等的数据耗时几十秒后面换成三路划分直接降到几百毫秒。从那以后我写快排默认就带三路划分反正代码量没增加多少收益却非常可观。如果你是自己练习还可以试着把 Lognormal、少量唯一值、完全有序这些数据都喂给你的排序函数看它是不是还能保持稳定。这一套测试流程比单纯背诵代码要管用得多。快速排序不是那种“看懂了就会了”的算法它是那种“写错了才会真正学会”的算法。多写几遍、多翻几次车你对它的理解会比任何文档都深。