快速排序这四个字几乎所有写程序的人都听过。它在算法教材里的地位无需多言面试中更是高频手撕题而我在实际工程和面试准备里也确实把它当作最值得研究的排序算法。原因很简单平均 O(n log n) 的时间复杂度、原地排序、优雅的分治思路让它用很少的代码解决了排序这个难题。这篇文章会从一趟划分的本质讲起给出我在讲算法时常用的几个 Python 实现版本再附上我踩过的边界条件坑、递归爆栈、重复元素退化等实战记录。无论你是刚接触算法的 Python 初学者还是已经会用sorted()但想真正理解底层原理的开发者都可以把这篇当作一份能直接上手的快速排序笔记。先说说我这几年写快速排序的感受它最大的“迷惑性”在于代码短长得好像很容易背下来。但只要你把某一个边界条件记错或者不理解枢轴在一趟划分后已经回到正确位置这件事就会出现死循环、排序结果错误、甚至递归爆栈。所以这篇文章不打算只贴一份能跑的代码我会一步步拆解为什么要这么写以及在真实调试中遇到的那些典型问题。1. 快速排序的核心思路分治、划分与枢轴1.1 一趟划分到底在做什么快速排序的核心不是“排序”而是“划分”。每一趟划分会从当前区间里选一个元素作为枢轴pivot然后把剩下元素分成两拨比枢轴小的放左边比枢轴大的放右边。等这一趟结束枢轴本身已经位于它最终应该在的位置上因为左侧所有元素都比它小右侧所有元素都比它大。接下来只要递归处理枢轴左右两个子区间整个数组就逐渐有序。你可以把它类比成整理一摞试卷先随便抽出一张当作基准把分数比它低的扔左边比它高的扔右边然后对每一摞重复同样的操作。关键点是那张基准试卷一旦分好就再也不用参与后续整理了。快速排序正是用这个“每趟至少让一个元素归位”的思路逐步缩短排序规模最终完成全部排序。递归终止条件也很容易理解当子区间长度为 0 或者 1 时区间本身已经有序不需要再递归。这个看起来简单的条件却是后续最容易出错的地方后面我会专门展开讲。1.2 枢轴选择的三种策略枢轴选得好不好直接影响快速排序会不会退化。工作中常见的策略有三种固定选最右边元素、随机选元素、三数取中。固定选最右或最左是教材里最常用的写法因为它实现最简单Lomuto 划分的代码写成pivot arr[right]即可。缺点是它对输入分布很敏感如果数组本身就是有序或者逆序每一趟划分都极不均匀效率直接从 O(n log n) 掉到 O(n²)。随机选枢轴是我在绝大多数手写场景下的首选。用random.randint(left, right)随机挑一个位置然后与最右元素交换代码只多两行却能把“最坏输入”变成概率极低的小概率事件。即使有人故意构造有序序列你也很难每次都选到最差的枢轴。三数取中是另一个经典的优化思路取left、mid、right三个位置的值选出中间大小的那个当枢轴。它对接近有序的数组特别有效能把大部分退化情况提前消解掉。实现上稍微复杂一点但理解原理后也很容易写。三种策略对比如下策略核心思路优点缺点固定端点直接取最左或最右元素代码最简单有序/逆序序列会严重退化随机选取随机挑一个位置避免恶意输入导致的退化需要产生随机数有少量开销三数取中取左、中、右三个元素的中位数对有序序列效果好且稳定实现略复杂样本小时收益不明显1.3 期望 O(n log n) 是怎么来的很多人知道快速排序平均是 O(n log n)但说不清楚为什么。其实很简单每一趟划分需要扫描当前区间把所有元素和枢轴比较一遍所以单趟开销是 O(n)。如果枢轴每次都落在区间中位数附近那么递归树高度大约是 log n 层每层近似处理 n 个元素乘起来就是 O(n log n)。最坏情况发生在每一趟划分都“极度偏科”的时候。比如固定取最右元素而数组已经升序排列那么每次划分都只有一个元素归位剩下的区间只比原来少一个元素递归树从一棵平衡二叉树退化成一条链表高度变成 n总时间复杂度就是 O(n²)。这也能解释为什么很多面试官在问快排时会追问一句“最坏情况是什么怎么解决”。答案就是随机化枢轴、三数取中或者在三路划分中直接把相等元素归档。2. Python 实现从教学版本到工程版本2.1 最直观的“生成新列表”写法初学快速排序时最容易理解的写法不是原地交换而是每次递归生成新的列表def quick_sort_simple(arr): if len(arr) 1: return arr pivot arr[0] left [x for x in arr[1:] if x pivot] right [x for x in arr[1:] if x pivot] return quick_sort_simple(left) [pivot] quick_sort_simple(right)这个版本把“小的放左边大的放右边”表达得非常直白用来理解快速排序的分治思路非常合适。你甚至可以把它当作面试或教学里的“思路演示版”因为它几乎不会写错边界条件。但它的缺点也很明显每一层递归都会创建新的列表数据量大时额外内存开销很可观。更关键的是它不符合快速排序“原地排序”的核心特性面试中如果只写这个版本很容易被追问空间复杂度。所以它可以作为理解工具但不适合当作工程实现或最终考核答案。2.2 Lomuto 单边划分最容易背下来的原地写法Lomuto 划分是面试中最常见的手写方案逻辑清晰代码短出错率相对低。我一般推荐先把这一版写熟练def quicksort_lomuto(arr, left, right): if left right: return pivot arr[right] i left for j in range(left, right): if arr[j] pivot: arr[i], arr[j] arr[j], arr[i] i 1 arr[i], arr[right] arr[right], arr[i] quicksort_lomuto(arr, left, i - 1) quicksort_lomuto(arr, i 1, right)这里关键变量是i和j。j用来从左到右扫描待处理区间i则指向“当前所有小于枢轴元素”的下一个插入位置。每发现一个元素小于枢轴就把它和i位置的元素交换然后i前进一位。扫描结束后把枢轴从最右侧换到i位置一趟划分完成。写这版最容易踩的坑有三个第一终止条件写成left right实际应该是left right因为递归调用可能传入空区间第二递归时把枢轴下标i也包含进去比如写成quicksort_lomuto(arr, left, i)会让枢轴反复参与排序第三最后一步忘记把枢轴换回i位置等于只做了个半成品划分。2.3 Hoare 双边划分更快但更烧脑的经典方案Hoare 划分比 Lomuto 更早出现它用两个指针从左右两端向中间扫描找到左侧第一个不小于枢轴的元素和右侧第一个不大于枢轴的元素然后交换。它一轮交换的次数更少所以常数因子更小。但边界条件也更微妙写错过一次就容易死循环。我常用的 Hoare 版本如下def quicksort_hoare(arr, lo, hi): if lo hi: return pivot arr[(lo hi) // 2] i, j lo, hi while i j: while arr[i] pivot: i 1 while arr[j] pivot: j - 1 if i j: arr[i], arr[j] arr[j], arr[i] i 1 j - 1 quicksort_hoare(arr, lo, j) quicksort_hoare(arr, i, hi)注意这里的递归区间是[lo, j]和[i, hi]不是[lo, i]和[j, hi]。由于退出循环时j已经小于i这两段区间之间不会有覆盖也不会漏排。很多人就是栽在这里把区间写反导致元素被重复排序或者漏掉。另外内层扫描用和而不是和这样能避免重复元素过多时指针卡死。交换之后还要各自i 1、j - 1保证循环能向前推进。如果你写 Hoare 版怎么也调不对建议先回退到 Lomuto 版把思路理清楚再试 Hoare。2.4 随机化枢轴与三路划分随机化版本是在 Lomuto 基础上加两行随机交换import random def quicksort_random(arr, left, right): if left right: return pivot_idx random.randint(left, right) arr[pivot_idx], arr[right] arr[right], arr[pivot_idx] pivot arr[right] i left for j in range(left, right): if arr[j] pivot: arr[i], arr[j] arr[j], arr[i] i 1 arr[i], arr[right] arr[right], arr[i] quicksort_random(arr, left, i - 1) quicksort_random(arr, i 1, right)随机化的意义不在提速而在“消除人为构造的最坏输入”。固定枢轴方案遇到极端有序序列会崩但只要枢轴是随机选的哪怕序列再特殊性能也只取决于随机数运气而不是输入本身。实际项目中数据可能来自各种渠道谁也无法保证不会出现恶意构造的坏序列随机化算是成本最低的保底策略。三路划分则用来解决“大量重复元素”问题。普通快速排序处理一百万个完全相同的元素时如果枢轴值等于大部分元素Lomuto 划分仍然会把所有相等元素扔到一边递归深度还是 n照样退化成 O(n²)。三路划分把区间切成三块小于枢轴、等于枢轴、大于枢轴递归时只处理小于和大于两块等于区直接跳过。代码很经典就是荷兰国旗问题的思路def quicksort_three_way(arr, left, right): if left right: return lt left i left gt right pivot arr[left] 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 quicksort_three_way(arr, left, lt - 1) quicksort_three_way(arr, gt 1, right)在真实数据里比如成绩统计、年龄统计、状态标记等场景大量重复值非常常见。三路划分是应对这种数据的关键优化而且会让算法在重复元素场景下理论上接近 O(n)。3. 复杂度边界、稳定性与性能实测3.1 最坏情况与退化场景很多人误以为快速排序“平均 O(n log n)”就默认它足够稳定。实际上它非常吃枢轴质量。前面说过最典型的退化场景是固定取最右端作为枢轴然后输入一个已经升序排列的数组。第一趟划分后右侧所有元素都比枢轴大左侧为空枢轴直接归位剩下的 n-1 个元素继续递归。每一趟只解决一个元素总复杂度自然变成 O(n²)。另一个不容易注意的退化场景就是全重复元素。比如一百万个 0你用 Lomuto 固定取最右端比较结果是每个元素都不小于枢轴一趟划分完成后枢轴换到最左端剩下 999999 个 0 继续递归。这个场景和有序数组一样糟糕随机化枢轴对“全相同”数据也救不了太多因为随机选到谁都是同一个值划分依然不均匀所以这时需要三路划分。我把常见退化场景整理成了速查表场景固定枢轴表现随机化枢轴三路划分有序数组O(n²)大概率恢复 O(n log n)O(n log n)逆序数组O(n²)大概率恢复 O(n log n)O(n log n)大量重复元素O(n²)仍然可能 O(n²)接近 O(n)3.2 稳定性表现与示例快速排序是不稳定的排序算法。所谓稳定是指两个相等元素的相对顺序在排序前后保持不变。举个例子有一组元组数据[(5, A), (3, B), (5, C)]我们希望按元组第一个数字排序。用 Lomuto 版跑一趟如果枢轴取最右边的(5, C)扫描时(5, A)并不会被交换到左侧最后枢轴换到i位置时数组会变成[(3, B), (5, C), (5, A)]。原本A在C前面排序后变成C在A前面相对顺序丢了。这个特性在按多个键排序时会带来麻烦。Python 内置的sorted()和list.sort()是稳定排序默认就是 Timsort所以在业务代码里如果你希望保证相等元素的顺序千万别自己手写快排去替代内置排序。但如果只是对基础数字排序稳定性就完全无所谓。3.3 与 Python 内置排序的对比实测我经常在技术群看到有人纠结“要不要用自己写的快排替代内置 sort”。结论很简单在 Python 里业务代码直接用内置排序手写快排属于学习、面试和特殊场景的产物。我做过一个粗略测试生成 20 万个 0 到 10 万范围内的随机整数分别用手写随机化快排和list.sort()跑import random import time def quicksort_random(arr, left, right): if left right: return pivot_idx random.randint(left, right) arr[pivot_idx], arr[right] arr[right], arr[pivot_idx] pivot arr[right] i left for j in range(left, right): if arr[j] pivot: arr[i], arr[j] arr[j], arr[i] i 1 arr[i], arr[right] arr[right], arr[i] quicksort_random(arr, left, i - 1) quicksort_random(arr, i 1, right) data [random.randint(0, 100000) for _ in range(200000)] data2 data[:] data3 data[:] start_time time.perf_counter() quicksort_random(data2, 0, len(data2) - 1) print(随机化快速排序耗时:, time.perf_counter() - start_time) start_time time.perf_counter() data3.sort() print(内置list.sort耗时:, time.perf_counter() - start_time)实测下来内置排序往往比纯 Python 手写快排快一个量级原因很简单内置 sort 是用 C 实现的 Timsort同时针对实际数据做了大量优化比如已经有序的片段检测、利用缓存局部性等手写纯 Python 循环则要经过解释器逐行执行天然吃亏。所以除非你需要“不引入额外内存的手写算法”或者“在算法题中展示实现能力”否则坚决用内置排序。3.4 递归深度与空间占用原地划分版本的额外内存主要来自递归栈。平均情况下递归深度是 O(log n)但最坏情况下可以达到 O(n)。Python 的默认递归深度限制通常是 1000所以拿一个一百万元素的退化序列跑普通递归快排几乎必然RecursionError。解决办法有两个方向一是修改递归深度限制比如sys.setrecursionlimit(1000000)但这只是把门槛抬高治标不治本因为 C 语言调用栈本身也有上限调得过高反而会直接让解释器崩掉二是放弃递归改用显式栈这正好对应很多人在搜的“快速排序非递归实现”。相比之下显式栈是更可控的方案至少你能精确掌握栈的大小甚至在必要时自行检查栈占用。4. 常见问题排查与实战调优记录4.1 递归爆栈禁用递归、改用栈模拟非递归快排的核心是用一个栈保存待排序区间。每处理完一个区间就把拆分出来的左右子区间压栈不断循环直到栈为空def quicksort_iterative(arr): stack [(0, len(arr) - 1)] while stack: left, right stack.pop() if left right: continue pivot arr[right] i left for j in range(left, right): if arr[j] pivot: arr[i], arr[j] arr[j], arr[i] i 1 arr[i], arr[right] arr[right], arr[i] stack.append((left, i - 1)) stack.append((i 1, right))这个版本和递归 Lomuto 的逻辑完全一样只是把“函数调用栈”换成了“自己管理的列表栈”。好处是递归深度不再是问题坏处是栈里的区间顺序可能影响实际运行时的局部性。如果你希望让栈空间尽量贴近 O(log n)可以在压栈前比较左右区间长度把较长的区间先压栈较短的区间后压栈先处理较短的。这个技巧在处理超大数组时能明显减少内存压力。我这里再补充一个细节压栈前做一下区间合法性判断会更高效。比如只在left i - 1时才压左区间只在i 1 right时才压右区间。这样能避免大量单元素区间入栈出栈的无意义循环。4.2 边界条件写错造成的无限递归如果说快速排序只有一件事必须刻在脑子里那就是边界条件。下面三种错误我调试过不止一次。第一终止条件写成left right。递归调用空区间时比如left0, right-1这个条件不成立函数不会退出。更可怕的是后续代码继续执行时right会是负数可能出现arr[-1]这种访问末尾元素的情况结果看起来“能跑”但排序结果是错的。第二递归区间包含枢轴。Lomuto 划分后枢轴已经在正确位置递归应该只处理left..i-1和i1..right。如果把左区间写成left..i枢轴会被反复纳入排序数据量稍大时每一层的规模减少速度变慢严重时递归层数爆炸。第三Hoare 版递归区间写反或重叠。Hoare 划分结束后j和i已经交叉正确区间是[lo, j]和[i, hi]。有人习惯性地写[lo, i]和[j, hi]结果两个区间重叠一部分元素被重复排序另一部分可能漏掉。我排查这类问题时习惯在递归函数开头打印left和right看有没有异常区间或者干脆写一个assert left right。调试完成后再把打印删掉用随机数据和sorted()对比验证。4.3 重复元素引发的性能陷阱前面提到过普通 Lomuto 快排在全部元素相等时退化为 O(n²)。我曾经在处理线上配置数据时遇到过类似问题一个十几万行的列表里排序键只有两三个取值用普通快排跑一次居然要好几秒换成三路划分后毫秒级完成。从那以后我再也不敢忽略重复元素这个因素了。三路划分的代码逻辑并不复杂它通过lt和gt两个指针维护“等于枢轴”的中间区域。如果你不想把三路划分写得太复杂也可以采用另一种折中策略当检测到大量重复元素时回退到sorted()或使用其他改进算法。但对学习而言我建议还是亲手实现一遍三路划分因为那个“荷兰国旗”思路在别的算法题里也会用到比如按颜色分类、按 0/1/2 分组等问题。另外三路划分仍然不稳定。如果业务需求强调稳定又不允许用内置排序那就要考虑归并排序而不是继续折腾快排。4.4 应试与工程中的选型建议在面试手撕代码时我建议的优先级是先写随机化 Lomuto 版本因为代码量最少、逻辑清晰、不容易出边界事故。如果面试官追问复杂度再顺势说出随机化对最坏情况的防御以及为什么还需要三路划分。这样既能展示你理解深度又能快速通过考核。工程上就完全不同。Python 内置的list.sort()是稳定、自适应、C 语言实现的 Timsort也是 Python 官方花了大量精力调优过的排序算法。业务代码里如果只是想排个列表手写快排更多是自找麻烦。我只有在以下几种情况会考虑手写快排算法题、教学演示、需要完全控制比较逻辑且对空间占用有严苛要求的嵌入式场景、以及语言本身没有提供可靠排序库的场景。还有一个小技巧如果需要按降序排序可以简单地把比较条件改成if arr[j] pivot或者写完后反转。但多键排序时更稳妥的方式是给元素包一层排序键然后用内置sorted(..., key...)又快又不会破坏稳定性的预期。我个人在实际项目里的体会是快速排序真正值钱的地方不在那几十行排序代码而在它背后“选基准、分区间、递归治理”的分治思想。我见过不少同事背熟了 Lomuto 模板但稍微改个需求比如降序、按对象某个属性排序、处理重复元素就手足无措。所以与其背代码不如把划分过程在纸上画一遍搞清楚指针移动的真实现场。等你把边界条件变成肌肉记忆之后不管面试哪个版本都能很快写对。最后再分享一个小技巧写完任何版本都快排都先用random生成大量随机数据再用assert sorted(arr) expected做自动化验证然后专门测试空列表、单元素列表、全部相同元素、逆序元素这四类边界数据。这四类一过代码基本就稳了。快速排序的坑大多集中在极端输入提前用脚本把这些场景跑一遍比事后再从报错信息里猜原因高效得多。