我一直觉得分治算法是算法入门里最值得花时间啃的一块硬骨头而快速排序则是检验你是否真正理解分治思想的试金石。这堂课编号420光听名字平平无奇但等你把它彻底吃透会突然发现以前觉得神秘的递归、复杂度分析、边界处理一下子都串起来了。快速排序不是那种“背下来就完事”的模板代码它更像一把万能钥匙既能帮你打开面试算法题的大门也能让你在实际项目中写出高性价比的排序逻辑。这篇文章适合刚学完基础语法、正在刷算法题的人也适合用过排序却从没关心过内部机制的老开发。我会从分治思想的底层逻辑讲起逐步拆解快排的实现细节、复杂度来源、优化技巧顺便把常见坑和排查思路一次性说清楚。内容本身不依赖特定编程语言我会用可读性优先的伪代码和Python示例来说明你完全可以移植到自己的技术栈里。1. 分治算法快速排序背后真正的主角1.1 分治的三个步骤到底在做什么很多初学者学快排时一上来就盯着“选一个数、把小于它的放左边、大于它的放右边”这个动作看结果看半天只记住了一个shell不知道整个算法为什么快。实际上快速排序只是分治算法的一种具体应用它的骨架是套路非常清晰的三步分解、解决、合并。分解是把一个大问题切成若干个结构相同、规模更小的问题解决是递归地对这些小问题做同样的事情直到小到可以直接处理合并是把子问题的结果拼回原问题的答案。听起来跟套娃一样但不同算法对这三步的侧重点完全不同。快排有意思的地方在于它的“合并”几乎是透明的真正费劲的是“分解”这一步也就是分区操作。而归并排序则相反分解很轻松合并时才需要额外开数组去归并。这个差异直接决定了两种算法的空间复杂度和常数性能。我见过很多人学完归并再学快排脑子里会下意识地问“那我分区完之后是不是还要做点什么把左右两边拼起来”答案是不需要。因为分区完成的一瞬间枢纽元素已经落在了它最终该待的位置上左右两边天然就是有序的雏形。这理解一旦打通写代码的时候思路会清爽很多变量名也敢放心地起成pivot、left、right了。1.2 为什么分治能把O(n²)减成O(n log n)这里的关键在于子问题规模的收缩速度。冒泡排序每处理完一个元素只是把某个元素送到正确位置但下一轮还是要扫几乎同样多的数据所以总工作量是n (n-1) (n-2) …约等于n²/2。而快排的每一层递归都会把所有元素切分成两堆每往下走一层虽然要处理的元素总数仍然是n但每个子问题的规模都在变小并且这些子问题能并行地看成“互不干扰的批处理”。我们可以用一棵递归树来看它第一层只用处理n个元素的划分第二层左右两个子数组各处理n/2总共还是n第三层处理四个n/4加起来依然是n。树一共有多少层呢如果每次划分都比较均匀树的深度就是log₂ n。所以总工作量是n乘以树的深度也就是O(n log n)。这正是分治算法最迷人的地方它没有减少每一层要干的活但通过控制递归层的深度把幂级的复杂度压缩成了对数级。我在实际讲课时喜欢用一个类比你想在一堆体检报告里找某一份如果全部摊开一张一张翻运气好翻第一张就中运气差翻到底平均也要翻一半。但如果按姓氏分堆先锁定一个部首区间再不断细分每次都能排除掉一大半效率天差地别。快排比冒泡快的原因就是这种“每次排除更多”的思维而不是因为它做了什么更高端的运算。1.3 快排在分治家族里的独特定位分治家族里最著名的两个成员就是快排和归并排序。归并排序的重心在合并它把数组劈成两半递归排好之后再用一个临时数组把两条有序序列缝合起来。归并是稳定的而且各种数据下表现都很稳定但它的缺点是需要O(n)的额外空间这在内存受限的环境里很让人头疼。快排则把重心放在划分上它不需要合并属于原地排序额外空间主要来自递归栈。从理论上讲快排的平均效率跟归并一样都是O(n log n)但它的常数项更小Cache命中率更高所以在大多数通用场景里快排都比归并跑得快。当然代价在稳定性普通快排是不稳定的遇到已经有序、重复元素极多的输入时还可能退化。理解这两种排序的分工推荐排序时心里才会有底——要稳定内存又够选归并要求时间和空间平衡选快排。2. 快速排序的核心细节从主流程讲到分区实现2.1 三步走先把主循环的框架定下来我们可以把快排的主流程写得非常干净总共就那么几行function quickSort(nums, low, high): if low high: return pivotIndex partition(nums, low, high) quickSort(nums, low, pivotIndex - 1) quickSort(nums, pivotIndex 1, high)你仔细观察会发现分区函数返回的pivotIndex既是枢纽元素在排序后数组里的最终位置也是左右递归的分界点。只要分区函数正确枢纽元素左边全都比它小右边全都比它大那它就再也不用参与后续任何递归了。写快排最大的心理障碍就在这里很多人总觉得递归到最后会发生什么神奇的事情其实每一个元素都会在某一轮分区里被选为桩元素一旦被选定它的一生就结束了。主循环里有个很容易出错的点边界条件到底是low high还是low high递归左区间是(low, pivotIndex - 1)还是(low, pivotIndex)。我见过不少代码在只有一个元素或者两个元素时陷入死循环根源就在于边界没有统一。这里我给个特别实用的经验你固定使用闭区间[low, high]当low high时终止分区返回的是“枢纽最终落点下标”那么递归时左区间一定写到pivotIndex - 1右区间写到pivotIndex 1。一旦定下来整个代码都不用再猜。2.2 两种主流分区算法Lomuto与Hoare先讲Lomuto分区它最好理解思路像打扑克时整理手牌。选最后一个元素当pivot用一个游标i记录“小于pivot的分区边界”然后让j从头走到尾遇到比pivot小的就让i先前进一位再把i和j的元素互换。等j走完把pivot和i1位置的元素对调返回i1。function partition(nums, low, high): pivot nums[high] i low - 1 for j low; j high; j: if nums[j] pivot: i i 1 swap(nums[i], nums[j]) swap(nums[i 1], nums[high]) return i 1Lomuto每个元素只遍历一次代码极其清晰特别适合教学和面试手写。可它有个小毛病当数组里有很多重复元素或者数据已经接近有序时分区结果容易失衡。再讲Hoare分区它是快排发明者最初用的方案。两个指针一个从左往右找比pivot大的一个从右往左找比pivot小的找到后就互换直到两个指针相遇。这个方法最经典的版本是把第一个元素或中间元素当pivot但注意返回的索引只是某个边界而不是pivot的最终位置递归时左区间要包含这个边界也就是(low, p)右区间是(p1, high)。function partition(nums, low, high): pivot nums[low] i low - 1 j high 1 while true: do i while nums[i] pivot do j-- while nums[j] pivot if i j: return j swap(nums[i], nums[j])Hoare的交换次数通常比Lomuto少得多连相等的元素也会被交换走所以对重复数据的抗性更强实际运行速度明显更快。我第一次从Lomuto跳到Hoare时发现性能直线上升但调试时也因为返回值含义不同栽过跟头。建议你初学时分清这两者写代码前先问自己用的是哪种分区然后再决定边界怎么写。2.3 不用递归的迭代版本怎么写递归版本虽然清爽但遇到特别大的数组时可能栈溢出。迭代版本是用显式栈模拟递归把尚未排序的区间下标压进栈里循环弹出区间并处理。function quickSort(nums, low, high): stack [(low, high)] while stack not empty: (left, right) stack.pop() if left right: continue p partition(nums, left, right) if p - 1 left: stack.push((left, p - 1)) if p 1 right: stack.push((p 1, right))有一个优化小技巧值得记一下弹出一个区间后比较左右子区间的长度先把较短的区间压栈再处理较长的区间。这样可以保证栈内最多只积累O(log n)个区间进一步降低内存压力。你可能会问值不值得我的看法是如果面试官追问“如果数据量巨大递归爆栈怎么办”这一手可以直接展示你的工程意识。3. 手动演算一遍排序全过程3.1 一步步追踪数据的流向光看不练很容易产生“我懂了”的错觉最好手动跑一遍。就拿[3, 6, 2, 8, 1, 9, 5]举例我们选最后一个元素5作为pivot。开始时左边比5小的会陆续被换到前面去3已经比5小6太大先不动2比5小跟6互换8太大不动1比5小跟6互换。最后数组变成[3, 2, 1, 6, 8, 9, 5]把5跟6互换得到[3, 2, 1, 5, 8, 9, 6]。此时5的左边有3、2、1右边有8、9、6第一轮分区完成。接着递归处理左区间[3, 2, 1]选1当pivot结果是1不动左区间变成[1, 2, 3]右区间[8, 9, 6]选6当pivot变成[6, 9, 8]。再递归地处理每个剩下来的单元素区间最终得到[1, 2, 3, 5, 6, 8, 9]。这个过程看起来平平无奇但其中有个关键认知每一轮分区至少把一个元素放到正确位置而且这个位置是永久性的。所以快排的平均复杂度不可能差到哪里去因为每一层递归都在“落实”一批元素。3.2 最坏情况、平均情况与最好情况的复杂度推导最好情况是每次分区后左右两边长度相等递归树深度为log n总工作量O(n log n)。最坏情况是每次选中的pivot都恰好是最大或最小元素比如对一个已经升序的数组选最后一个为pivot每次只能分出长度n-1和0两个区间。递归树退化成一条链深度变成n总工作量就是n (n-1) (n-2) …即O(n²)。平均情况怎么算精确推导要用概率期望但有个直觉算法任意选取枢轴它落在某个位置的概率是均等的。将每次划分后左右子问题的期望规模表示成递推关系解出来仍然得到O(n log n)。为了防止面试官追问你要记住关键结论快排的平均复杂度是O(n log n)最坏是O(n²)最坏局面产生的原因是选枢轴的策略太差而不是算法本身有问题。3.3 稳定性问题为什么快排不是稳定排序稳定排序的意义在于相等元素的相对顺序不变。快排不稳定的原因在分区时会发生跨距离交换比如[2(第一个), 2(第二个), 1]用第一个2当pivot经过交换后两个相等2的相对位置很可能颠倒。这个细节在日常工作中影响不大但在数据库排序、多关键字排序场景下稳定性还是很重要。如果你必须用快排的O(n log n)平均性能又想要稳定性可以额外记录元素原始下标作为第二关键字但这会牺牲一部分空间和性能。工程上更常见的做法是干脆选归并排序或稳定版本的变体比如通过特定分区技巧让相等元素保持顺序只是实现复杂度和常数开销都会上升。4. 性能调优与工程落地实践4.1 优化枢轴选取三数取中与随机化快排最怕有序数组尤其是已经升序的数据。有人会说那选中间元素不就行了但中间元素在分布极端时也会失效。工程上最常用的两个手段随机选择pivot或者从low、mid、high三个位置取中位数。三数取中的效果更稳定因为它能有效避免最大或最小值被选中让数组在大多情况下都能切成两半。三数取中实现起来很简单function choosePivot(nums, low, high): mid low (high - low) // 2 if nums[low] nums[mid]: swap(nums[low], nums[mid]) if nums[low] nums[high]: swap(nums[low], nums[high]) if nums[mid] nums[high]: swap(nums[mid], nums[high]) return mid返回mid后通常把它跟最后一个元素换位再走Lomuto分区或者跟第一个元素换位再走Hoare分区。这套组合在很多算法竞赛代码里都是标配。4.2 小数组切换到插入排序临界点怎么定快排在递归到只剩很少元素时递归调用和分区的固定开销反而超过插入排序的成本。因为插入排序在小规模数组上局部性极好几乎就是顺序比较加移动。所以很多工业级实现都会加一个阈值判断当数组长度小于某个值时直接用插入排序而不是继续递归。阈值该设多大我在实践中试过8到24之间差别都不算大一般取10到20。太小的阈值优化不明显太大的阈值又会让插入排序在相对大的区间上做一些不必要的移动。一个简单的适配方式是在快速排序的递归开头加一句if high - low 16: insertionSort(nums, low, high); return。这样改完整体的最坏复杂度依然是O(n²)但常数显著下降实测对数百万规模的乱序数组提速能达到20%左右。4.3 三路快排专治重复元素当数组里有大量重复元素比如几百万个1夹杂少量其他数字普通快排会反复处理那些等于pivot的元素效率非常难看。这时可以考虑三路快排思路来自荷兰国旗问题把区间分成小于pivot、等于pivot、大于pivot三部分。function partition3(nums, low, high): pivot nums[low] lt low gt high i low while i gt: if nums[i] pivot: swap(nums[i], nums[lt]) lt i elif nums[i] pivot: swap(nums[i], nums[gt]) gt-- else: i return lt, gt主流程随后只需要递归处理(low, lt-1)和(gt1, high)两段中间那段直接跳过。这种写法在处理大量重复值时优势巨大很多语言标准库里快排的退化场景也会使用它。我在处理用户行为日志里的枚举值字段排序时实测三路快排比普通快排快了三倍以上。4.4 什么时候不应该用快排快排不是万能的。数据量非常小只有几十个元素时直接插入排序更省心需要稳定排序时优先考虑归并数据几乎已经有序时虽然快排有三数取中兜底但插入排序或者更专业的自适应排序常常更快。内存极度受限连递归栈都不能接受循环实现也许够用或者干脆选原地堆排序。5. 常见问题与排查技巧实录5.1 分区索引边界错乱导致死循环或越界最常见的坑是Lomuto里返回i而不是i1。如果你的循环写法是if nums[j] pivot且返回的是i在有一堆相等元素的情况下会出现极端失衡。排查这类问题时不要只靠肉眼直接准备一个长度3到5的重复元素数组打印中间状态。我建议的排查套路在每次递归调用前输出当前区间low、high、pivotIndex以及数组内容。如果发现连续两次递归区间长度没变基本可以断定是pivotIndex边界问题把某个元素重复处理了。用纸笔手动演算三五个元素比任何调试器都高效。5.2 递归深度过大导致栈溢出栈溢出常见于最坏情况退化比如每轮只切掉一个元素递归深度达到n。解决思路有三个方向第一采用随机化或三数取中从源头避免最坏情况第二把递归改成迭代加显式栈第三只对较短的子区间递归较长的子区间用循环处理也就是尾递归优化的思路。工程上我会优先做三数取中因为它几乎不会让最坏情况发生。如果你在极端环境下还是要彻底避免递归那就按前面给的迭代版本改压栈时加一个长度判断。5.3 全相等数组和逆序数组的表现不同为什么全相等数组遇到Lomuto分区时返回的pivotIndex是high递归退化成O(n²)但三路快排只需一轮就能把所有元素都放到等于段。逆序数组面对选择最后一个元素当pivot的普通快排也是O(n²)如果配合三数取中选到最大值其实问题不大。这些退化行为是最容易被面试官拿来加问的点体现出你对算法本质理解的深度。我记得当年面试时被问到一个很刁钻的问题“如果全是相同元素你的快排会退化吗”当时我只知道答案会退化但说不出为什么。后来动手分析才发现问题出在“比较时用还是”上三个不同的等值条件会导致三种不同行为。自此之后我再也不敢小觑这些细节。5.4 关于稳定性、最坏情况、三分区的追问清单如果你在准备面试除了写代码还要能回答这几个问题为什么分区时要加等号为什么Hoare返回的不是枢轴的最终位置三路快排的中间段需不需要再排序原地分区和额外数组分区的性能差距在哪里我的回答思路是等号决定了相等元素的走向影响退化程度Hoare返回的是两个分区相遇点不代表枢轴落点所以递归区间写法完全不同三路快排中间段已经全部相等不需要再递归原地分区省空间但交换顺序不稳定额外数组分区好理解但多一次拷贝。写在最后的一点个人心得快速排序是我在几十个排序算法里复习得最频繁的一个每次重写都有新体会。它最值得学习的不是那几行代码而是它背后“如何把一个大问题拆成多个不需要合并的小问题”的思维方式。我后来处理并发任务拆分、数据库分片甚至写文档大纲时都会有意无意地使用分治的思路其实根子都是当年啃快排时打下的底子。如果你正处于初学阶段建议你干一件有点笨但极有效的事用手写的方式模拟快排处理一副扑克牌每一步都在纸上画出分区结果。多做几次你会慢慢找到手感知道选哪个当pivot以及什么时候切插入排序。等你能闭着眼把Lomuto和Hoare都默写出来再对比一下两者的差异基本上这个算法就算透彻了。最后分享一个我的小习惯写任何需要排序的代码前先问自己三个问题——数据量多大、重复元素多不多、容不容许不稳定。把这三个问题想清楚再决定用快排还是别的排序。很多线上性能问题本质上不是排序算法慢而是选错了算法。
