1. 为什么说快排真的很好玩先从一圈人都在争论它说起如果你在程序员群里扔出一句“快排真的很好玩”大概率会引发一场混战有人说它是算法入门第一课有人说它面试天天考还有人会说“我上次线上出问题就是快排搞的”。作为一个写了十年代码、也踩过无数排序坑的人我想先给快排正个名——它确实值得玩而且玩透了你会发现自己对递归、分治、复杂度这些概念的理解都上了一个台阶。快排全称快速排序Quicksort是绝大多数排序场景里效率最高、使用最广的排序算法之一。它的基本思路只有一句话从数组里选一个基准值把小于它的放到左边大于它的放到右边然后对左右两部分分别做同样的事。听上去简单但这里面的东西多到可以陪你玩很久。这篇文章既适合刚学算法的朋友也适合准备面试、想在工程里彻底搞懂排序的人。我会从最基础的版本开始一步步写出能扛住真实数据的快排再把常见的坑、经典变体和思维方法都聊透。1.1 快排是什么一段让数据变得有序的“魔法”在编程里排序是最常见、最基础的需求之一。不管是给成绩单排个名次、给商品按价格排序还是后端日志按时间戳整理最后都绕不开排序算法。而排序算法里快排的地位有点像武侠世界里的“独孤九剑”不是最好写的但用它的人最多用得好的话效果最好。要让一组数字从乱序变成有序常规思路有两种一种是像冒泡排序、插入排序那样每趟想办法把一个元素放到正确位置另一种就是快排的思路——分而治之。把排序整个数组的大问题逐步切分成排序两个更小数组的小问题小到不能再小的时候自然就排完了。我特别喜欢用整理书架的比喻来解释快排。假设你书架上一排书完全乱序现在要按书的厚度从左到右排好。快排的做法是随手抽一本书当“基准”然后把比它薄的书放左边比它厚的放右边。之后你对左边那堆再做一次同样的操作对右边那堆也做一次同样的操作。只要这个操作不断递归下去最后每本书都会到它该在的位置。整个过程最巧妙的地方在于你抽基准书的时候其实并不知道最终书架长什么样但你通过一次又一次的“以某本书为界”让问题规模快速减半。我们拿一个实际数组来看这个过程。假设数组是[8, 4, 3, 7, 6, 1, 5]第一轮选基准值为5假设选最后一个元素分区后得到[4, 3, 1]和[8, 7, 6]基准5已经放在了正确位置。接下来左半部分选基准1得到空数组和[4, 3]右半部分选基准6得到空数组和[8, 7]。一层层递归下去每个子数组的长度都在迅速缩小最后所有元素各就各位。整个过程就像剥洋葱每剥一层问题就小一圈。这个算法的平均时间复杂度是 O(n log n)。啥概念处理10万个元素大概只需要几十毫秒而 O(n²) 的冒泡排序可能要几十秒甚至更久。正是这种效率优势让快排在工程世界占据了一个非常重要的位置。1.2 分治的乐趣把大问题剪成小问题快排的核心思想其实就两个字分治。我第一次真正理解分治的时候心里想的是原来很多看似复杂的事情拆开看就简单了。快排的递归过程本质上是在不断问自己一个问题能不能把我手里的这个数组分成“比基准小”和“比基准大”两拨然后让这两拨各自内部分别有序如果能那么整个数组就有序了。这个思想放进生活里也一样。比如接手一个混乱的大型项目你不会想着一口气把整个项目全部理清而是先找一个“基准”——比如把任务按紧急程度分紧急的放左边不紧急的放右边然后分别处理。先分类、再细化、再逐个击破这就是分治。从递归树的角度看快排每一次分区都尽量把数组切成两段理想情况下递归树的深度是 log2(n)。也就是说对100万个元素的数组排序递归树的深度大约是20层。每一层所有分区加起来要处理 n 个元素所以整体工作量是 n 乘以树深也就是 O(n log n)。这也是为什么快排一旦基准选得不好、分区严重失衡递归树会退化成一条长链深度变成 n效率就崩了。从这个角度来说快排不仅是一个算法更是一个思维模型。它教会我的是在面对一个看起来很复杂的问题时先找到一个能把问题一分为二的“轴”然后递归地处理每一半。这种体验真的很爽——尤其是在纸上手画一个无序数组然后一步步把快排的分区过程画出来你会看到混乱的数据慢慢变得整整齐齐。我可以毫不夸张地说这就是算法世界里最像“魔法”的瞬间之一。2. 手把手写一个快排从能跑通到能扛事既然说快排好玩那光看不练可不行。这一章我们直接上手写代码。我会给你两版实现先写一个最直观、最容易理解的版本再写一个工程里真正会用的原地分区版本。2.1 最简版快排五分钟写出来的递归实现先看这个版本其实核心代码只有几行。我用 Python 写因为可读性最好def quicksort_simple(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 quicksort_simple(left) [pivot] quicksort_simple(right)这段代码做的事就是如果数组长度是0或1直接返回因为已经有序了否则把第一个元素当作基准值 pivot遍历剩下的元素比基准小的或者相等的放进 left比基准大的放进 right然后递归排序 left 和 right最后拼起来。我拿一个例子跑一下就清楚了。假设arr [8, 4, 3, 7, 6, 1, 5]第一轮选 pivot 8那 left 就是[4, 3, 7, 6, 1, 5]right 是[]因为剩下所有数都比8小。然后递归排序 left等 left 排好变成[1, 3, 4, 5, 6, 7]最后拼上8和空数组结果就是[1, 3, 4, 5, 6, 7]。这个版本非常好理解但它有几个问题。第一它创建了新数组 left 和 right额外空间是 O(n)第二它没法在原数组上直接操作工程里很少这么用。不过作为学习工具它是完美的入门版本。如果你第一次接触快排我建议你在纸上把递归调用树画出来会特别有感觉。2.2 原地分区面试和工程里最常写的 partition工程里和面试里更常见的快排写法是“原地分区”也就是不创建新数组直接通过交换元素来完成排序。这里我介绍最经典的 Lomuto 分区方案。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 quicksort_inplace(arr, low, high): if low high: pi partition(arr, low, high) quicksort_inplace(arr, low, pi - 1) quicksort_inplace(arr, pi 1, high)这段代码的思想是把数组最后一个元素当作基准 pivot然后用两个指针 i 和 j 把数组扫描一遍。i 指向“小于 pivot 区域”的末尾j 负责遍历那些还没处理过的元素。当 arr[j] 小于 pivot 时就把 arr[j] 和 arr[i1] 交换把小于 pivot 的元素“挪”到左边区域。扫描结束后把 pivot 放到 i1 的位置这个位置就是 pivot 最终的位置然后递归处理左右两半。注意一个关键点arr[i 1], arr[high] arr[high], arr[i 1]这行是把基准值 pivot 放到正确位置上。很多人第一次写的时候会漏掉这行导致排序结果完全不对。另外递归边界要特别注意pivot 所在位置 pi 已经归位所以递归范围是low, pi - 1和pi 1, high如果把 pi 本身也传进去递归就会出现死循环。这个版本的空间复杂度是 O(log n)递归栈的深度时间上依然是平均 O(n log n)。它不需要额外的数组所以在实际工程中使用得更广泛。我在面试别人时也经常会让他们写这个版本因为它能很好地考察一个人对指针、边界条件的把握。除了 Lomuto 分区还有更早提出的 Hoare 分区方案。Hoare 分区从两头往中间扫描交换逆序对平均交换次数更少但实现起来边界条件更绕。StatisticallyHoare 分区在大部分数据集上比 Lomuto 快一点因为它做的交换次数更少。但 Lomuto 更好写、不容易出错所以教学场景里更多见。如果你追求极致性能可以去研究一下 Hoare如果你想要“写得对、答得稳”Lomuto 完全够用。2.3 基准选择为什么不能永远拿第一个元素开刀看到这里你可能会想既然快排这么简单为什么网上有那么多关于快排的讨论答案是因为基准值选不好快排会从“快排”退化成“慢排”。最极端的例子就是对一个已经有序的数组比如[1, 2, 3, 4, 5, 6, 7, 8]如果用第一个元素当基准分区后你会发现 left 永远是空right 是剩下的所有元素。每一轮递归只能减少一个元素这样就需要递归 n 层时间复杂度直接变成 O(n²)比冒泡排序好不到哪去。解决思路有两个都很简单。第一种是使用随机化基准。每次分区时从[low, high]中随机选一个位置作为 pivot然后把 pivot 和arr[high]交换再走 Lomuto 分区。这样即使输入是最坏情况算法也不会总是踩中那个最坏的坑。数学上可以证明随机化快排的时间复杂度期望是 O(n log n)。第二种是使用三数取中法median-of-three。从子数组的左、中、右三个位置各取一个值选择大小居中的那个作为基准。这样做既不需要生成随机数也能有效应对“数组基本有序”的情况。很多标准库就是这么做的。我做过一个简单的对比实验对 10 万个已经有序的整数排序固定选第一个元素当基准耗时约 8 秒选中间元素当基准耗时约 20 毫秒随机化基准耗时约 25 毫秒。这个差距足够说明问题基准选得对不对直接决定了快排是“快排”还是“慢排”。实际工程里快排的基准选择几乎都是随机化加三数取中的组合拳既有稳定性又有性能。3. 快排的进化形态三路快排、随机化与混合策略快排不是一成不变的。真实工程里很少有人直接拿最基础的快排就用因为它在面对重复元素、小规模数据和有序数组时都会遇到性能水位下降的问题。这一章我们聊聊快排的几个进化方向。3.1 三路快排当数组里全是重复元素时先考虑一个场景一个数组里有一半元素是相同的比如一堆用户状态码大量都是0、1、2这三种值。如果用标准二路快排分区的时候等于把一堆相同的值分散到左右两边后续递归还要反复处理它们白白浪费了很多时间。三路快排3-way quicksort专门解决这个问题。它的分区不是两个区域而是三个区域小于 pivot 的、等于 pivot 的、大于 pivot 的。等于 pivot 的那部分已经放在了正确位置下一轮递归完全不用管它。这样当重复元素很多时效率会有很明显的提升。核心代码思路大致是这样的def partition_3way(arr, low, high): pivot arr[low] lt low # 小于 pivot 的区域右边界 gt 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 return lt, gt这个写法的巧妙之处在于遇到大于 pivot 的元素时把当前元素与 gt 位置的元素交换但 i 不前进因为换过来的元素还没被检查过。很多人第一次写的时候会在这里踩坑忘了“交换后 i 不移动”这个细节导致某些元素被跳过。调用时递归只处理[low, lt-1]和[gt1, high]两个区间中间那段等于 pivot 的元素直接跳过。对全数组都是同一个值的极端情况三路快排只需要一次分区就能结束复杂度接近 O(n)。这也是为什么在处理大量重复键的场景里三路快排是首选方案。C 标准库、Java 的 Arrays.sort 在某些场景下对快排做进一步优化时也会用到类似思路。3.2 频繁排序小数组插入排序比快排更快另一个容易被人忽视的问题当子数组规模非常小比如小于15个元素快排的递归调用开销反而比插入排序更大。因为每次递归都要分配栈帧、执行 partition这些固定成本对小规模数据来说太奢侈了。工程里的做法是在快排里加一个阈值判断如果当前子数组长度小于某个阈值通常取10到20就直接用插入排序而不再继续递归。这段逻辑写出来大概是这样def quicksort_hybrid(arr, low, high): if high - low 1 20: insertion_sort(arr, low, high) return pi partition(arr, low, high) quicksort_hybrid(arr, low, pi - 1) quicksort_hybrid(arr, pi 1, high)插入排序在小数据量下有一个天然优势它几乎没有什么额外开销而且是稳定排序。让插入排序处理小尾巴让快排处理大头两相结合整体性能能提升不少。C STL 里的 std::sort 就是这么干的它在数据量小的时候转用插入排序在递归过深的时候转用堆排序这就是所谓的“内省排序”introspective sort。我自己在项目里也实践过这个思路。以前写日志分析工具要对几万个时间戳排序最初直接用了最基础的快排发现整体要 90 多毫秒。后来加上小数组插入排序的优化同样的数据量降到了 60 毫秒左右。别小看这 30 毫秒在实时请求链路里可能就是一个可用性和超时的区别。阈值具体选多少可以在你的数据上做几次实验一般 10 到 20 是一个甜点区间。3.3 语言内置排序为什么你天天用 sorted但它不是快排看到这里你可能会问那我日常用 Python 的sorted()、Java 的Arrays.sort()它们是快排吗答案有点意外它们不一定是我们刚才写的经典快排。Python 的sorted()用的是 TimSort它本质上是一种结合了插入排序和归并排序的混合算法特别擅长处理“原本就部分有序”的数据。Java 的Arrays.sort()对基本类型数组用的就是双轴快排Dual-Pivot Quicksort对对象类型数组用 TimSort。为什么语言设计者不直接全部用经典快排一个很重要的原因是稳定性。快排不是稳定排序也就是说两个相等元素的相对顺序在排序后可能发生变化。很多业务场景比如按时间排序后再按用户排序要求多关键字排序这时稳定排序才有意义。另一个原因是快排的最坏情况终究是 O(n²)虽然随机化可以把概率降得极低但某些系统还是希望从理论上规避这种风险。了解这些背景你再看“快排很好玩”这件事就不只是停留在手写算法层面了。它让我意识到一个算法的工程落地要考虑数据分布、稳定性、内存访问模式还要考虑最坏情况的兜底方案。快排是这一切讨论的绝佳入口也是理解“为什么一个算法有这么多变体”的活教材。4. 快排思维的“超能力”快速选择与 Top K 问题快排最好玩的地方可能不在于排序本身而在于它那个核心操作 partition 可以被拆出来单独使用。你不需要对整个数组排序就能拿到一些非常有用的结论。4.1 快速选择第 K 大元素的分治解法举个例子给你一个乱序数组想找第 K 大的元素。常规做法是先排序然后按下标取需要 O(n log n) 时间。但如果用 partition 的思路我们可以做到平均 O(n)。思路是这样的调用一次 partition返回基准值的最终位置 pi。如果 pi 恰好等于 K那arr[pi]就是我们要找的元素如果 pi 大于 K说明第 K 大的元素在左半部分那么只需要递归处理左边就可以了如果 pi 小于 K则递归处理右边。每一轮只需要处理一个子区间而不是继续排序所有子区间。def quick_select(arr, low, high, k): if low high: return arr[low] pi partition(arr, low, high) if pi k: return arr[k] elif pi k: return quick_select(arr, low, pi - 1, k) else: return quick_select(arr, pi 1, high, k)注意这里我从 0 开始计数所以 k0 对应最小值klen(arr)-1 对应最大值。如果是找第 K 大可以先转成对应下标也可以改一下比较方向。这个技巧在解决“Top N 个最大元素”、“求中位数”这类问题时非常有用。为什么平均复杂度是 O(n)因为每轮 partition 只在一边递归工作量从 n 降到 n/2再降到 n/4加起来是一个等比数列总和约等于 2n。虽然每轮 partition 本身是 O(n)但只处理一边所以整体是线性的。当然如果基准选得差QuickSelect 同样会退化到 O(n²)所以随机化基准在这里一样重要。我在面试候选人的时候很多人能背出快速排序代码但很少人能想到用 partition 来做快速选择。这恰恰是快排思想最有魅力的延伸同样是分而治之排序只是它的一个功能它还是一种高效的查找手段。4.2 将快排套路用于真实项目日志 TopK 统计与中位数计算具体到实际项目我印象最深的一次是帮一个数据团队优化统计逻辑。他们的需求是从一天几百万条事件日志里找出访问量最大的前100个用户 IP。最朴素的实现是用哈希表统计每个 IP 的次数然后对整个哈希表按键值排序取前100个。这个方案在数据量小的时候没什么问题但日志量大了以后全排序的开销就不划算。用快速选择的思路可以做一个优化把所有 IP 的次数收集成一个数组然后用一个最大堆先维护前100个元素或者直接使用快速选择找到第100大的阈值再遍历一遍数组把大于等于阈值的 IP 输出。这样排序部分变成了 O(n) 平均值整体性能有了明显提升。这种套路本质上就是快排的“分治”思想在数据统计中的应用。很多时候我们不需要完全有序只需要知道某一个位置上的值或者前 K 个元素是谁。抓住“partition 返回了某个元素最终位置”这个特性就能大幅减少无用功。这也是为什么我一直跟团队里的新人说快排不是一个背下来就完事的算法它是理解更高级算法的一把钥匙。学会了 partition快速选择、荷兰国旗问题、以及很多数据统计题的解法都会变得顺理成章。你把 partition 封装得越好后续在这些问题上花的时间就越少。5. 快排实战中的常见坑与排查技巧聊了这么多理论最后分享一些实战中踩过的坑和排查方法。这些内容通常是文档里不会写的但遇到了往往很让人头疼。5.1 死循环或排序结果不对先检查递归边界快排最容易出问题的地方在递归边界。比如我见过不少人写的递归入口是这样的quicksort_inplace(arr, low, pi)注意 pi 这个位置已经被 pivot 占据了不需要再次排序。如果边界不写成pi - 1和pi 1就会导致 pivot 反复参与分区轻则排序结果错误重则无限递归、栈溢出。排查方法很简单在 partition 返回后把数组打印出来看看 pivot 是否到了正确位置左右两侧的元素是否满足“左小右大”。只要这个不满足问题大概率出在指针移动上。另一个常见错误是在 Lomuto 分区中如果数组里有大量等于 pivot 的元素且判断条件是小于 pivot那么等于 pivot 的元素会散落到两侧。这本身不会导致错误但会让递归树不平衡效率下降。这时可以考虑用三路快排来优化。我在实际带新人时会让他们专门跑一组测试用例空数组、单元素数组、全部相同数组、降序数组、随机大数组。这五类用例能覆盖快排绝大多数的边界问题。其中“全部相同数组”最能暴露分区策略的弱点很多看起来没问题的快排实现跑这一组数据时效率会骤降。5.2 递归栈溢出三招救回来用递归实现的快排在数据量非常大且递归不平衡的时候可能会触发递归栈溢出。在 Python 里表现就是 RecursionError。先检查递归深度。Python 默认递归深度是 1000你可以用sys.setrecursionlimit(100000)临时提高上限但这只是治标。真正管用的方法有三个随机化基准尽量避免每次选到最大或最小元素。三数取中让基准值尽量靠近中间值。尾递归优化在递归调用时只对短的一半使用递归长的一半用循环处理。这样一来递归深度最多是 O(log n)而不是 O(n)。尾递归优化的代码模式大致是这样的def quicksort_tail(arr, low, high): while low high: pi partition(arr, low, high) if pi - low high - pi: quicksort_tail(arr, low, pi - 1) low pi 1 else: quicksort_tail(arr, pi 1, high) high pi - 1这段代码的原理是每次都把更长的那一半用循环继续处理把更短的那一半交给递归。递归深度最多是 log(n)不会因为输入是有序数组而递归 n 层。我自己的建议是在面试中如果遇到“写快排”这个题最好主动提一句“我会选择随机化基准并做尾递归优化”这会立刻让面试官对你的代码功底刮目相看。5.3 快排为什么会比冒泡还慢数据规模说了算还有一种很有意思的情况有些人拿快排和小数据量排序对比发现快排反而更慢于是怀疑自己的实现有问题。这其实是正常的。当数据量特别小比如只有几十个数快排的 partition 调用、递归调用栈分配、函数调用开销都是实打实的成本。而插入排序在接近有序的小数据上几乎不退步因为它只需要移动少量元素。这也是为什么几乎所有工业级排序实现在小数据量上都会切换成插入排序。另外还要考虑一个因素缓存局部性。快排在递归过程中访问的位置是跳跃的对 CPU 缓存不太友好插入排序是线性扫描缓存命中率更高。所以在特定数据集下快排的快会被缓存效应抵消一部分。这也是工程里才有的问题你在算法教科书上不太会看到。我做过一个测试对 100 个已经接近有序的整数排序插入排序耗时约 0.02 毫秒快排约 0.06 毫秒。但如果把数据量放大到 10 万个乱序整数插入排序就需要好几秒而快排只要 20 多毫秒。结论是没有绝对最优的排序算法只有最合适的算法。当你下次在项目里遇到排序性能不理想时先别急着怀疑快排看看数据规模、数据分布和内存访问特征很多时候问题的答案就藏在这些地方。6. 聊聊我玩了这么久快排的真实体会说实话快排的好玩之处不仅在于它的效率高更在于它是一扇窗。透过这扇窗你能看到分治、递归、随机化、复杂度和工程优化这些计算机科学里的核心概念是如何在一个“排序”小问题上交织在一起的。我至今还记得自己第一次在纸上完整画出快排分区过程时的那种顿悟感原来复杂不是问题不懂分解才是问题。快排从理论到工程中间隔着很长一段路。教科书上讲的是最基础的逻辑但真正要在一个日活百万的系统里稳定跑起来你还要考虑随机化、三路分区、小数组插入排序、递归深度限制甚至还要考虑缓存命中率。这些细节单独拿出来都不难但组合在一起就是一个非常完整的工程优化案例。这也是为什么我一直鼓励团队成员花点时间把快排吃透因为它在很小的代码量里浓缩了太多可迁移的经验。最后再分享一个小技巧如果你在项目里经常手写排序逻辑建议把 partition 单独封装成一个函数不管是用 Lomuto 方案还是 Hoare 方案。这样下次遇到找第 K 大、求中位数、甚至荷兰国旗问题时你都能直接在它之上快速构建解法而不是从零再写一遍。快排的好玩就是你越用它越能发现它能用到更多地方。这个封装的习惯我保留到了今天它帮我节省了大量重复造轮子的时间。