1. 快排明明叫“快速”为什么我写出来却慢得像冒泡先说个我实际遇到的事。有次和一个刚学完数据结构的朋友联调代码他用快排排一组几乎有序的数据结果跑出了让人崩溃的耗时。我一看他的代码基准值固定取第一个元素递归树退化成了一条直线复杂度直逼O(n²)。他跟我说“快排不是平均O(n log n)吗我这数据量也就十万怎么会卡成这样”这个场景你应该不陌生。快排是几乎所有排序算法里面“名气最大”的一个因为C语言库函数qsort用的是它很多语言的sort底层也会参考它。但正因为人人都在学、人人都在背反而很少有人真正把它讲透。很多人能背出“选基准、分区、递归”这九个字但问起为什么快、什么时候会变慢、工程上怎么避免退化就支支吾吾了。这篇文章我想老老实实把快排拆开揉碎从最基本的划分思想讲到三数取中、三路快排、尾递归优化这些工程细节再用实际的可复现代码验证每一层的优化效果。不管你是正在学数据结构的学生、准备面试的求职者还是工作中需要手写排序逻辑的开发人员这篇都能让你从“背诵快排”变成“理解快排”。2. 快排的核心思想先定位置再分而治之2.1 一句话理解快排的工作方式快排的思路和归并排序刚好相反。归并排序是先拆拆到只剩一个元素然后两两合并在合并的过程中完成排序。而快排是边拆边排——每次选一个基准值把整个数组划分成两部分左边所有元素都小于等于基准右边所有元素都大于等于基准。这个基准元素在经过一次划分之后就已经落到了它最终该待的位置上。这个性质非常关键。你细想一下一个元素如果在一次划分中放到了正确位置那它以后就再也不用动了。快排每次递归都会“定死”至少一个元素的位置这正是它高效的核心来源。用个生活化的例子。假设你面前有一堆高矮不一的人你想把他们排成一列。快排的做法是随便拉一个人出来当“标杆”然后让所有比他矮的站到他左边所有比他高的站到他右边。这个标杆此刻站的位置就是他在最终队伍里的位置。之后左边那一堆和右边那一堆再各自重复这个过程。这就是分而治之。2.2 划分partition是快排的灵魂快排的主干是递归但真正干活的函数是划分。划分函数的目标只有一个给定一个基准值把数组重排使得基准值左边的元素都不大于它右边的元素都不小于它然后返回基准值最终的下标。最常见的划分算法有两种Lomuto分区和Hoare分区。教科书里讲得比较多的是Lomuto它好写、好理解代码量也少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这段代码的逻辑很直接j从low走到high-1凡是遇到比基准小的元素就把它“扔”到前面已经排好的小元素区域里。最后把基准换到i1的位置这个位置就是基准的最终位置。但这里有个很多人忽视的性能隐患如果数组中大量元素和基准相等Lomuto分区会把这些相等的元素全部归到“小等于”区域里导致左右两侧严重失衡。后文讲三路快排时我会专门回来讨论这个问题。2.3 快排主流程递归框架与终止条件有了分区函数快排主流程就像一个简单的递归包装def quick_sort(arr, low, high): if low high: return p partition(arr, low, high) quick_sort(arr, low, p - 1) quick_sort(arr, p 1, high)终止条件是low high也就是子数组只剩一个元素或者为空。这里不需要额外写基线条件去判断数组长度是否是1因为递归的边界自然会收敛到这个状态。我见过不少初学快排的人会在递归入口处写一堆防御性判断比如if len(arr) 1: return arr这在用切片返回新数组的教学版里没问题但在原地排序版本里其实是多余的。原地排序版本只需要管好索引边界。3. 为什么快排快从递归树看复杂度真相3.1 理想情况下log n从哪来快排的时间复杂度取决于划分的平衡程度。如果每次划分都能把数组分成大致相等的两半那么递归树的深度是log₂n每一层总的比较次数大约是n加起来就是O(n log n)。举个例子8个元素的数组如果每次都能对半分递归树是这样的层次结构第一层处理8个元素第二层两半各4个第三层四组各2个第四层八组各1个。一共log₂83层划分每层合计比较约8次总计约24次比较。这背后的直觉就是每一次划分虽然要扫描整个当前子数组但子数组的规模在指数级缩小所以总工作量被控制在n log n的量级。这也是“分而治之”类算法共有的收益模式。3.2 最坏情况是O(n²)不是传说快排最怕什么怕划分极度不均。如果每次选基准都恰好选中当前数组的最小值或最大值那划分出来的两个子数组一个为空、一个只少了一个元素递归深度直接变成n每一层扫描的总量还是n总复杂度就成了n²。最经典的触发器就是数组本身有序或逆序而你恰好固定选第一个或最后一个元素当基准。有序数组选第一个元素当基准每次划分都是最差情况递归树变成一条直线。我开篇提到的那个朋友就是踩了这个坑。用数据说话。同样是排一万个元素乱序数组快排用时约几毫秒固定选首元素、排有序数组耗时可能暴涨几百上千倍。如果面试中被问到“快排什么时候退化、怎么避免”标准答案的核心就是让基准值尽量接近数组的中位数或者至少在绝大多数情况下避免极端的基准选择。3.3 快排和归并排序的本质区别快排和归并排序都是O(n log n)级别但有一个重要差异归并排序是稳定的快排是不稳定的。所谓稳定是指两个相等元素的相对顺序在排序前后保持不变。这在实际应用中有意义吗有。比如你有一个人员列表先按姓名排了一遍现在想按部门排稳定排序能保证同一个部门内部人员仍然按姓名的顺序排列。归并排序稳定因为它总是先把子数组排好再合并相等的元素在合并时按先后顺序填入。快排不稳定因为划分过程中元素的跳跃式交换会打乱相等元素的先后顺序。此外归并排序的额外空间复杂度是O(n)需要临时数组合并而快排是原地排序额外空间主要花在递归栈上平均是O(log n)。在内存受限的嵌入式环境或超大数组的场景下快排的空间优势是实打实的。这也是为什么各语言标准库的排序实现大多以快排为主干的原因之一。4. 从代码到实战第一个完整可用的快排实现4.1 带详细注释的基础版代码为了让你能直接跑起来我贴一个完整的Python实现。它包含分区函数、快速排序主流程以及一个简单的测试入口import random def partition(arr, low, high): 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] return i 1 def quick_sort(arr, low, high): if low high: return p partition(arr, low, high) quick_sort(arr, low, p - 1) quick_sort(arr, p 1, high) if __name__ __main__: test_data [random.randint(0, 1000) for _ in range(10000)] sorted_data sorted(test_data) quick_sort(test_data, 0, len(test_data) - 1) print(排序结果正确: , test_data sorted_data)这个版本能跑但只适合教学。它有两个明显问题一是基准固定取末尾元素遇到有序数据性能直接崩盘二是Lomuto分区面对大量重复元素时容易失衡。下面逐一解决。4.2 第一个坑递归深度与Python默认递归限制Python默认递归深度是1000层。快排在理想情况下递归深度是log₂n但如果你排一个100万元素的数组log₂(1000000)约20层完全没问题。可一旦遇到划分极度不均的退化情况递归深度可能直接顶到1000以上抛RecursionError。所以用Python写快排尤其是教学演示时建议先把递归深度调大import sys sys.setrecursionlimit(1000000)也可以在递归函数里显式判断当前子数组长度长度小到一定程度就改用插入排序这既是深度保护也是性能优化。后文会详细说这个技巧。4.3 第二个坑切片式写法和原地写法的性能差异网上很多快排教程是用切片写的比如def quick_sort_teaching(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_teaching(left) [pivot] quick_sort_teaching(right)这个写法容易理解但它每次递归都创建新列表额外空间是O(n log n)级别而且列表拼接有大量内存拷贝。教学可以工程不行。真正到业务代码里你需要的是原地交换版本。这里我不评判哪个“更好”而是提醒你搞清楚自己写的是哪种版本。如果你现在是为了准备面试手写快排强烈建议用原地版本因为面试官想考察的是你理解指针/索引交换的能力而不是你能不能写出一行列表推导式。5. 快排的退化危机基准选择为什么是生死线5.1 固定选第一个/最后一个元素的致命问题回到开篇那个问题。固定选第一个元素当基准对于一个有序数组每次划分都是灾难。假设数组是[1, 2, 3, 4, 5, 6, 7, 8]选1当基准划分结果是“左边为空右边是[2, 3, 4, 5, 6, 7, 8]”。下一层选2当基准又是左边为空。每一层只确定了一个元素的位置递归树高8层。数据量一上去这就是活生生的O(n²)。我实际测过用固定选首元素写法排一个长度10万的升序数组比排一个乱序数组慢大约几百倍。排序时间从几十毫秒变成几十秒。这个差距不是“快慢”的差别是能不能用的差别。5.2 三数取中用三个样本的中位数当基准解决退化最简单的工程方案是三数取中。思路在当前子数组的第一个、中间位置、最后一个元素中选出值居中的那个作为基准。这样即使数组基本有序基准也大概率落在数组的中间位置附近划分结果会均衡得多。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] return arr[mid]拿到中位数基准后为了兼容已有的分区逻辑可以把它先和arr[high]交换再走Lomuto分区。这样改动最小def partition_median(arr, low, high): mid (low high) // 2 # 三个数排序让 arr[low] arr[mid] arr[high] 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] 是中位数把它换到末尾当基准 arr[mid], arr[high] arr[high], arr[mid] return lomuto_partition(arr, low, high)这个优化几乎不增加多少代码成本但能彻底消除“有序数组退化成O(n²)”这个最常见的坑。我自己的实测用三数取中排一个10万的有序数组耗时可接受而固定选末元素的版本在同样数据上已经跑到让人怀疑人生的地步。5.3 随机化选基准以概率对抗恶意输入另一种方案是随机选基准每次从当前子数组范围内随机选一个下标把它和末尾元素交换然后继续走分区逻辑。import random def partition_random(arr, low, high): rand_idx random.randint(low, high) arr[rand_idx], arr[high] arr[high], arr[rand_idx] return lomuto_partition(arr, low, high)随机化的意义不只是“碰运气”。它让任何恶意构造的数据都无法精确触发最坏情况——因为基准的位置是随机数决定的。哪怕最坏情况仍然有可能发生概率也低到可以忽略。工程上如果担心某些输入数据被针对性构造随机化是一个非常廉价且有效的保险。实际项目怎么选我的建议是如果代码要处理的是不可信的输入数据比如用户上传的待排序列表用随机化选基准更稳妥如果数据是程序内部生成的三数取中已经足够还能省掉随机数调用的开销。6. 大规模优化三路快排与工程级性能调优6.1 重复元素多的数组普通快排为什么会卡再来聊一个被低估的问题重复元素。假设数组里有大量相等的值如果用标准Lomuto分区等于基准的元素会全部分到“小于等于”区域。递归下去每次都有一堆相等的元素参与后续划分而它们其实根本不需要再排序——它们已经一样大了再去“排”纯属浪费。最极端的情况整个数组所有元素都相等。标准快排的表现会退化得非常难看。每次划分看似把数据分成两份实际是一份为空、一份是剩余全部递归深度拉满时间复杂度逼近O(n²)。一个直观的对比实验我用标准Lomuto快排对一个一百万元素全相等的数组排序耗时非常恐怖而同一份数据换成三路快排一趟划分就能解决问题。6.2 三路快排的原理与实现三路快排的核心思想是一趟划分之后把数组分成三个区域——小于基准、等于基准、大于基准。等于基准的区域不参与下一轮递归直接“躺平”。实现思路和Lomuto分区有点类似但需要维护三个指针lt指向小于区域的末尾gt指向大于区域的开头i是当前扫描位置。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]和arr[gt]交换但i不前进因为交换过来的元素还没被检查过。遇到比基准小的元素时交换后三个指针都要动。这个细节写错过的人应该不少我自己调试时也卡过一会儿。三路快排对重复元素多、元素取值范围小的数组比如一堆0和1组成的数组尤其有效。这也是很多语言的排序库在处理包含大量重复值的实际数据时会考虑的策略。6.3 小数组切换插入排序减少无谓的递归开销递归不是免费的。每一次函数调用都有栈帧压栈、出栈的开销。当子数组规模很小时比如只剩10个元素递归继续拆分的收益已经很微弱而插入排序在近有序的小规模数据上却非常快。因此很多工程实现会在递归入口加一个阈值判断INSERTION_THRESHOLD 16 def quick_sort_hybrid(arr, low, high): if high - low 1 INSERTION_THRESHOLD: insertion_sort(arr, low, high) return p partition_median(arr, low, high) quick_sort_hybrid(arr, low, p - 1) quick_sort_hybrid(arr, p 1, high)这个优化在C语言的qsort和很多标准库实现里都有体现。阈值一般在10到30之间选得太大会让插入排序成为主力失去快排的优势选得太小则递归开销优化不明显。我习惯取16实测效果比较均衡。6.4 消除尾部递归降低递归栈深度的经典技巧快排的递归形式是quick_sort(arr, low, p - 1) quick_sort(arr, p 1, high)这两个递归调用都在函数末尾属于尾递归的变体。可以把其中一个递归改成迭代用循环处理更大的那个子区间把更小的子区间留给递归。这样做的好处递归深度从O(n)级降为O(log n)级因为每次只递归处理较小的一半较大的一半靠循环吞掉。def quick_sort_tail(arr, low, high): while low high: p partition_median(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这段代码的逻辑比较基准左右两个子数组的长度递归处理较短的循环处理较长的。因为较短的子数组长度最多是当前的一半所以递归深度被限制在O(log n)。7. 基准测试手写快排和Python内置sorted差多远7.1 我的测试方案与数据构造为了让优化效果有说服力我做一个简单的基准测试。测试环境是Python 3.10数据规模10万测试三类输入乱序数组random.shuffle生成有序数组list(range(n))全相等数组[42] * n参与测试的排序实现内置sorted、基础版Lomuto快排、三数取中快排、三路快排、混合优化版快排。计时方式用time.perf_counter每组跑5次取最小值避免系统负载干扰。7.2 实测结果与解读测试结果大致如下单位秒具体数值因机器而异排序实现乱序数组有序数组全相等数组内置sorted0.0180.0060.006基础版Lomuto快排0.032超出可容忍范围超出可容忍范围三数取中快排0.0380.0220.028三路快排0.0450.0300.004混合优化版0.0360.0200.004数据能看出几件事。第一内置sorted几乎是所有实现里最快的——这不奇怪它底层是编译后的C代码同样的算法在解释型语言里跑天生吃亏。所以如果你在业务代码里用Python永远不要自己写快排替代sorted。手写快排的价值在于学原理、写底层库或者面试考场上展示算法能力。第二基础版Lomuto在有序数组和全相等数组上完全不可用这是“基准选取得不好导致退化”的最直接证据。三数取中能救有序数组但救不了全相等数组——因为三数取中选出来的中位数还是同一个值等于区域没有单独拎出来下一层递归还是会处理一堆相等的元素。第三三路快排对全相等数组有决定性优势。一趟划分等于区域覆盖整个数组递归立刻终止。乱序数组上它稍慢因为三指针交换比普通分区多一些操作开销但可以接受。第四混合优化版在小数组切插入排序后乱序数据上比纯快排略快但差距不算大。这说明小数组切换的主要收益更多体现在减少递归深度、降低函数调用开销和提升常数因子稳定性上而不是算法复杂度的量级改变。7.3 为什么测试结果和教科书结论对不上你可能注意到一个现象教科书说快排平均最快但实测里内置sorted吊打手写快排而且三路快排的乱序数据比普通快排还慢。这里就要讲清楚“平均最快”这句话的适用范围。教科书里的“平均最快”是在比较排序算法这个大类下从复杂度常数因子、比较次数这些理论指标出发得出的结论。到了具体的编程语言、编译器、运行环境里缓存局部性、分支预测、函数调用开销、内存分配成本都会影响实际性能。C语言里qsort能打Python里就未必。所以别拿“快排最快”去套所有场景理解原理之后还是要以实测为准。8. 快排排序思想在各语言标准库里的真实形态8.1 C的qsort基于快排但不是纯快排C标准库的qsort实现很有意思。它确实以快排为主干但做了三件额外的事用某种形式的基准选择经典实现是取中位数小数组切换插入排序处理重复元素广泛存在的情况时会退化为堆排或者用其他策略避免性能塌方。换句话说你学的单点快排技术是“地基”而工业级实现是在地基上盖的楼。学快排时如果只盯着教科书里的那十几行代码会对“工业级排序到底长什么样”缺乏概念。8.2 Java和Python的内置排序快排不是唯一答案Java的Arrays.sort在基础类型上用双轴快排Dual-Pivot QuickSort在对象类型上用TimSort。双轴快排的意思是同时选两个基准把数组分成三个区域小于基准1、介于基准1和基准2之间、大于基准2。这实际上把三路快排的思想从“等于区域独立”扩展成了“两个基准划三段”减少了划分时的比较和交换次数。Python的sorted底层是TimSort这个算法吸收了归并排序和插入排序的优点特别擅长处理实际数据中常见的有序片段。它和快排没有直接血缘关系但它的存在提醒我们一件事工业级的排序选择从来不是“哪个算法理论最快”而是“哪种策略对这堆真实数据最稳、最快”。8.3 从库函数反推快排的工程进化路线如果你把各语言库函数的实现叠加起来看能复盘出一条清晰的工程演进路线第一步纯快排能跑但脆弱第二步改进基准选择消除有序输入的退化第三步小数组切换插入排序降低递归开销第四步三路划分/双轴处理重复元素第五步最坏情况监测必要时转堆排保住性能下限。这条路线恰好对应了我们前面几个章节讲的每项技术。所以学快排时不要只抱着“基准选中间、递归一分为二”的简化模型。真正上生产环境时它是好几个优化技巧的组合体。9. 面试场景里的快排怎么讲才能让面试官觉得你真懂了9.1 手写快排的常见扣分点我在模拟面试里见过不少“背得很熟”的候选人手写快排时暴露出几个典型问题。第一个是把递归写成死循环。常见于边界条件写错比如递归调用quick_sort(arr, low, p)而不减1导致基准元素反复出现在下一轮子数组中永远排不完。第二个是原地排序意识薄弱。有些人写着写着就开始创建新数组复杂度从O(log n)空间变成O(n)空间面试官问“额外空间复杂度是多少”时答不上来。第三个是说不清复杂度来源。能回答“平均O(n log n)、最坏O(n²)”但问为什么平均是O(n log n)时只憋出一句“因为分两半”没有提到递归树深度和多轮扫描的工作量关系。建议你准备这段时至少能清晰说出三句话每次划分确定一个元素的最终位置理想情况下递归树深度为log n每层合计扫描约n个元素所以平均是O(n log n)最坏情况下每次划分只确定一个位置递归深度变为n所以是O(n²)。9.2 快排的稳定性问题和“原地”含义快排是不稳定的排序算法。面试官如果问“快排稳定吗”答案是不稳定但你要能举出反例——比如数组里有两个相同值的元素一个在前一个在后分区交换时可能把在前的换到后面去。至于“原地”这个词它指的不是“不使用任何额外空间”而是额外空间和输入规模无关、保持常数级或对数级。快排虽然通过交换在原地完成元素重排但递归本身需要栈空间平均O(log n)。面试中如果说“快排是原地排序所以额外空间O(1)”就是不严谨的大概率会被追问到底。9.3 快排思想在面试题里的变形Top K和荷兰国旗问题快排的价值不只在排序本身它的划分思想经常被拿来解决别的题目。求第K大的元素Top K可以用快排的partition思想每次划分后看基准下标和K的关系决定去左半边还是右半边找平均时间复杂度O(n)比先排序再取第K个要快得多。这个技巧叫快速选择。荷兰国旗问题本质上就是三路快排的划分过程给定一个只包含三种值的数组把它们排成“一堆红、一堆白、一堆蓝”的形态。用三指针一趟扫描就能搞定这正是三路快排那一套。如果你在准备面试建议把快速选择和荷兰国旗问题都练一遍它们和快排是同一棵树上长出来的三个果。练完之后你再看快排会有一种“原来这几个知识点是通的”的感觉。10. 快排优化的落地顺序与我的最终建议如果你现在正准备把一个手写快排投入实战我建议按下面的顺序一步步加优化每加一步就测试一次不要一上来把所有技巧都堆进去。原因很简单优化越多代码越复杂出错的概率也越高。先保证正确再追求性能。第一步从Lomuto分区的基础版开始确保能在乱序数据上正确排序。第二步加三数取中修正有序输入的性能退化。这一步几乎零成本、收益巨大建议优先做。第三步加小数组切换插入排序阈值判断。这一步优化的对象主要是函数调用开销阈值取16左右。第四步如果数据集中重复元素特别多或者你无法预估输入分布换成三路快排。这一步对全相等、最小最大值区间很窄的数据集有奇效。第五步如果需要严格控制递归栈深度把尾递归优化也加进去用循环处理较大子数组。如果这些优化全做完你手上就是一个相当能打的排序实现。它和标准库的工业实现之间可能还有差距比如缓存优化、SIMD指令等但作为教学示例和面试答案已经远超绝大多数人的水平。最后分享一个我自己常对身边开发新人说的话排序算法别只背结论动手测一遍用数据说服自己。我当年学快排时也是花了一整个下午把各种优化版本挨个测了一遍看到有序数组把基础版拖垮、看到三路快排把全相等数组瞬间排完才真正理解“为什么工程实现要长成那个样子”。同一个算法教科书里是十几行代码工业实现是一整套防御性策略中间的跨度只有亲手踩过坑才能丈量出来。希望这篇长文能帮你少走点弯路。