消息传开那天程序员社群的画风出奇一致转发、沉默、然后继续敲代码。很多人第一反应是去看一眼自己代码里那个 sort()——因为就在那一刻全世界数以亿计的程序正老老实实地运行着这位老人六十多年前想出来的算法。快速排序这个名字只要学过数据结构就绕不开只要写过业务代码就逃不掉。它不是最复杂的算法却是把“分治”和“原地操作”发扬光大的开山之作。不少网友在评论区写下“编程界永远的神”我看到这句话时并不觉得夸张反而认为这是从业者能给出的最朴素、最真诚的评价。这篇文章不打算写悼词我想趁这个机会把快速排序从思想、实现到工程实战完整拆一遍顺便聊一聊托尼·霍尔Tony Hoare留给这个行业的其他遗产。不管你是刚翻开《算法导论》的学生还是每天和 CRUD 打交道的工程师这篇都值得你慢慢读并把代码亲手敲一遍。1. 核心思想拆解快速排序为什么能这么强1.1 分治思想从整理扑克牌说起1960年前后Tony Hoare在莫斯科国立大学做访问学者当时他负责一个机器翻译项目需要在俄英词典数据上做排序。那个年代的计算机内存小得可怜动辄几十KB任何排序算法都必须在数组内部完成交换不允许额外开一块等大的内存。在这样一个朴素而严苛的环境下他想出了一个极其简洁的方案随便选一个元素作为基准把比它小的放到左边比它大的放到右边然后对左右两边递归执行同样的操作。这个思路放到今天依然惊艳。用一个生活化的例子来说打扑克的时候如果你面前有一堆乱牌聪明的整理方式不是一张张把牌插到正确位置——那是插入排序——而是先抽一张牌当“分界线”把小于它的牌丢到左边、大于它的牌丢到右边。接下来只需要对左右两堆重复这个动作。这种“分而治之”的策略让每轮处理只需做简单的比较和交换不需要额外的暂存区。这也是快速排序在诞生60多年后的今天仍然作为众多标准库排序基础的根本原因。拆开来看快排只有三个动作选基准pivot、分区partition、递归。选基准的方法五花八门分区写法也有好几种但骨架从1962年论文发表至今几乎没有变化。它的伟大恰恰在于把“排序”这个看起来只能一步步推进的问题抽象成了“划分加递归”的结构化思考。很多刚学算法的同学总觉得递归是绕弯子但快排会告诉你直接让子问题递归解决自己往往比手写一堆嵌套循环优雅得多。1.2 复杂度直觉O(n log n) 到底怎么来的要理解快排为什么能成为“默认选项”得先说清楚它的时间复杂度直觉。每一轮分区需要扫描当前子数组的所有元素把比基准大的、小的分开所以单轮工作量是 O(n)。如果基准选得足够好数组会被切成两个长度接近的子问题递归树的高度约为 log n。每一层都要处理约 n 个元素乘起来就是 O(n log n)。注意我说的是“如果基准选得足够好”。快排有一个著名的弱点如果每次基准都选到当前区间最大或最小值划分结果是 1 和 n-1递归树退化成一条长链复杂度直接变成 O(n²)。这就是为什么教材里总在强调随机化基准、三数取中这些优化。但工程实践中合理优化后遇到最坏情况的概率极低这也是快排敢在标准库中挑大梁的底气。我整理一个常见排序算法对比表算法平均时间复杂度最坏时间复杂度额外空间稳定性特点冒泡排序O(n²)O(n²)O(1)稳定代码简单教学意义大插入排序O(n²)O(n²)O(1)稳定几乎有序时接近 O(n)归并排序O(n log n)O(n log n)O(n)稳定适合对象排序、外排序堆排序O(n log n)O(n log n)O(1)不稳定最坏情况可控常数大快速排序O(n log n)O(n²)O(log n)不稳定常数小缓存友好这里有一个很关键的对比归并排序最坏也是 O(n log n)为什么很多场景还是选快排核心在常数因子。归并的合并过程需要大量数组拷贝和额外空间快排只需要在数组内部交换元素对 CPU 缓存也友好得多。尤其在现代计算机的分层缓存架构下快排这种局部性好的写法往往能跑出比理论分析更好的成绩。真正遇到必须稳定排序的场景工程库才会自动切换到归并排序或 TimSort。理解这一点你才算真正看懂了标准库排序的实现取舍。2. 手写快速排序两种分区实现与防退化优化2.1 Lomuto 分区最安全的教科书写法如果只记一种快排写法建议从 Lomuto 分区开始。它的思路非常直白用一个指针 i 维护“最后一个比基准小的元素位置”扫描指针 j 从左往右走凡是遇到比基准小的元素就把 j 位置的元素换到 i1 位置然后 i 前进。扫描结束后把基准换到 i1 位置这个位置就是分区的切分点。Python 实现def quick_sort(arr, low, high): if low high: return # 选最后一个元素作为基准 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] cut i 1 quick_sort(arr, low, cut - 1) quick_sort(arr, cut 1, high)注意循环条件是arr[j] pivot而不是。这意味着相等的元素会被分到基准的左边但递归区间已经完全排除了基准本身所以不会死循环。边界条件low high是递归出口千万别写错成low high然后漏掉空区间。这段代码看起来简单却是很多面试者栽跟头的地方有人把递归区间写成quick_sort(arr, low, cut)和quick_sort(arr, cut, high)导致基准被反复处理最终栈溢出。Lomuto 的缺点在于它默认取最后一个元素当基准如果数组本身已经有序每次分区都只会切掉一个元素算法直接退化成 O(n²)。这种写法在教学、面试中够用但工程上基本不会直接用。2.2 Hoare 分区原始双指针版本Tony Hoare 原始论文里使用的其实不是 Lomuto而是双指针相向而行的 Hoare 分区这也是为什么很多经典教材会专门对比这两种写法。Hoare 分区的核心是选一个基准两个指针从左右两端同时向中间逼近左指针找到比基准大的元素停下来右指针找到比基准小的元素停下来然后交换继续逼近直到两个指针交错。def quick_sort(arr, low, high): if low high: return pivot arr[(low high) // 2] i, j low, high while True: while arr[i] pivot: i 1 while arr[j] pivot: j - 1 if i j: break arr[i], arr[j] arr[j], arr[i] i 1 j - 1 quick_sort(arr, low, j) quick_sort(arr, j 1, high)这里有两个特别容易踩的细节。第一分区函数返回的不是基准下标而是 j——左半部分的结尾。递归时左边是(low, j)右边是(j1, high)千万不能按 Lomuto 那套用 cut-1 和 cut1。第二内层 while 用的是arr[i] pivot和arr[j] pivot不是和。如果写成和当数组里大量元素等于基准时指针会不断越过基准互相穿过最终导致分区失效甚至死循环。我用一个简单例子验证过数组[2, 2, 2, 2]如果内层用第一次循环 i 直接走到越界程序崩给你看。这是我在给团队做代码评审时印象最深的一个 bug。与 Lomuto 相比Hoare 分区平均需要的交换次数更少而且两个指针都在数组内部移动不需要额外空间。这也是为什么绝大多数工程实现都基于 Hoare 分区做改进。2.3 防退化三板斧三数取中、随机基准、插入排序工程上的快排绝不会老老实实取“最后一个元素”当基准因为那是退化重灾区。常见的优化手段大概这么几类。第一三数取中。从数组的首、中、尾三个位置取中位数作为基准然后把它换到合适的位置。这个技巧极其便宜却能显著降低有序数组或近似有序数组退化的概率。第二随机化基准。每次随机选一个下标把基准值和开头或结尾交换再走分区流程。它不保证一定选到中位数但把最坏情况从“必然发生”变成了“概率近乎为零”。第三小区间切换插入排序。递归到区间长度大约小于等于 16 或 32 时直接改用插入排序。原因很简单区间越小快排的递归调用和分区开销就越显得“大炮打蚊子”而插入排序在小范围里常数极小表现反而更好。再往后就是更重的措施了。C 的std::sort采用 introsort内省排序会在递归深度超过一定阈值时从快排切换到堆排序硬性限制最坏情况为 O(n log n)。JDK 的Arrays.sort对基本类型则使用双轴快排Dual-Pivot Quicksort把区间分成三段而不是两段进一步摊薄了交换和比较开销。这些优化说明一个道理快排不是被某个神秘算法取代了而是一代代工程师在老爷子框架上不断打补丁让它更加皮实耐用。3. 从标准库到数据库快排后代无处不在3.1 标准库排序背后的快排血统一位普通后端工程师的一天其实早就被快排包围了。你写 Python排序调用sorted()底层是基于归并优化的 TimSort它针对现实数据常见的部分有序情况做了大量处理但核心依然是分治。你写 JavaArrays.sort(int[])底层是 Dual-Pivot Quicksort这是快排的直系后代。你写 JavaScriptV8 引擎对数组排序会用分区思想配合插入排序。你写 Cstd::sort是 introsort前身就是快排。你写 Go1.19 之后的sort包换成了 pdqsort名字里就带着 quicksort 的血统。数据库里更是如此。执行ORDER BY时如果数据能装进内存优化器大概率会选用基于比较的排序快排及其变种出现的频率极高。Redis 的SORT命令、Elasticsearch 的排序、Spark 的 sortBy底层都能找到分区排序的影子。所以说“我们每天都在用他的代码”这句话一点都不夸张甚至可以说是从业者能想到的最朴素也最真诚的致敬。3.2 不止排序快速选择与大数据的底层思想快速排序的价值远不止“排序”本身。它衍生出的快速选择算法Quickselect解决的是“从一堆数据里找出第 K 大或第 K 小”的问题。做法很巧妙做一次分区如果基准的位置正好是 K那基准的值就是答案如果 K 在左半部分就只递归左边否则只递归右边。这个算法平均时间复杂度是 O(n)而且几乎不需要额外空间。面试题里“从 10 亿个数字里找第 100 大的数”标准答案就会用到这种分治思路。另外分布式计算中常见的 Shuffle 阶段本质上也是对海量 key 做分区排序一些 GPU 并行排序算法先把数据切块让每个线程块独立快排再对桶做归并。外部排序中快排还经常被用来对内存缓冲区内的数据做初始排序。可以说分治和分区这两个由快排带火的抽象已经成了大数据处理里的基础设施级概念。它用最简单的方式证明了一个道理很多时候把问题切小比把每一步做得更精细来得更有效。3.3 不只是快排Hoare 逻辑、CSP 与空引用托尼·霍尔在 1980 年获得图灵奖身份是“算法设计与编程方法学的先驱”快排只是他众多贡献里最广为人知的一件。他提出的 Hoare 逻辑是程序验证领域的基石用前置条件、后置条件和循环不变式来严格证明一段程序是否正确地完成了目标。你在大学里学的“循环不变式证明”根子就在老爷子这里。他还设计了通信顺序进程CSP一种描述并发系统交互的形式语言。今天 Go 语言里的 goroutine 与 channel、Erlang 的进程模型思想源头都能追溯到 CSP。换句话说不光是排序现代并发编程里也有他留下的基因。还有一个程序员圈子里流传很广的梗老爷子本人说过他在 1965 年设计 ALGOL W 时引入了空引用null后来他自己把这称为“十亿美元错误”因为空引用导致的程序崩溃和工期延误累计至今耗费的金钱和精力远不止十亿美元。每次看到 NullPointerException程序员们都会想起这位诚实的图灵奖得主——他不但创造了无数令人拍案叫绝的设计还敢于当众承认自己挖过的坑。这种坦然也是大家叫他“永远的神”时特别敬重他的一点。4. 真实踩坑记录快排的边界、死循环与选型建议4.1 递归边界错写的栈溢出事故我帮同事排查过一次特别典型的崩溃。他在面试准备阶段手写快排Lomuto 版本递归调用写成了quick_sort(arr, low, cut)和quick_sort(arr, cut, high)。看起来没什么问题但基准值 cut 被反复包含在子区间里递归永远无法收敛最终抛出 StackOverflowError。排查的时候我先在递归函数开头打印 low、high 和 cut很快就发现区间长度要么不变、要么负增长问题一目了然。正确的边界必须保证区间严格缩小右边子区间从cut 1开始左边子区间到cut - 1结束。如果你对边界没有信心可以在每次递归前加一句断言让程序在异常状态下快速失败。调试递归算法的通用思路是先确认“递归是否朝终止方向前进”再去看终止条件本身。这个习惯对写任何递归代码都有用。4.2 重复元素导致的死循环与分区失效Hoare 分区在高重复元素数组上有一个著名的坑当内层 while 条件写成或时指针会在相等元素上来回穿梭。举个例子数组全是同一个值比如[2, 2, 2, 2]左指针会因为“找到等于基准的值”而一直右移右指针会一直左移最终两个指针交错出界while 循环根本等不到i j的终止代码直接崩掉。即使没有崩分区结果也会变得毫无意义左右各分不出有效区间。修复方法就是我前面给的写法左指针用arr[i] pivot找第一个不小于基准的元素右指针用arr[j] pivot找第一个不大于基准的元素。遇到相等元素时进入交换同时让两个指针各走一步。这样等于基准的元素会被均匀地摊到左右两侧既不会阻塞指针推进也不会造成递归区间不减。4.3 大数据量下的递归深度与显式栈方案我最初学习快排时有个习惯拿 Python 写实验代码然后给一个 10 万级别的随机数组排序。在本地跑得好好的换成 100 万数据后 Python 直接栈溢出了。原因是 Python 默认递归深度上限只有 1000 左右而快排的递归深度在随机数据下大约有几十层看似没问题但如果数组本身有序或者接近有序又没用三数取中递归深度会暴涨瞬间击穿上限。工程解决思路有两个。一是优化基准选择把递归深度压下来二是干脆不用递归改成显式栈模拟def quick_sort_iterative(arr): stack [(0, len(arr) - 1)] while stack: low, high stack.pop() if low high: continue pivot arr[(low high) // 2] i, j low, high while True: while arr[i] pivot: i 1 while arr[j] pivot: j - 1 if i j: break arr[i], arr[j] arr[j], arr[i] i 1 j - 1 stack.append((low, j)) stack.append((j 1, high)) return arr用列表模拟栈之后递归深度就不再受语言限制极端情况下也只是栈存了太多区间而已。我自己在实际项目中很少需要手写这种版本因为标准库早就处理好了但在嵌入式或用 C 写底层库时这种写法依然是值得掌握的兜底方案。4.4 排序选型什么时候不要用快排并不是所有排序场景都应该用快排。我整理一份选型速查场景推荐方案原因基本类型数组排序语言内置排序多含快排性能好稳定可靠对象/多关键字稳定排序归并排序或 TimSort保持相等元素的原始相对顺序数据几乎有序且量很大TimSort / 插入排序优化现实数据常近似有序TimSort 又快又稳内存极其紧张堆排序原地排序最坏仍 O(n log n)学习与面试手写快速排序练分治、双指针、边界思维这个表背后的原则很简单生产环境优先用内置工具不要自己造排序轮子自己写的快排主要用于学习、面试和解决特定性能瓶颈。真要自己实现一定要处理三数取中、小区间切换、递归边界这三大关卡。另外提醒一句排序算法的稳定性不是“性能好”就能弥补的遇到需要保持原顺序的多字段排序直接上归并才是正解。5. 纪念托尼·霍尔把快排刻进肌肉记忆5.1 手写快排的五个阶段Tony Hoare 的离世让很多程序员重新想起了这个算法。真正的纪念方式是把快排刻进肌肉记忆。我建议按下面这条路径循序渐进先能默写 Lomuto 分区版本理解基准归位和递归边界。再写 Hoare 双指针版本背下 j 是左半部分结尾这个关键点。加入三数取中和小区间插入排序感受常数优化的意义。分析最坏情况和平均情况能解释为什么随机化有效。扩展实现快速选择算法解决 TopK 问题。这套路径我在带实习生时用过很多轮平均一个下午能走完前四步剩下的瓶颈基本都卡在第 5 步。只要把快排吃透你会发现后面学归并、堆排序、二分查找都会顺利得多因为它们共用同一套递归分治的思维方式。练手时不用迷信刷多少道题把快排能讲到别人听懂就算真正掌握了。5.2 他说过的那句话值得程序员一直记着托尼·霍尔留下过一句名言计算机科学并不是关于计算机的就像天文学并不是关于望远镜的。这句话放在今天看依然精准。我们写代码、调 API、优化性能真正的功夫其实在抽象问题、建立模型、理解边界——这些才是超越具体工具的能力。他设计快排的年代计算机还笨重得要命内存小得可怜但他没有陷入“等硬件再好一点”的被动里而是用数学直觉找到了一个足够简单、足够优雅的解法。现代开发者遇到性能问题第一反应常常是买更大的机器、加更多缓存很少有人愿意停下来想一想问题的结构能不能切得更小快排留给我们的不只是几行算法代码更是一种把复杂问题化解为简单重复的思维方式。在我带过的不少新人身上我见过两种极端一种是不懂原理只会上网搜代码另一种是沉迷手写算法、业务里非要自己造排序。老爷子留给我们的启示或许是一种更好的平衡——既能默写快排又能在该用sorted()的时候毫不犹豫。这些年做工程最大的体会就是基础算法不是拿来背诵的而是用来训练的思维方式。每当你需要权衡、需要优化、需要把一个看似复杂的问题切分成可处理的小块快排这个六十几年前的老算法都会在你脑子里亮一下。愿你也能把它写进自己的肌肉记忆里。这大概是对一位“编程界永远的神”最好的纪念。