托尼·霍尔爵士走了享年92岁。听到这个消息的时候我正在给一批业务数据写排序逻辑——用的恰恰就是他发明的快速排序。这件事本身就挺有宿命感的你很难找到一台服务器、一套数据库、一门编程语言跟快速排序毫无关系。无论是Java里的Arrays.sort还是C里的std::sort又或是搜索引擎的词项倒排索引背后都藏着分而治之这套思想。这篇文章不是念悼词而是想以一个工程师的视角把霍尔留给这个世界的算法遗产拆开看看快速排序到底怎么运转它凭什么赢下这场持续六十年的排序战争为什么默认写法又容易翻车以及如今的工程世界替他打了哪些补丁。适合所有手写过排序代码、背过面试八股、或者正在学算法的人。1. 托尼·霍尔一个改变了排序这个词的人1.1 1960年的一次灵光乍现快速排序诞生于1960年。那年霍尔在莫斯科国立大学做访问学者研究机器翻译。机器翻译有个基础环节把俄语词汇按字母顺序排列以便建立词表、查词频、对齐语料。当时的计算机性能弱得可怜内存以KB计CPU主频远不如今天一块电子表芯片。已有的排序算法像冒泡排序、选择排序都是O(n²)复杂度处理几千个词就慢得让人绝望。归并排序虽然快但需要一块额外的存储空间在那个内存金贵的年代开销太奢侈。霍尔后来在很多场合讲过他是在某个瞬间意识到我可以把数组分成两半左边放比基准小的右边放比基准大的然后递归处理。这个想法朴素得惊人却是计算机科学史上第一批原地分治排序算法之一。他1962年在《The Computer Journal》上正式发表了这篇论文论文标题就叫《Quicksort》。从那一刻起快速排序这个名字就在学界和工业界同时传开了一直传了六十多年传进了今天每一套主流编程语言的运行时库。有个细节值得多说一句霍尔当时并不是为了发表论文而发明算法他是为了完成机器翻译任务。这很符合早期计算机科学家的做事方式——先解决眼前的问题再从中提炼普适的方法论。也正因为如此快速排序没有那种学院派算法的拧巴感它足够简单、足够直接、足够实用以至于今天手写一遍快排仍然只需要十来行代码。1.2 这个人远远不止会排序提到霍尔大家最先想到的是快速排序但他的分量远不止这一个算法。说几个同样影响深远的贡献。霍尔逻辑Hoare Logic是他在1969年提出的程序验证方法用前置条件和后置条件描述一段代码执行前后的状态关系从而在数学上证明程序是否正确。这几乎是今天一切形式化验证、断言式编程、契约式设计Design by Contract的理论源头。如果你写过单元测试用过assert读过带param和return注释的接口文档其实都在间接品尝霍尔逻辑的滋味。另一个重量级成果是CSP通信顺序进程Communicating Sequential Processes他1985年出版的《CSP》论著深刻影响了并发编程的理论和设计。后来Go语言的goroutine通道模型、Erlang的actor模型都能看到CSP思想的影子。霍尔在并发领域思考的问题直到今天云计算和微服务大行其道时依然不过时。还有那句流传最广的忏悔。2009年他在QCon大会上说null引用的发明是自己的十亿美元错误。因为null导致过数不清的空指针异常让无数程序员在深夜加班让无数系统在线上崩溃。这句话翻译成工程师的语言就是你写的每一个NPE有一部分都能追溯到霍尔那里。但反过来想能发明一个被全世界骂了这么多年、却依然无法彻底移除的语言特性这本身也是一种传奇。1980年霍尔获颁图灵奖。他的成就当然配得上这份荣誉。他还有一句话我一直很喜欢软件设计有两种方式一种是让它非常简单以致于明显没有缺陷另一种是把它做得非常复杂以致于没有明显缺陷。第一种方式要难得多。这话用来评价快速排序再合适不过——那是一个简单到没有明显缺陷的设计。2. 快速排序为什么能快分治、复杂度与分区套路2.1 用整理卷子的思路理解快排不懂分治的人第一次看快排可能觉得算法不过是在折腾数组元素。我更喜欢用生活场景来讲你手上有两万张考试卷要按分数从低到高排好方便登记成绩。笨办法是冒泡排序从头到尾扫一遍发现相邻两张顺序不对就交换。一遍扫完能确定一个最大值滚到最后然后再扫一遍确定第二大值……两万张卷子要扫差不多两万遍每遍还有两万次相邻比较总量级在四亿次上下搬卷子的人会疯掉。快排的办法不一样。你先随机抽一张卷子比如分数是75。把低于75分的卷子放左边一摞高于75的放右边一摞等于75的跟着75站中间。这一轮下来75这张卷子在最终序列里的位置就确定了因为它左边都是小于等于它的右边都是大于等于它的。接下来你在左边那摞和右边那摞分别重复同样的操作——各自抽一张基准卷再分成三堆。直到某一摞只剩一张或零张结束。这个抽基准、分左右、再递归的流程就是快排的全部核心。它对数据做的是原地重排不需要额外的数组这是当年胜过归并排序的关键它又通过递归把大问题一层层切成小问题每次只付出O(n)的扫描成本就能让一个元素落位。2.2 平均O(n log n)是怎么算出来的算法的复杂度是绕不开的话题。快排的平均情况是O(n log n)最坏情况是O(n²)。写代码可以粗糙但复杂度分析必须清楚否则你连什么时候会翻车都不知道。假设每轮分区后基准元素落在数组中间位置左边大小约等于右边。递归式可以写成T(n) 2T(n/2) O(n)解这条递推式的过程画一棵递归树就能看清第一层处理n个元素第二层左右两半加起来还是n第三层四段加起来还是n。整棵树一共log n层每层合计O(n)所以总复杂度是O(n log n)。操作次数直观一点说一个十万元素的数组快排平均比较约170万次左右而冒泡排序要比较五十亿次上下。差距就是这么大。最坏情况也容易推导。如果每次选基准都选到当前数组里的最小值或最大值分区结果一边是空、一边是n-1递归式退化成T(n) T(n-1) O(n)这个等式展开就是n (n-1) (n-2) ... 1结果是O(n²)。也就是说快排在极端情况下会从快排退化成慢排。这正是好多面试题喜欢问的已排序数组对固定基准快排为什么这么慢的答案来源。怎么防办法是让基准的选择不可预测。随机选基准后每次都选到极端值的概率极低最坏情况虽然在理论上还存在但在工程实践中几乎不可能连续出现。还有一个更稳妥的方案是三数取中从头部、中部、尾部三个位置取中位数当基准后面我会给具体实现。2.3 两种分区套路Lomuto与原始Hoare快速排序的核心是分区partition。教科书和面试题里常教Lomuto分区代码简洁好写而霍尔当年论文里用的是另一种分区方式更绕但比较次数更少、性能更好。两者我都在实际项目里写过非常适合先对照着学。Lomuto分区的思路是把基准固定在数组最右端用一个慢指针i维护小于基准的区域边界快指针j从左往右扫。遇到比基准小的就把它挪到i的位置里最后把基准换到i1的位置。对比项Lomuto分区Hoare分区扫描方式单向遍历一个快指针加一个慢指针双指针从两端向中间靠拢代码难度简单容易写对略绕边界条件多交换次数较多每次命中条件都交换较少只有需要时才交换对重复元素全等数组退化成O(n²)等值处理稍好但仍可能退化适用场景教学、快速实现、低频数据性能敏感、数据量大时的首选Hoare分区用左右两个指针左指针找比基准大的右指针找比基准小的找到后交换两指针相遇时天然分成两半。它每次交换能让两个元素同时落到正确阵营所以交换次数比Lomuto少。代价是边界条件特别容易写错内层while循环必须先判断越界递归区间要用相遇点而不是基准点否则会死循环或栈溢出。我在第五节会专门展开这些坑。3. Java实现快速排序从最简模板到工程级优化3.1 最简版模板Lomuto分区实现先给一份面试与作业最常用的实现基准选最右端使用Lomuto分区public static void quickSort(int[] a, int low, int high) { if (low high) { return; } int pivot a[high]; int i low - 1; // 小于基准区的右边界 for (int j low; j high; j) { if (a[j] pivot) { i; swap(a, i, j); } } swap(a, i 1, high); // 基准归位 quickSort(a, low, i); quickSort(a, i 2, high); } private static void swap(int[] a, int i, int j) { int t a[i]; a[i] a[j]; a[j] t; }写这段代码时有几个点必须想清楚。第一递归终止条件是low high不是low high因为递归调用里的区间可能传成low比high大比如quickSort(a, 0, -1)。第二循环里的比较是a[j] pivot用小于等于而不是小于这样遇到与基准相等的值时会把它们挪到左边区域避免基准值附近出现乱序。第三整个过程中pivot一直待在a[high]没有移动直到分区完成才一步到位地交换这是Lomuto分区最大的优点——基准位置好算代码不容易乱。这个版本的优点是肉眼可见的简洁缺点是i指针在for循环里每命中一次就交换一次交换次数明显偏高。数据和基准正好呈现大小交替时这种反复交换尤其频繁。所以它只适合教学不适合大数组的极致性能场景。3.2 霍尔原始分区更接近1962年的那版代码霍尔版的快排看起来不像Lomuto那么规整但性能和思想都更原汁原味。实现如下public static void quickSortHoare(int[] a, int low, int high) { if (low high) { return; } int pivot a[low (high - low) / 2]; // 取中间值当基准 int i low; int j high; while (i j) { while (a[i] pivot) i; while (a[j] pivot) j--; if (i j) { swap(a, i, j); i; j--; } } if (low j) { quickSortHoare(a, low, j); } if (i high) { quickSortHoare(a, i, high); } }这份代码我建议你逐行读因为每一个边界条件背后都是一个真实翻车现场。pivot取中间位置的元素对有序数组的表现比固定取两端好得多。内层两个while循环先移动指针遇到等于基准的元素时才停下并交换等于基准的值会均匀分配到两侧这在处理重复数据时比Lomuto更抗打。记住外层while用的是i j而不是i j。相遇之后必须还要再交换一次否则中间两个元素可能漏处理。递归区间是[low, j]和[i, high]不是把基准位置挑出来递归因为霍尔分区的基准可能落在任意位置甚至还可能被交换到另一边去。刚开始写霍尔分区时我在这里来回调试了好多回一度怀疑是不是自己交换逻辑写错了后来才确认问题出在递归区间的划分上。3.3 随机化与三数取中防翻车的第一道保险固定基准最怕两类数据完全有序的、接近有序的。电商系统按注册时间导出用户列表、日志系统按时间戳排数据这类场景到处都是。只要基准固定取头或尾有序数组直接触发最坏情况O(n²)。随机化是最简单的解法在递归函数里先随机挑一个位置和末尾或者中间交换后续逻辑完全不动。Random random new Random(); int rand low random.nextInt(high - low 1); swap(a, rand, high); // 把随机基准放到最右继续用Lomuto或者Hoare逻辑随机化之后最坏情况的概率变得极低。你不需要保证每次基准都近似中位数只需要保证不可能有一个恶意数据集稳定地让你每次分区都失衡。这就够了。三数取中median-of-three是另一种常用策略取low、mid、high三个位置的元素用其中位数当基准实践中对有序数据的抵抗效果很好。int mid low (high - low) / 2; if (a[mid] a[low]) { swap(a, mid, low); } if (a[high] a[low]) { swap(a, high, low); } if (a[high] a[mid]) { swap(a, high, mid); } swap(a, mid, high); // 把中位数送到最右方便使用常规分区逻辑三数取中实现只有几行却能把已排序数组从最坏情况变成最好情况因为三个位置的中位数正好就是整个数组的分位点。我自己在压测一个接近有序的大文件排序时就靠这个优化把耗时从几十秒降到了几百毫秒效果非常可观。3.4 三路快排专治大量重复元素遇到大量重复元素的数组比如按性别统计用户、按状态值切分订单普通快排会吃不消。Lomuto分区在全等数组上尤其会退化成O(n²)因为每次分区的结果永远是一边很大一边很小。三路快排3-way quicksort把数组分成三段小于基准的、等于基准的、大于基准的。等于基准的元素不再参与后续递归处理重复数据时效率极高。public static void quickSort3(int[] a, int low, int high) { if (low high) { return; } int pivot a[low]; int lt low; // 左边界等于区的起始 int i low 1; int gt high; // 右边界等于区的结束 while (i gt) { if (a[i] pivot) { swap(a, lt, i); } else if (a[i] pivot) { swap(a, i, gt--); } else { i; } } quickSort3(a, low, lt - 1); quickSort3(a, gt 1, high); }这段代码的思路来自荷兰国旗问题lt指针维护小于区gt指针维护大于区i指针遍历中间区域。比基准小的换到左边并把lt右移比基准大的换到gt处并把gt左移等于基准的i直接右移。循环结束后lt到gt区间里全是等于基准的值直接跳过不再递归。全等数组的场景下三路快排的一次遍历就能结束全部排序过程复杂度从O(n²)降到O(n)。如果你要处理的数据已知有大量重复三路快排是性价比很高的选择。Java标准库对对象类型的排序没有直接用快排而是用了稳定的归并排序变体但不少高性能排序库在特定数据分布下仍然会切到三路快排的思路。4. 工程世界里的快排早就不是原始版本了4.1 Java的Arrays.sort到底用了什么很多写Java的同事多年来都把快排很危险挂在嘴边但他们在JDK里调用Arrays.sort时其实根本不用担心最坏情况。Java 7开始Arrays.sort对于基本类型数组使用双基准快速排序Dual-Pivot Quicksort这个算法由Vladimir Yaroslavskiy提出荷兰算法大神Tim Peters和Joshua Bloch等人都参与过讨论和验证。双基准快排的思路是在一轮分区里选两个基准pivot1和pivot2把数组切成三段小于pivot1的、介于pivot1和pivot2之间的、大于pivot2的。相比单基准快排它在很多数据分布下需要的比较次数更少排序速度大约能再提升几个百分点。但是注意它依然不是稳定排序依然有退化空间。所以JDK内部在实现时做了多重防御小数组切到插入排序、递归深度过深切换堆排序也就是内省排序的策略保证最坏情况不会真的出现在你的线上环境里。而Arrays.sort对于对象数组用的是TimSort。为什么因为基本类型的排序只关心值相等元素怎么排序都无所谓但对象排序往往涉及Comparator甚至涉及多个字段的复合排序一旦快排把人家的相等对象顺序打乱后续再按另一个字段二次排序时结果就可能出错。稳定性在这里成了硬需求所以JDK放弃快排选择了归并排序优化的TimSort。4.2 C的std::sort与内省排序C标准库里的std::sort普遍采用内省排序introsort。它本质上是一个混合体主体是快速排序但会跟踪当前递归深度。一旦递归深度超过2倍的log2(n)说明分区质量糟糕继续用快排只会越陷越深于是算法立刻切换到堆排序。这种设计非常实用。堆排序保证O(n log n)的最坏情况但常数比快排大快排平均性能好却怕最坏情况。内省排序把两者的优点拼在一起绝大多数时候用快排的快速分区分不动了再用堆排兜底。这个思路是David Musser在1997年提出的后来的C标准库基本都沿用了。所以你在C里随手写std::sort并传入一个有数十万元素的vector时底层其实早就替你设好了安全带。把JDK和C的行为对比着看你会发现工程世界对快排的态度是既用又防用它的平均性能和原地特性防它的退化、防它的不稳定性、防它的递归开销。这不是对霍尔的背叛恰恰是对他思想的完善——把简单算法做进工业级运行时本来就该如此。4.3 稳定性与插排优化的取舍除开稳定性另一个容易被忽略的点是小数组到底怎么处理。快排递归到区间很小的时候继续递归的性价比很低函数调用开销、基准选择开销都不划算。insertion sort在几乎有序的小区间上表现极好所以JDK和很多算法库都会对16或32大小以下的子区间直接改用插入排序。我在写自己的排序工具时也沿用了这个策略当递归传入的high - low小于16时直接调用一个本地插入排序方法。实测下来这个改动在几万级别的数组上都有一两成的性能收益数据量越大收益越明显因为最底层递归被砍掉了绝大多数。注意这个优化并不是改变快排本身而是工程上压缩递归树底部的无效花销。还有一件事提醒一下快排不是线程安全的算法。如果多个线程共享同一个数组、对不同的子区间同时做递归快排分区间可能重叠导致数据错乱。多线程排序应该使用并行归并排序或者Fork/Join框架并确保每个子任务操作互不重叠的区域。5. 手写快排翻车现场常见问题与排查速查5.1 越界和死循环新手最容易写的两个故障快排边界条件多手写代码时几乎每个人都会踩坑。我每年面试都能看到看起来差不多但一跑就崩的快排版本。最常见的两个bug一个是数组越界一个是死循环。数组越界往往出在内层while循环。霍尔分区里如果内层循环没有加ij判断左指针会一路右滑直到超出数组右边界然后直接访问a[i]时抛出ArrayIndexOutOfBoundsException。正确写法是while (i j a[i] pivot) i; while (i j a[j] pivot) j--;注意先判断指针位置再访问数组元素。这个顺序一旦颠倒崩溃只是时间问题。同理Lomuto分区里循环遍历完jhigh后swap基准和i1时i1一定在[low, high]范围内但如果low和high传成了非法值就可能在递归启动时就出问题。死循环的典型场景是数组中存在等于基准的元素分区后左右两边都包含基准或其他相同元素递归调用时的区间没有严格缩小导致永远递归下去直到栈溢出。排查方法很简单在递归函数第一行打印low和high观察区间是否真正收敛。5.2 已排序数组与栈溢出另一个高频事故是对已经排好序的大数组做快排。固定选末尾为基准时有序数组的每次分区都产生一边空、一边n-1的结果递归深度会达到n层。n是十万时JVM默认栈深度根本不够直接抛出StackOverflowError。这不仅是性能问题是直接崩溃。解决办法前文已经提到随机化基准、三数取中或者改用内省排序。我这里多说一个实战技巧递归深度很深时优先递归区间小的那一侧把区间大的那一侧留到循环里继续处理可以显著降低最大递归深度。虽然Java标准库没有像C那样直接内置内省排序给用户排序数组用但你在自己写快排时完全可以模拟这个策略把最坏递归深度压到O(log n)量级。5.3 全等数组为什么比乱序数组还慢抽查数据里全是相等的元素时性能反而不如乱序数组这很反直觉但确实会发生。Lomuto分区遇到全等数组每次遍历所有元素都符合a[j] pivoti指针一路交换每次分区后基准还是归位到最右侧递归区间压不下去。复杂度最后落到O(n²)不说交换还特别频繁。三路快排是这个问题最直接的解药。如果你不能确定数据分布但又不想在代码里塞进三路分区这种更复杂的逻辑一种次优的折中是在分区之前先随机抽样检查几个元素如果发现大量重复再临时切到三路快排。这种动态策略在许多排序库里有实现比如Go语言标准库在排序时就会根据数据类型自动选择不同的核心算法。5.4 快速排序问题排查速查表症状可能原因排查与解决递归栈溢出递归深度过大或区间没有收敛改用随机/三数取中基准先递归小区间或改用内省排序数组越界异常内层while缺少ij判断先判断指针范围再访问元素校验递归区间参数排序结果乱序分区后的递归区间划分错误检查递归边界Lomuto用low~i和i2~highHoare用low~j和i~high大量重复数据性能骤降普通分区无法处理等值元素用三路快排或使用JDK自带的排序方法多线程环境下数据错乱多个线程同时操作同一数组区域加锁、使用并行归并排序或复制数据确保无共享可变状态小数组性能反而差递归和函数调用开销太大区间长度小于16时切到插入排序排查时建议先加日志打印每次分区的low、high和pivot位置观察分区是否在缩小、基准是否归位。排序类bug不像业务bug那样有报错堆栈可以层层定位靠的是对算法每一步的精确推演。我调试自己的快排实现时最常用的一招是用随机数组和系统的Arrays.sort做对照测试每次排序后逐元素比对一旦有差异就缩小到一个最小复现集再用单步调试看分区细节。这个方法笨但可靠。回到霍尔爵士。他1960年在一台慢得发指的机器上写出的那几十行代码如今每天在全球数以亿计的服务实例里运行着。快速排序之后他又在程序验证、并发理论、编程语言设计上留下了一连串深刻的足迹而他却用一句发明null引用是十亿美元错误跟后来的程序员们开了一个苦涩又诚实的玩笑。对我这样的普通工程师来说霍尔的传奇不在于拿了图灵奖不在于写了教科书而在于快速排序这个名字已经融进了我每天打开编辑器、运行测试、查看日志的日常之中。每次写下那五行递归都是跟这位老人的一次隔空交流。走好爵士。