排序算法是个老生常谈的话题但每次重新去看快速排序我都会发现一些以前没注意到的细节。很多教材把它放在“交换排序”一节里几句话讲完分治思想好像代码背下来就完事了。但实际到工程里快速排序远不止“选一个基准值把小的放左边、大的放右边”这么简单。递归深度怎么控制、重复元素怎么处理、最坏情况怎么避免、稳定性到底意味着什么这些问题在我自己做数据清洗和排序模块的时候都踩过坑。这篇就当是把我这些年写快速排序的经验、踩过的坑和优化思路完整梳理一遍给正在学数据结构、准备笔试面试、或者想在项目里手写排序逻辑的朋友做个参考。1. 快速排序到底在解决什么问题1.1 从无序到有序的朴素起点排序是所有算法问题里最基础的一类。想想日常场景通讯录按名字排、成绩单按分数排、购物车按价格排本质上都是在做同一件事——建立一个“顺序规则”然后把数据按照这个规则重新放置。快速排序解决的也是这个问题而且它在平均情况下是已知比较排序里相当快的一种。我刚接触排序的时候先学了冒泡排序和选择排序。冒泡的思想特别直观相邻两个比大小大的往后冒一趟下来最大的数就到末尾了。选择排序也直观每一趟找最小的放到前面去。这两个算法代码简单但问题也很明显元素比较次数太多数据量稍微上来一点耗时肉眼可见地增长。比如一万个整数冒泡排序要比较大约五千万次实在有点吃不消。快速排序的思路完全不同。它不追求每一趟把某个“最值”送到最终位置而是每一趟把整个数组划分为两半让左半边都小于某个数右半边都大于某个数然后对左右两边分别重复这个过程。这种“分而治之”的策略让它在大多数情况下能把问题规模快速减半因此平均时间复杂度只有O(n log n)。很多没有深入理解快速排序的人会把它当成一个“高级技巧”其实它的核心思想就是一句话把一个难问题拆成两个更容易解决的小问题然后递归地做下去。1.2 为什么选择快速排序而不是其他这里要先说清楚一点没有任何一种排序算法在所有场景下都绝对最优。快速排序的“快”是有条件的它依赖于基准值的选择和数据的初始分布。但即便如此它依然是工业界和学术界应用最广的通用排序算法之一。对比几种常见排序归并排序性能稳定无论数据怎样分布都是O(n log n)但它需要额外的O(n)空间来合并数组空间开销比快速排序大。堆排序空间复杂度是O(1)理论上也很优但它的实际常数比较大而且对缓存不友好访问序列跳来跳去在真实硬件上反而没有快速排序快。插入排序在数据接近有序时表现极好但数据量大且乱序时会退化成O(n²)。快速排序把这些优势综合起来平均情况下速度极快、不需要额外大块内存、对缓存比较友好。这也是C语言标准库的qsort、很多编程语言内置排序算法都选择以快速排序作为基础思路的原因。当然快速排序有一个致命弱点如果基准值选得不好它会退化成O(n²)。这也是我后面要花大量篇幅去讨论的部分。可以这么说快速排序的设计核心不在于“快”而在于“避免变慢”。2. 核心思想拆解分治和基准值2.1 一趟划分到底做了什么快速排序的每一趟操作可以理解成“选一个裁判然后把所有人与裁判比较站到裁判的左右两边”。这个裁判就是基准值。不过需要特别注意一趟划分执行完之后基准值本身已经位于它最终应该在的位置上。也就是说它左边的元素都比它小右边的元素都比它大但左右两边内部仍然是无序的。接下来要做的就是分别在左半部分和右半部分重复这个过程。举个例子给定数组[5, 3, 8, 1, 9, 2, 7]如果我们选5作为基准值一趟划分后可能变成[3, 1, 2, 5, 8, 9, 7]也可能变成[2, 3, 1, 5, 7, 8, 9]。具体结果取决于分区算法的实现方式但有一点是确定的5到了索引3的位置它左边全是小于5的右边全是大于5的。此时5在整个数组中的位置已经不会再变了。然后对[3, 1, 2]和[8, 9, 7]继续做同样的事情直到子数组长度为0或1排序就完成了。这里有一个初学者容易误解的地方划分过程并不保证左右两边的元素是“有序”的只保证“相对大小”正确。比如左边可能有[2, 1, 3]2在1前面但2大于1这在全局排序里是允许的因为后续递归会把左边排好。理解这一点比记住代码更重要。只要每一趟都能确定一个元素的最终位置递归下去所有元素最终都会被放到正确的位置。2.2 基准值选得好效率差很多基准值的选取直接决定了快速排序的效率。理想情况下每一趟划分都应该把数组均匀分为两部分这样递归树的深度就是log₂n每一层做大约n次比较总复杂度就是O(n log n)。但如果基准值恰好是每趟的最小值或最大值那么划分之后一边是空数组另一边是n-1个元素的数组问题规模每次只减少了1。这种情况下递归深度变成n总比较次数是n (n-1) (n-2) ... 1也就是O(n²)。这个退化在已排序数组上特别容易发生如果你每次都取第一个元素当基准值而数组本来就是升序排列的那么每一趟都会把最小的元素挑出来剩下的全部堆到右边算法彻底变成“慢速排序”。解决思路主要有三种。第一种是随机选取基准值从概率上避免最坏情况。第二种是三数取中取数组左端、中间、右端三个数的中位数作为基准值这样即使数据基本有序也能大概率选到一个比较“居中”的值。第三种是在极端情况下引入其他排序策略比如当递归深度超过某个阈值时改用堆排序这就是后来一些工业级排序算法里提到的“内省排序”思想。我对三数取中的评价是实现简单、效果稳定日常使用基本够用。随机化选基准值虽然理论上更好但在真实场景中会有随机数生成的开销而且对某些可复现的实验场景不友好。如果面试或者写练习题三数取中是性价比最高的选择。后面给出代码的时候我会详细展示。2.3 递归边界和终止条件任何一个递归算法都必须考虑“什么时候停下来”。快速排序的递归终止条件有两个层面一是子数组长度为1或0显然不需要再排序二是当子数组长度小于某个阈值时不再递归直接改用插入排序。第二点是很多工程实现里常见的优化我一开始写代码时也想不明白为什么都“快速排序”了还要用插入排序这种简单算法后来才意识到递归调用的开销是真实的函数调用、压栈、返回都是有成本的。当数组被切得很小的时候元素已经基本接近有序插入排序在近有序数组上性能极好而且它是稳定算法常数极小。所以很多标准库的实现里都会在n小于某个阈值一般是16到32时切换到插入排序。这里有一个细节插入排序的“近有序”优势只有在数组规模小、逆序度低的时候才能体现。如果你把阈值设得太大比如100那么每个子数组里虽然接近有序但还是有部分乱序插入排序的时间反而可能比快速排序继续递归更慢。我自己测试下来阈值设在16左右是比较合适的数据量小但也能发挥插入排序的优势。这个值其实不算关键参数不同机器、不同编译器可能有差异但大方向是明确的。3. 手写实现与关键细节3.1 基础版经典Hoare分区很多教材上写的快速排序用的是Lomuto分区方案代码短容易理解。但我更推荐先掌握Hoare分区因为它的交换次数更少在重复元素多的时候表现也更稳定。Lomuto分区是用一个指针扫描数组把小于基准值的元素往前面换Hoare分区则是从左右两端同时向中间扫描找到左边大于等于基准值和右边小于等于基准值的元素然后交换。先看一个我常用的基础版本分区函数用Hoare思路def quick_sort(arr, low, high): if low high: return pivot arr[(low high) // 2] i, j low, high 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 quick_sort(arr, low, j) quick_sort(arr, i, high)这个版本里pivot取的是中间位置的值。注意这里用的是arr[i] pivot和arr[j] pivot而不是或。这么做的原因是避免左右指针在等值元素上来回交换导致死循环。当遇到与pivot相等的元素时i和j都会停下来经过一次交换后等值元素被分到两侧整体还是平衡的。这个细节如果我当初没踩过坑可能到现在也不会特别注意。Hoare分区的一个重要特点是一趟划分结束后pivot不一定位于i和j相遇的位置而是可能在左半部分或右半部分也可能就在中间某个地方。因此递归调用时左区间是[low, j]右区间是[i, high]而不是像Lomuto分区那样用[low, pivot_index-1]和[pivot_index1, high]。初学者很容易在这里写错把边界搞混导致无限递归或遗漏元素。我的建议是先用小数组手动模拟一遍整个流程把每个变量值写下来再对照代码看递归边界基本就不会错了。3.2 改进版三数取中 小区间插入排序基础版在绝大多数情况下已经足够快但为了让排序在各种输入下都有稳定表现我会加两个优化三数取中和小区间插入排序。三数取中需要先写一个取中位数的逻辑可以用比较交换实现def median_of_three(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] # 把中位数放到 high-1 位置作为基准值 arr[mid], arr[high - 1] arr[high - 1], arr[mid] return arr[high - 1]这个函数返回基准值同时把它交换到数组靠近右端的位置这样后续分区时只需要处理[low1, high-2]区间内的元素减少了一次不必要的比较。注意这里的边界处理如果数组长度很短high-1可能越界所以需要判断high - low 1是否大于某个阈值。在实际代码中这一步往往和小区间插入排序配合使用整体流程更清晰def quick_sort_opt(arr, low, high): while high - low 1 16: pivot median_of_three(arr, low, high) i, j low 1, high - 2 while True: 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 else: break arr[i], arr[high - 1] arr[high - 1], arr[i] # 对短的子数组使用迭代方式处理长的递归 if i - low high - i: quick_sort_opt(arr, low, i - 1) low i 1 else: quick_sort_opt(arr, i 1, high) high i - 1 insertion_sort(arr, low, high)这里我还做了一个小优化把递归改成“一半递归一半迭代”。方法是对较短的子数组递归调用较长的子数组则通过更新low或high继续循环处理。这样可以有效减少递归深度避免极端情况下栈溢出。虽然这个版本的代码比基础版复杂一些但理解了思路之后你会发现每一步都有它的理由。3.3 参数分析和复杂度推导快速排序的时间复杂度分析是数据结构课程的重点。先说结论平均时间复杂度O(n log n)最坏时间复杂度O(n²)最佳时间复杂度O(n log n)空间复杂度O(log n)到O(n)不等取决于递归深度和是否做了尾递归优化。平均复杂度的推导方式有好几种最直观的是看递归树。每一层划分会把n个元素处理一遍做n次比较而递归树的深度在“平均情况”下是O(log n)所以总的比较次数是O(n log n)。更严谨的做法是假设每个元素被选为基准值的概率相等然后推导期望比较次数最终会得到约1.39n log n的常数因子。这个1.39是什么意思就是说快速排序平均要比理论最优比较次数多约39%的比较操作。虽然看起来“不完美”但因为这个常数因子很小实际运行速度依然很快。空间复杂度要特别说一下。递归调用本身需要栈空间每一层递归需要保存一些局部变量和返回地址。如果划分均匀递归深度是O(log n)如果每次划分都严重不均衡递归深度会达到O(n)。这也是为什么需要三数取中和递归深度控制的原因——本质上是为了把空间复杂度控制在O(log n)级别避免在排序几十万条数据时直接爆栈。还有一个值得关注的概念比较排序的下界是O(n log n)。这个结论来自于决策树模型n个元素有n!种排列方式而每次比较只能产生两种结果所以至少需要log₂(n!)次比较根据斯特林公式这个值是O(n log n)。快速排序在平均情况下能达到这个下界的量级说明它是一个渐进最优的比较排序算法。当然如果数据规模很小插入排序或选择排序可能更快因为常数更小。这也是为什么工程实现中普遍使用“混合排序”的思路。4. 实操过程中踩过的坑4.1 递归深度和栈溢出我自己第一次用快速排序处理一个几十万条记录的数组时程序直接崩溃了。当时第一反应是怀疑数组索引越界查了半天才发现是递归深度过大栈空间不够用。那次的输入是几乎已经排好序的数据而我的代码用的是固定取第一个元素作为基准值。每一趟划分都只去掉最小的那个元素递归深度直接到了几万层不崩才怪。解决这个问题有两条路。一是优化基准值选择避免最坏情况发生二是改造递归结构比如前面提到的“半迭代半递归”让递归深度始终保持在O(log n)。从工程角度看两条路最好一起做。另外如果你用的是C/C这类语言还可以考虑设置更大的栈空间但这不是根本办法。根本办法还是要让算法本身不依赖“碰运气”才能跑得好。我在实际编码中还会加一个防御性判断如果递归深度超过某个阈值比如log₂n×2就切换成堆排序。这种思路在很多现代标准库的排序实现里都能看到它保证了即使数据分布极端算法也能在O(n log n)时间内完成。4.2 重复元素与分区退化另一个经典坑是数组里重复元素特别多。比如有一个数组全是同一个值按基础版快速排序的逻辑每个元素都等于pivot。如果用arr[i] pivot这种写法i指针一路扫到头j指针一路扫到底一趟下来啥也没分区等于没排序但递归调用还继续发生最终复杂度爆炸。我的改进办法是把等值元素也交换到两侧并且让左右指针在遇到等于pivot的值时都停下。这样一趟划分后等值元素会被比较均匀地分到两边子问题规模能有效减半。更进一步的做法是使用三路快排。三路快排把数组分成三个区域小于pivot、等于pivot、大于pivot。一趟划分完成后中间区域已经全部是最终位置不需要再递归处理。这种算法在处理大量重复元素时性能提升非常明显可以降到接近O(n)的复杂度。下面是三路快排的一个核心分区片段def quick_sort_3way(arr, low, high): if low high: return pivot arr[low] lt low # arr[low..lt-1] pivot gt high # arr[gt1..high] pivot i low 1 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)这个写法是从左到右扫描当前元素比pivot小时把它和小于区的下一个元素交换扩大小于区比pivot大时把它和大于区的前一个元素交换保持未知区相等时直接跳过。三路快排比普通双路快排代码上多一点但面对重复数据时优势巨大。在Java的DualPivotQuicksort实现里对各种情况都做了精细处理三路划分也是其中很重要的一个思路。4.3 快排的不稳定性到底意味着什么稳定性是指如果两个元素的值相等排序后它们的相对位置是否保持不变。快速排序是不稳定的。举个例子数组里有两条记录key都是5第一个5在原数组的前面第二个5在后面。排序后这两个5的相对位置可能颠倒。这在排序普通整数时无所谓因为整数本身没有“区分度”。但在排序对象是结构体、元组或者带有多字段的记录时稳定性可能就很重要了。比如你有一组订单先按金额排过一遍现在想再按时间排序如果排序算法不稳定前一次金额排序的结果可能被完全打乱。我自己的经验是在工程中如果需要稳定排序直接使用归并排序或者稳定版本的混合排序而不是强行给快速排序加稳定性。给快速排序加稳定性的代价是引入额外空间和更复杂的元素移动逻辑性能提升不明显代码可读性却大大下降。这个场景下“稳定性”比“速度”更重要所以不必死磕快速排序。当然如果数据量不大直接用带索引的辅助数组也可以实现稳定效果但那是另一种思路了。4.4 分区边界的经典错误边界错误是手写快速排序最常见的bug来源之一。我的一个朋友在我面前调试了很久问题出在递归调用时子数组的区间范围搞错了。Hoare分区后左区间和右区间的划分点不是固定的基准值索引而是左右指针停止的位置。很多教程里写的代码看起来很简单但如果你直接照着抄很容易把low和j、i和high的对应关系搞混。我建议自己写一个测试函数对随机数组、升序数组、降序数组、全相等数组分别跑一遍然后和Python自带的list.sort()结果比对。这个方法虽然朴素但真的能有效抓出边界bug。5. 快速排序在真实场景中的应用5.1 自己实现库函数时应该注意什么在应用层写代码很多时候不需要重复造轮子直接用语言内置排序就好。但如果你的项目有特殊需求比如不能修改原始数据、需要自定义比较器、需要按多个key倒序排序、或者数据规模特别大需要外部排序这时候手写或定制排序算法就有用武之地了。我参与过一个模拟项目需要给几十万条带有权重信息的数据按权重排序同时还要把排序结果实时推送到展示层。因为数据源是流式的内存里始终保留全部数据不现实所以不能用普通的全量快排。最后我采取的是“分块排序加归并”的策略先按批次对小块数据用快速排序排好再把多个有序块合并成最终结果。这个过程中快速排序的优势在于它排序小块数据时速度极快、内存占用低非常适合作为外部归并排序的内层排序器。如果改成归并排序做内层排序速度也不慢但会多消耗一份拷贝空间。还有一个场景是嵌入式或资源受限环境。在这种环境里内存非常宝贵归并排序需要的额外O(n)空间往往无法接受而快速排序只需要O(log n)的栈空间所以成为默认选择。当然要配合三数取中或随机基准来防止最坏情况。我在某公司做内部工具的时候处理过一段C代码就是给一个单片机固件里的数据数组排序。那上面没有标准库可用我手写了一个比较紧凑的快排为了控制栈深度把递归调用改成了手动栈模拟效果很理想。5.2 内置排序里快速排序的身影很多现代语言的排序并非单纯一种算法。以Java的Arrays.sort()为例对于基本类型数组它使用双轴快排对于对象数组则使用TimSort一种改进的归并排序。C语言的qsort虽然名字带“q”但实现细节由各平台自行决定很多平台的实现其实是内省排序。内省排序会在快速排序递归深度过深时切换成堆排序保证最坏情况仍然是O(n log n)。Python的list.sort()和sorted()使用TimSort它充分利用了数据中已有的有序片段在真实数据上表现非常出色。知道这些有什么意义如果你只是调用内置排序那不需要了解内部细节。但如果你需要对算法进行评测、优化或移植了解这些实现差异能帮助你判断瓶颈在哪里。比如你发现在Python里排序一个已经基本有序的列表很快那是因为TimSort检测到了有序段而非快速排序的功劳。如果你在一个自研系统中照抄快速排序却没有考虑到初始数据的连续有序性性能可能适得其反。所以快速排序不是万能钥匙但它作为基础算法是理解其他高级排序的重要跳板。6. 我这几年用下来的最终建议如果要说我个人的体会那就是快速排序要“学它的思路而不是背它的代码”。思路的核心是分治和划分只要掌握了这两点不管是写双路快排、三路快排还是内省排序你都能根据自己的数据特征去调整。我在面试中见过很多人能把基础快排代码默写出来但问到“如果数据全相等会怎样”就答不上来也有很多人知道会有退化问题却说不清楚具体怎么改。这说明大家普遍缺少“从原理出发去推演问题”的训练。我给自己的练习方法很简单准备几种特殊数据比如随机数、升序、降序、全相同、有大量重复、近乎有序然后逐个用自己写的排序跑一遍记录比较次数和运行时间。不要只拿随机数测试因为那样通常测不出问题。我每次手写排序算法后都会用这组数据自测很多边界问题都是这么暴露出来的。最后做一个小的扩展如果你的数据是字符串、对象或者自定义类型别把快速排序硬往上套先想清楚比较规则和稳定性要求。快速排序擅长的是“通用快速排序”不是“什么都能排”。遇到这种场景我会优先看一下系统自带的排序能不能满足不能的话再根据数据类型选择归并、堆排序或者定制版本。排序算法没有银弹但快速排序绝对是最值得深入理解的那个。希望通过这篇梳理你能从“默写代码”进阶到“按需设计”的阶段。