提到排序算法大多数人脑中的第一反应就是快速排序。尤其是面试环节快速排序几乎是必考题但很多教程只丢给你一段递归代码让你背下来真到让你讲讲“为什么这么写”“最坏情况怎么防范”的时候就露馅了。这篇文章我不打算把教科书伪代码抄一遍就完事而是要把Python里快速排序的完整实现路径讲清楚——从最基础的分区逻辑到随机化、非递归、三路分区再到我实际调试中踩过的递归栈溢出和死循环坑。目的是让你看完之后既能手写经典代码也能写出能应对真实数据的工程版本。无论你是准备面试的在校生还是工作中需要手写定制排序的开发者按文章的代码走一遍能少走不少弯路。1. 快速排序核心思想与设计拆解1.1 分治思想快速排序在解决什么问题快速排序是Tony Hoare在1960年提出的分治排序算法。它解决的本质问题非常朴素如何把一个乱序的大数组用尽量少的比较和交换变成有序数组。手段也直接——选一个基准值把小于基准的放左边大于基准的放右边于是基准元素在一次分区后就处在了最终位置上。接下来对左右两个子数组重复同样的操作最终整个数组有序。这个思路放到生活里很像整理一摞混杂的试卷你随手抽一张卷子作为分数线分数低于它的放左边高于它的放右边这张卷子的位置就固定了。左右两摞再各自抽一张继续分直到每摞只剩一张。整个过程没有另外开一份空间去抄数据而是直接在原数组上交换这是快排在内存受限环境下依然能打的根本原因。这里要注意快排和归并排序的本质区别。归并排序也是分治但它的核心工作量在“合”把两个有序子数组合并时需要额外数组空间。快排的核心工作量在“分”只要分区划得合理合这一步几乎不存在因为每个元素在一次分区后就已经处在最终相对位置附近。这个差异直接决定了快排的空间复杂度更低平均只需要O(log n)的递归栈空间。1.2 为什么工程里还是绕不开快速排序你可能会问Python内置的sorted已经用C语言实现了为什么还要自己写快速排序这个问题很实际。如果只是为了把列表排好序直接调用sorted()或list.sort()是对的内置TimSort融合了归并和插入排序的优点常数因子极小性能天花板很高。但至少有三个场景你绕不开快排。第一是面试和算法考核快速排序是高频考点考官会通过它考察递归、原地交换、指针边界、复杂度分析这些基本功背答案没用。第二是定制排序场景当你需要处理自定义对象、按特定规则分区、或者用分区思想解决Top-K和快速选择问题时快排的分区逻辑能直接变成高效工具。第三是受限环境某些嵌入式环境或者无法依赖标准库排序的场景里快排这份“不依赖额外大内存”的算法就是最可靠的候选之一。就算这些场景你都不沾边理解快排也会让你在看数据库排序、分布式系统分区策略这类更高级的话题时拥有更敏锐的直觉。排序不只是排序它代表了一类“分而治之原地整理”的工程思维。2. Python实现前的关键准备与方案选型2.1 运行环境与前置知识准备这篇文章里的所有代码我都用Python 3.10以上版本验证过不需要安装任何第三方库标准库就够。如果你电脑里还没有Python环境去官网下载对应平台的安装包安装的时候记得勾选“Add Python to PATH”这样在终端里直接敲python就能进交互模式。用VS Code的同学装好Python扩展然后在左下角选对解释器路径就行。这里的细节不难但很多人卡在第一步。动手写快排之前你只需要理解三件事递归、列表原地修改、以及切片到底发生了什么。递归决定快排的天然写法原地修改意味着你不需要用return返回新数组而切片arr[:k]会复制出一段新列表如果你在递归里用了切片排序结果就不会反映到原数组上这是一个非常隐蔽的坑我后面专门讲。还有一个容易被忽略的基础点Python函数传参是引用传递列表作为参数传进去后函数内部修改会直接作用在原对象上。所以写快排时好的习惯是定义def quicksort(arr, low, high)直接操作arr最后不需要任何返回值。另一种“纯函数”风格每次都返回新列表虽然代码看起来更干净但会带来额外的内存复制和性能损耗不适合工程场景。2.2 分区方案选型Lomuto还是Hoare快排实现的分水岭在分区函数主流两种Lomuto分区和Hoare分区。Lomuto以数组最后一个元素为基准用一个慢指针i维护小于基准区域的右边界快指针j遍历整个数组。遇到小于等于基准的元素就把i前进一位并交换arr[i]和arr[j]。遍历完成后把基准换到i1的位置。优点是逻辑直观、易懂、好写特别适合教学和面试讲解缺点是交换次数偏多在部分数据分布下性能略差。Hoare则是双指针从两端相向扫描左指针找比基准大的元素右指针找比基准小的元素找到一对就交换。最终返回的分界点把数组分成“左边整体小于右边整体”的两块。交换次数更少平均性能更好但边界条件需要非常小心稍不留神就写出死循环或越界。我给一个实用建议面试首选Lomuto因为容易写、容易解释、不容易出错生产环境或数据规模很大时优先用Hoare。接下来两个版本我都会给出完整代码并逐步拆解。3. 快速排序核心代码实现与逐步拆解3.1 Lomuto版本最容易背诵的写法def quicksort(arr): def _sort(low, high): if low high: return pivot arr[high] i low - 1 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] pi i 1 _sort(low, pi - 1) _sort(pi 1, high) _sort(0, len(arr) - 1) return arr逐行说关键逻辑。pivot arr[high]表示取最后一个元素作为基准这样做的目的只是简化循环边界。i low - 1代表小于基准区域的终点初始时该区域为空。从low遍历到high-1时只要arr[j]不大于基准就把它丢进左侧区域具体操作是先把i前移一位再交换arr[i]和arr[j]。循环结束后所有小于等于基准的元素都在i之前i1就是基准的最终位置交换过去后基准就位。随后递归排序基准左边和右边。还有一个细节值得讲比较符号用的是不是。如果改成等于基准的元素会被扫到右侧在重复数据较多时分区严重失衡复杂度会很快向O(n²)滑落。不过就算用当数组里全是相同元素时Lomuto也会退化因为等于基准的值全部堆积在左侧右侧每次只减少一个基准元素真正的问题规模几乎没变。这种场景的正确解法是三路分区我在4.2会说。3.2 Hoare版本工程中更快的双指针方案def quicksort_hoare(arr, low, high): if low high: return pivot arr[(low high) // 2] i, j low - 1, high 1 while True: i 1 while arr[i] pivot: i 1 j - 1 while arr[j] pivot: j - 1 if i j: break arr[i], arr[j] arr[j], arr[i] quicksort_hoare(arr, low, j) quicksort_hoare(arr, j 1, high)这里有几个关键设计。基准取中间元素而不是首尾元素好处是在面对已经有序的数组时分区不会严重失衡。内层两个while用的都是严格小于和严格大于遇到等于基准的元素就停住这样即使数组里全是相等元素指针也会停在中间位置附近然后交换退出不会无意义地一路扫到底。循环结束条件用if i j: break最后以j作为递归分界。这里经常出问题有的资料会把递归边界写成(low, i-1)和(i, high)在特定数据下会漏排或重复排。我的建议是严格按照(low, j)和(j1, high)来写配合一个小数组手走一遍就能确认逻辑。Hoare版本稍微难懂但值得花时间吃透它的性能优势在随机数据下明显胜出。3.3 随机化版本摆脱最坏情况的必杀技import random def quicksort_random(arr, low, high): if low high: return rand_idx random.randint(low, high) arr[rand_idx], arr[high] arr[high], arr[rand_idx] pivot arr[high] i low - 1 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] pi i 1 quicksort_random(arr, low, pi - 1) quicksort_random(arr, pi 1, high) return arr随机化的动机很简单当输入数据已经有序或接近有序时固定取端点基准会让每次分区一侧为空递归树深度变成n时间复杂度退化成O(n²)。尤其在大数据量下这种退化是灾难性的。随机选一个位置和最后一个元素交换相当于把基准的选择变成随机事件恶意构造数据很难再命中你最差的分区方式。平均情况下随机化后快排的时间复杂度稳定在O(n log n)。代价是random.randint本身有一点额外开销但相比整个排序时间几乎可以忽略。我实测下来随机化对“接近有序”和“恶意构造数据”两类的提升最明显。如果你确定数据来源安全、不可能被针对性构造那么省略随机化也不会出大问题但多写一行交换代码换来的是更稳的心理保障我认为很值。4. 非递归实现与进阶优化策略4.1 非递归快速排序用栈对抗递归深度限制Python默认递归深度限制大约是1000层快排在平均情况下递归深度是O(log n)100万个随机整数上大约20层表面上不会出问题。但一旦数据触发最坏分区递归深度瞬间增长到n级别100万数据直接触发RecursionError。递归函数调用本身也有栈帧开销在稳定性要求高的环境里显式栈模拟递归是更好的选择。def quicksort_iterative(arr): stack [(0, len(arr) - 1)] while stack: low, high stack.pop() if low high: continue pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] pi i 1 arr[pi], arr[high] arr[high], arr[pi] stack.append((low, pi - 1)) stack.append((pi 1, high)) return arr这个版本和Lomuto分区逻辑一致只是把递归调用换成了栈。入栈顺序对正确性没有影响因为左右子问题谁先处理都不改变最终结果。但从栈空间角度有一个优化技巧每次先压较大的子数组再压较小的子数组这样栈中同时保留的任务数量始终被控制在O(log n)量级。生产级代码一般都会做这一步。另外不要以为非递归一定比递归快。Python函数调用开销在大数据量下会被列表遍历的时间稀释两者性能差异很小。非递归的核心价值是可预测性——不依赖调用栈深度没有递归溢出风险。如果你在写一个长期运行的排序模块这是非常重要的优势。4.2 三路分区处理重复元素的正确姿势大量重复数据是经典快排的噩梦。用户标签、状态码、库存数量这些字段经常出现海量重复值用Lomuto分区时等值基准全部堆在左侧递归时真正待排序的规模几乎不减复杂度崩向O(n²)。三路分区也就是荷兰国旗分区专门解决这个问题def quicksort_3way(arr, low, high): if low high: return pivot arr[low (high - low) // 2] lt, i, gt low, low, high 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_3way(arr, low, lt - 1) quicksort_3way(arr, gt 1, high) return arr这段代码维护三个区间arr[low:lt]全部小于基准arr[lt:gt]全部等于基准arr[gt1:high]全部大于基准。i从左向右扫描遇到小于基准的值就交换到左边界并同时推进lt和i遇到大于基准的值就交换到右边界只收缩gt等于基准就什么都不做只推进i。循环结束后等于基准的整块区间已经全部归位后续递归完全跳过这一段重复数据越多性能反而越好。我拿100万个完全相同元素实测过经典Lomuto版本会退化到几乎无法完成三路分区版本几乎是瞬间结束因为第一轮分区后左右两侧都是空区间递归直接终止。如果你的业务数据里经常有高重复度字段三路分区应该是你的默认选项。4.3 小数组阈值与插入排序混合优化还有一个实用的组合优化当待排序子数组长度小于一个阈值时不再继续递归分区而是改用插入排序。常见阈值是16或32。原因很实在——递归调用、维护栈帧、执行分区循环这些固定开销在小数组上反而比插入排序的简单移动更贵。插入排序在小规模数据上常数极小而且对近乎有序的数据表现尤其好。def insertion_sort(arr, low, high): for i in range(low 1, high 1): key arr[i] j i - 1 while j low and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key def quicksort_mix(arr, low, high, threshold16): if high - low 1 threshold: insertion_sort(arr, low, high) return pivot arr[high] i low - 1 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] pi i 1 quicksort_mix(arr, low, pi - 1, threshold) quicksort_mix(arr, pi 1, high, threshold)如果你还想继续压性能可以在选基准时做三数取中——取low、mid、high三个位置的中位数作为基准进一步降低分区失衡概率。这些小优化不是炫技C标准库的qsort实现里就综合了这些策略。面试时被问到“还有什么优化手段”能说出阈值混合、三数取中、随机化、三路分区这四件套已经是很漂亮的答案了。4.4 不同实现方案的实测对比我自己在笔记本上跑了轮对比Python 3.11数据规模20万个随机整数范围0到10万每个方案重复5次取中位数大致结果如下方案相对耗时适用场景内置sorted0.03秒级绝大多数常规场景无脑首选Lomuto递归0.45秒级教学、面试最简单实现Hoare递归0.30秒级常规手写排序首选随机化Lomuto0.52秒级需要抵抗恶意输入时非递归Lomuto0.47秒级避免递归深度问题三路分区0.34秒级重复元素多的数据阈值混合优化0.28秒级生产优化向手写方案数字只反映相对量级不同机器会有浮动但两个结论比较稳定内置sorted永远是碾压级别的性能手写方案里Hoare分区和阈值混合优化最值得投入精力。还有一点经验随机化带来安全性的同时也有开销如果你确定数据构造安全可以省略随机化来换一点点性能。5. 常见问题与排查技巧实录5.1 RecursionError递归深度溢出怎么办这个错误我在调试快排时遇过太多次典型场景就是几千个有序元素直接报“maximum recursion depth exceeded”。原因很明确固定选端点基准输入又已经有序递归深度等于元素个数轻松超过Python默认的1000层限制。排查办法是先小规模复现在递归函数里打印low和high观察每次递归后区间是不是只在缩小一个元素。临时办法是sys.setrecursionlimit(10000)但这只是把症状后移。生产代码里我从来不调递归上限因为Python递归栈开销远大于显式栈万一上限设置过高进程可能直接崩溃而不是抛出可捕获异常。正确做法是用4.1的非递归版本或者在4.3的阈值混合版本里加小数组保护。5.2 分区后死循环与越界的排查方法死循环最常出现在Hoare分区。典型错误是内层循环用了而不是例如while arr[i] pivot: i 1。当pivot是数组最大值的时候i会一路越过high边界下次访问arr[i]直接IndexError。另一个常见错误是递归边界传错导致无限递归或者漏排。排查这类问题我的通用手段是在分区函数入口和出口打印low、high、i、j、pivot跑一个5元素小数组把每一步手工走一遍。特别是Hoare版本循环结束后返回j作为分界递归边界用(low, j)和(j1, high)。如果你在两个递归调用里写成(low, i-1)和(i, high)在特定数据下就会出边界问题。遇到这类bug不要靠肉眼死盯代码画图最有效。5.3 切片式写法为什么是个坑网上流传很广的“简洁版”长这样def quicksort_slice(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] left [x for x in arr if x pivot] right [x for x in arr if x pivot] mid [x for x in arr if x pivot] return quicksort_slice(left) mid quicksort_slice(right)这段代码功能没错用来理解分治思路也完全合格但它有两个致命问题。第一每次递归都创建了三个新列表空间复杂度退化到O(n log n)根本不是原地排序。第二性能比原地版本差很多数据量过百万后慢得让人失去耐心。还有一点它返回的是新数组调用方原本持有的列表引用不会改变这在很多业务代码里是致命的语义差异。我建议你把这个切片版本当作分治思想的入门玩具但生产代码用它就是灾难。面试官看到这种写法一般会追问“能不能写成原地版本”如果你能顺势引出分区指针、递归栈深度这些话题反而能展示出思维深度。5.4 稳定性说明什么时候不能无脑用快排稳定性是排序算法最容易被忽略的性质之一。快速排序不稳定因为分区交换时相等元素的相对顺序可能被打破。举个业务场景你有一组学生记录先按姓名排好再按班级排第二轮用快排的话班级相同的学生之间姓名顺序可能就乱了。如果预期保留第一轮排序键的顺序你需要的是稳定排序。Python内置的sorted基于TimSort是稳定的C的std::stable_sort也是稳定的。当你需要级联排序时直接用sorted多次排序或者用key(字段A,字段B)元组处理都比手写快排稳妥。手写快排前一定问自己数据里有没有依赖稳定性的键有就选归并或TimSort没有再放心用快排。6. 快速排序与主流排序算法的横向对比6.1 快排、归并、堆排序三强对比把快排、归并、堆排序放到一张表里差异一目了然算法平均时间复杂度最坏时间复杂度空间复杂度稳定性快速排序O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定快排最坏O(n²)的根源是每次分区严重失衡比较次数变成n-1 n-2 ... 1。那它为什么依然受欢迎因为平均性能极好常数因子最小而且加入随机化和三路分区后最坏情况在现实中几乎不会出现。堆排序最坏也稳定在O(n log n)但缓存局部性远不如快排实际速度一般也不如。归并排序稳定且最坏可控但需要额外O(n)空间在超大数组上内存压力明显。选择并不复杂需要稳定用归并或TimSort需要最坏情况可控且想少占内存选堆排序追求平均速度、想要原地、希望保留优化空间直接用快排。6.2 不同数据场景的选型建议按数据特征给一份速查指南常规列表、没有特殊要求直接用sorted()或list.sort()稳定、快、省心。数据几乎有序插入排序直接就是O(n)内置TimSort也是极佳选择不要用固定端点基准的快排。大量重复值三路分区快排或者直接内置排序。内存非常紧张原地快排Hoare分区是首选。需要稳定性使用内置排序或归并排序。超大数据量超出内存归并排序思想为主的外部排序。这里我需要专门提一下内置sorted综合性能最好那为什么还要学习快排因为内置排序是固定黑盒你在工程里常有“部分有序子区间单独重排”或“Top-K、按列快速筛选”这类需求。快排的分区思想可以直接变化出高效工具比如快速选择算法QuickSelect就是只递归一边平均O(n)就能找到第K大的数这是sorted不具备的能力。理解快排相当于多了一把能按需改装的螺丝刀。说到练习我的真实建议是不要只看不写。拿一张纸画一个10个元素的乱序数组用Lomuto分区一步步走一遍再画第二个数组用Hoare走一遍。然后把文章里的每个版本都敲进编辑器用随机数据加断言验证最后用我上面提到的边界例子全相等、已有序、倒序、大量重复专门测一遍。这样折腾一晚上快排的各种细节就真的是你的了。有机会的话再把场景扩展到快速选择、区间统计之类的变体你会发现自己对分治算法的理解已经不是一个水平了。