快排这个名字几乎所有写程序的人都听过。不管你是刷算法题准备面试还是在业务代码里对几万条数据做排序快速排序Quick Sort都是绕不开的一个核心算法。我在第一次接触快排时看递归代码整个人是懵的明明只有十几行却怎么都想不明白它凭什么能把一个无序数组给排好。后来自己一遍遍写、一步步调试又经历了若干次线上排序逻辑的性能排查才算是真正把这个算法吃透了。这篇文章就把我对快排的理解、踩过的坑、总结出的一些优化心得一次性讲清楚希望能帮你少走点弯路。这篇文章适合几类人正在学数据结构与算法的学生、准备大厂面试的求职者、写业务代码时想自己实现排序逻辑的工程师。读完你至少能收获快排的核心分治思想、基准数的选择逻辑、分区操作的底层细节、复杂度推导过程以及直接可用的优化版本代码和排错经验。1. 快排到底是什么一个排序界的常青树1.1 为什么是快排而不是别的排序排序算法有太多种选择排序、插入排序、冒泡排序、归并排序、堆排序……每种都有自己适合的场景。但在大多数编程语言的内置排序实现中快排或快排的变体往往占据核心地位。比如 C 语言标准库的qsort、Java 的Arrays.sort对基本类型其底层都采用了双轴快排或快排的改良版本。为什么偏偏是它关键在于快排在平均情况下拥有 O(n log n) 的时间复杂度而且常数因子非常小。什么意思归并排序也是 O(n log n)但归并排序需要额外的 O(n) 辅助数组来合并两个有序子序列堆排序虽然也是 O(n log n)但堆排序在实际运行中有较差的空间局部性——元素在数组里跳来跳去CPU 缓存命中率低。而快排是原地排序的它通过交换元素来实现分区不需要额外的存储空间缓存友好性也非常好。举个简单的类比。想象一个班级要按身高排队归并排序的做法是把所有人先分成两半各自排好后再把两排按顺序合并起来合并时需要借助一块新的空地站人。而快排的做法是随便挑一个同学做标准矮的站左边高的站右边然后左右两边各自再重复这个过程。整个过程不需要额外的“空地”效率自然高。1.2 快排的适用场景与需谨慎的场景快排擅长处理的是元素可随机访问的数据结构也就是数组。对于链表虽然也能做快排但随机访问基准数不方便分区操作要遍历链表效率明显不如数组。这时候归并排序反而是更自然的选择因为链表节点的合并不需要额外空间。另外当数据量非常小时快排的递归开销反而可能拖后腿。递归调用本身有栈帧分配和函数调用的成本再加上分区操作中的复杂逻辑在小规模数据上可能不如直接插入排序来得干脆。所以工业级的快排实现比如 Python 的 TimSort 虽然不是快排但类似思路通常会在数据量小于某个阈值比如 10~20时切换到插入排序。这个细节在后面优化部分我会展开讲。还有一类情况需要特别注意当待排序数据已经是接近有序或完全有序时如果基准数选得不好快排会退化到 O(n²) 的最坏情况。这个问题不是快排本身的“缺陷”而是基准数选择策略导致的极端情况后续有个专门的章节来分析这个问题和对应的解法。2. 核心思想拆解分治、基准与分区2.1 分治思路的精髓快排的核心思想其实是分治法Divide and Conquer。整体思路可以概括为“三步走”分解从待排序区间选择一个基准数pivot通过交换操作把小于等于基准数的元素放到它左边大于等于基准数的元素放到它右边。求解递归地对基准数左右两侧的子区间重复这个分解过程。合并因为所有操作都是原地进行子区间各自排好后整个数组自然就有序了不需要额外的合并动作。这第三个步骤和归并排序有本质区别。归并排序在“合并”这个动作上是大头快排则在“分解”这一步把工作全干完了。你可以这样理解快排每做一次分区操作就有一个元素被放到了它最终该待的位置上——这个被选中当基准数的元素它左边的全比它小右边的全比它大那它自己其实已经“归位”了。剩下的事情只是让左右两边的元素各自内部也达成这个状态。递归的终止条件也很直观当待排序区间只有一个元素或者没有元素时不需要做任何操作直接返回。这个条件写不好会出现数组越界或死递归后续讲边界问题时会专门强调。2.2 分区操作是怎么算出“最终位置”的分区partition是快排的灵魂也是写代码时最容易出错的地方。基本目标是给定数组和一个基准数把数组重新排列使得基准数左边的元素都小于等于它右边的元素都大于等于它然后返回基准数最终所在的下标。业内最常见的分区方法有两种Lomuto 分区法和 Hoare 分区法。先看 Lomuto它逻辑简单、代码好写适合教学但交换次数比 Hoare 多一些。核心思路是维护一个“慢指针” i它指向的是当前已确定“小于等于基准数”区间的末尾用另一个“快指针” j 遍历整个区间每当发现一个小等于基准数的元素就把它和 i1 位置交换然后 i 往前挪一步。这段代码看起来简短但这里有一个常见的理解误区为什么要“交换”而不是“直接覆盖”因为分区操作的前提是原地排序不能新建一个数组更不能丢失元素信息。交换才能保证每个元素都在数组中只是位置变了。Hoare 分区的思路不太一样它用两个指针一个从左往右找比基准数大的一个从右往左找比基准数小的找到后两个交换。这样做的好处是交换次数更少平均性能更好。很多标准库的实现都是 Hoare 的变体。但它初学时不太容易写对边界条件非常容易错比如while (arr[left] pivot) left和while (arr[right] pivot) right--的符号边界还有最后返回 left 还是 right 的问题差一个下标就会导致死循环或者漏排。2.3 基准选择最容易被忽略却最关键的一步很多教程讲快排时会直接说“选第一个元素当基准”这个说法教学上没问题但工程上隐患很大。如果待排序数组本身就是升序或降序排列选第一个元素当基准会使得每次分区都极度不均衡左边为空右边是剩余全部元素。这样一来递归深度变成 n时间复杂度退化成 O(n²)性能直接从“快排”变成“慢排”。常见的改进方案有三种随机选基准在区间内随机挑一个下标当基准。这个策略的好处是无论数据预先怎么排算法的最坏情况变成了一个概率问题几乎不会发生。工程上这种策略简单高效代码只需要加几行随机数逻辑。三数取中Median of Three取区间最左、最右、正中间三个位置的元素把中间值当作基准。这样可以规避“已经有序的数据”这种常见的最坏情况性能也比较稳定。很多工业实现采用这种方法。基于数据分布的自适应策略比如对大量重复元素走三路快排逻辑。这类方案更复杂属于进阶优化的范畴后面在优化章节里详细展开。基准策略实现难度优点不足之处固定第一个元素很低代码简单对有序输入退化严重随机选取低避免恶意输入有随机数生成开销三数取中中稳定性和性能平衡好对重复元素效果有限三路快排高海量重复元素性能极佳代码复杂度大幅提升3. 复杂度分析快排为什么快又在什么时候慢3.1 平均复杂度 O(n log n) 的直觉理解要理解快排的平均复杂度得看递归的结构。每次分区操作你要遍历整个区间做交换所以单次分区的代价是 O(n)。如果每次都能把区间对半分那递归调用的深度就是 log n总复杂度就是 O(n log n)。递归深度是 log n 这一点怎么直观理解一个长度为 n 的数组每次对半切切成大小为 1 的区间需要切 log_{2}n 次。每一层递归都处理了大约 n 个元素因为每一层的所有子区间加起来长度之和大约就是 n所以总的工作量是“层数乘以每层工作量”也就是 n log n。换句话讲快排相当于一遍一遍对整个数组做“扫视”但每一遍扫视的重点区间在不断缩小。第一遍扫整个数组第二遍扫两个一半的数组第三遍扫四个四分之一……这也解释了为什么快排通常都很快——它几乎不会做超过 log n 遍的“全量扫描”。3.2 最坏情况是怎么触发的最坏情况发生在每次分区都极端不均衡的时候。比如每次选到的基准数恰好是当前区间的最大值或最小值这样分区完一边是 0 个元素另一边是 n-1 个元素递归深度变成 n总时间复杂度变成 O(n²)1 2 3 … n等差数列求和。最经典的触发场景就是前面提到的“数据已有序固定选第一个元素当基准”。一个升序数组 [1, 2, 3, 4, 5]如果选第一个元素 1 当基准找到的位置。 后来我自己反复演练了很多次画图推演才算是真正理解了。说白了就是一组比较与交换的循环核心逻辑就一句话把比基准小的元素往左赶。4.2 Hoare 分区更少交换的进阶写法Lomuto 分区虽然好写但有一个缺点交换频率偏高。当数组元素较多时不必要的交换会影响效率。Hoare 分区的设计哲学是“两个指针相向而走”一个从左往右找大于基准的数一个从右往左找小于基准的数找到后两个数直接交换直到两个指针相遇。Hoare 实现代码如下def partition_hoare(arr, low, high): pivot arr[(low high) // 2] i low - 1 j high 1 while True: i 1 while arr[i] pivot: i 1 j - 1 while arr[j] pivot: j - 1 if i j: return j arr[i], arr[j] arr[j], arr[i]这里有个有趣的细节Hoare 分区返回的 j 并不是基准数所在的最终位置它只是“两个指针相遇的位置”。所以递归的时候左区间是[low, j]右区间是[j1, high]而不是像 Lomuto 那样用partition的返回值减 1。对比项Lomuto 分区Hoare 分区交换次数较多较少代码可读性更容易理解边界条件更复杂返回下标含义基准数最终位置左右区间分界点递归区间划分[low, pi-1] 和 [pi1, high][low, pi] 和 [pi1, high]4.3 三数取中与随机化打破最坏情况的两把钥匙要避免快排退化最基本的措施是让基准选择不依赖输入数据的初始顺序。三数取中是我个人最推荐的一种方案它兼具稳定性和代码可读性。思路很简单取区间的首、中、尾三个位置的元素把它们排序用中间值作为基准。选择中间值作为基准而不是直接选中间位置是因为中间位置的值可能恰好是最大值或最小值。三数取中策略相当于对三个样本做了个小排序把最大和最小的排除在基准候选之外。这样一来即使输入近似有序基准数至少不会差到极端。根据我个人的实践经验三数取中不需要写太复杂的排序逻辑三个元素的手动比较即可实现耗时极短。三数取中还有一个附带的好处在选基准的过程中可以顺带把首元素和尾元素做个小调整让首元素小于尾元素这对后续分区的稳定性会有一点微小的帮助虽然性能够用即可不必太纠结。随机化的思路同样有效。随机选基准几乎彻底化解了“恶意输入导致最坏情况”的风险因为即使输入是有序的随机选到的基准大概率在数组的中间位置附近。它的写法也非常简单只需要在算法开始前随机挑一个下标然后和首元素交换即可。4.4 小数组切换到插入排序摆脱递归拖累递归调用有开销包括函数栈帧的创建、销毁以及参数传递。当子数组的规模非常小比如只剩 10 个元素你对它继续做快排分区成本反而比直接做插入排序更高。工业界的做法通常是设置一个阈值当待排序区间长度小于这个阈值时改用插入排序Insertion Sort。为什么插入排序在小规模数据上表现好因为插入排序没有递归调用逻辑简单常数因子极小而且对于近乎有序的数据插入排序的交换次数趋近于零。在小规模数组上O(n²) 的复杂度实际运行开销完全在可接受范围内。我在实际工程里通常把阈值设为 16效果比较理想。更严谨的做法是对不同阈值做基准测试看哪个阈值在自己的数据规模上性能最佳。移植这个优化到递归代码中并不困难只需要在快排函数开头加一个判断即可。以下是一个结合了“三数取中 小区间插入排序”的完整实现这份代码我测试了多种输入场景稳定性较好可以作为后续开发中的基础模板。def quicksort_optimized(arr, low, high): if low high: return if high - low 1 16: insertion_sort(arr, low, high) return pivot_index median_of_three(arr, low, high) arr[pivot_index], arr[high] arr[high], arr[pivot_index] pi partition_lomuto(arr, low, high) quicksort_optimized(arr, low, pi - 1) quicksort_optimized(arr, pi 1, high)4.5 三路快排十万个重复元素的最佳应对如果数据集中有大量重复元素传统的二路快排仍可能遇到性能问题。比如一个数组有十万个元素全是一样的数值两次分区后会得到一块极短区间和一块极长区间递归不平衡的问题依然存在。三路快排3-Way Quick Sort专门解决这个问题它将区间分为三个部分——小于基准、等于基准、大于基准。等于基准的部分不需要再参与递归排序直接跳过。三路快排在处理大量重复数据时能达到 O(n) 级别的复杂度这是普通快排做不到的。其核心逻辑是在 Lomuto 基础上增加一个“等于区”的指针。每次遍历时如果当前元素小于基准就把它交换到左边区域等于基准就原地不动大于基准就交换到右边区域。一趟遍历下来数组被清晰地切成三段。在 Java 标准库的Arrays.sort中对基本类型的双轴快排实现也包含了类似三路划分的思想可见这种优化是工业级的演进方向。单靠固定基准的快排在存在大量重复数据的业务场景中可能慢得难以接受一旦切换成三路快排性能会提升一个量级。5. 常见问题与排查实录5.1 递归过深导致栈溢出快排用递归实现方便理解但递归深度过大时会撑爆栈空间。最容易触发递归过深的场景就是“数据有序 固定选首元素当基准”。我之前做过一个测试对 10 万条已经排好序的整数调用基础版快排程序直接报出 RecursionError。无论环境的栈空间大还是小这种极端情况都存在栈溢出隐患。解决思路有三个方向。第一个是采用随机基准或三数取中从根源上消除“输入有序导致分区不均衡”的可能。第二个是采用尾递归优化手动把递归改成循环控制这是编译器层面的常见优化手段在解释型语言里可以通过显式栈模拟实现。第三个就是前面提到的迭代式实现用栈来管理子区间彻底绕开递归深度的问题代价是代码稍显复杂。5.2 海量重复元素下的性能灾难有些场景下数据分布非常集中比如统计用户访问频次数组中可能充斥着大量相同的数字。这时如果使用传统二路快排即使基准选得不错也可能出现一边是等于基准的一个大区间、另一边是空区间的极端现象。递归的重心偏移让每次分区的效率大打折扣最终性能从期望的 O(n log n) 恶化成 O(n²)。这个问题最直接的办法就是换用三路快排这在上面已经详细说过。另外还有一个通用思路如果数据取值范围不大且已经知道所有可能取值那直接用计数排序可能比任何基于比较的排序都更快位图法甚至可以在 O(n) 时间内解决。因此遇到重复元素导致的性能问题先别急着优化快排本身先分析数据分布往往能找到更轻量高效的算法。快排并不是银弹选算法要结合场景来考虑。这也解释了为什么各大语言标准库的排序实现会综合多种算法之长在不同条件下自动切换策略。5.3 边界条件写错引发的疑难杂症边界条件错误是快排代码里的最高频事故排查起来也比较费神。我整理了几个最常见的边界地雷供各位参考Lomuto 分区中for j in range(low, high)而不是range(low, high1)。为什么因为此时high位置存放的是基准数本身j 走到 high-1 就够了之后再单独把基准交换到i1处。多走一次虽然逻辑也能跑通但会把基准数和自身做一次无意义的比较。递归调用时右区间必须是[pi1, high]而不是[pi, high]。因为pi位置的元素已经归位下次递归绝不能把它再纳入排序区间否则会出现元素被反复交换但始终无法完全排序的诡异现象。在 Hoare 分区中i j就返回而不是i j。因为当数组长度是偶数时两个指针可能会交错走过如果只在相等时返回会发生越界访问。交换操作必须使用两个变量直接交换值不能使用数组某个位置做临时存储。用arr[i] arr[j]这种覆盖写法会直接丢掉元素导致排序结果错误且难以调试。调试快排问题时最好的工具是“最小用例 打印交换过程”。找一个长度 5~10 的数组人肉模拟一遍期望的交换顺序和程序打印的每次交换结果做对比通常几步就能定位到越界或死循环的位置。还有一个习惯很有用在写递归函数时函数开头打印一下要处理的区间[low, high]代码跑起来一旦出现奇怪的下标立刻能看出问题点。6. 从快排出发的一点体会快排这个算法看起来简单实际写对、写稳、写快每一步都有讲究。我自己从“能写出来”到“能针对不同场景做调优”这个过程差不多花了两周时间。最大的感悟是算法学习不能只背代码必须搞清楚每一步操作的意图尤其是分区操作里每个边界条件的意义。建议你找一个无序数组用纸笔手动走一遍 Lomuto 分区和 Hoare 分区的全过程这对理解快排的底层逻辑非常有帮助。如果你准备面试快排的常考点包括时间复杂度的推导过程、最坏情况的触发条件和解决方案、递归与迭代的写法差异、快排的稳定性分析以及它和归并排序的应用场景对比。这些东西并不是背答案就能答好的关键还是看你对“分治”和“分区”这两个核心动作的理解是否足够扎实。手里有数据结构基础的话还可以试着对比阅读标准库里的排序实现源码看看工业级排序是怎么在这些优化点之间做权衡的。读源码有时候比看几遍教科书都管用因为你会看到真实世界对性能的每一处细节打磨。另外分享一个小技巧在本地写快排练习时用 Python 的 unittest 或者简单的断言对随机生成的数组、有序数组、倒序数组、全重复数组分别做正确性验证。这样每次改动后都能快速确认代码没有破坏基本正确性排查问题时也更有底气。这种“多场景验证”的习惯比写完就扔到一边强太多了。