托尼·霍尔爵士走了享年92岁。计算机行业在这一刻失去了一个曾经用一页纸代码重新定义“排序”这个基础操作的人。大多数程序员认识他是因为快速排序Quicksort但排序只是他职业生涯的起点霍尔逻辑奠定程序正确性验证的根基通信顺序进程深刻影响并发系统的设计而他后来把自己当年设计的空引用称为“十亿美元的错误”。一个敢把自身缺陷做成经典的人值得我们认真复盘。这篇内容我打算把重心放在两个层面一是悼念和梳理托尼·霍尔留下的技术遗产二是把快速排序从思想到代码到工程踩坑完整讲透。特别是最近后台有不少朋友搜“快速排序 java实现”、“快速排序代码”那我就用Java为主线带你从零实现一个能真正上生产的版本顺带聊聊为什么托尼·霍尔当年能被后人称作“排序界的传奇”。1. 传奇落幕托尼·霍尔与快速排序的故事1.1 一个在莫斯科打草稿时诞生的算法1960年托尼·霍尔在莫斯科国立大学做访问学者当时他正在研究机器翻译。翻译系统里需要把一个包含上千个俄语单词的列表按字母顺序排列以便进一步做词形分析和匹配。那时候的计算机资源极其紧张内存很小磁盘访问又慢如果排序算法太复杂、交换次数太多程序根本跑不完。霍尔当时想出来的办法在今天看来简单又大胆选一个基准元素把列表分成两半一半比基准小一半比基准大然后对这两半分别重复同样的过程。这个思想今天叫“分治”但在当时几乎没有人把递归当做一个正经的工程工具来用。讽刺的是他自己起初也怀疑这个办法能不能落地因为他觉得递归调用听起来太像玩具。后来他花了不少时间在Elliott 503计算机上调试才让这个“玩具”变成了真正能高效排序的算法。快速排序随后在1961年公开1962年发表在《Computer Journal》上。论文名字就叫“Quicksort”霍尔在里面没有用花哨的术语而是直接给出了算法流程和实验数据。那个年代没有互联网没有算法平台的在线评判但这篇论文仍然迅速传遍欧洲和北美成为后续几十年排序算法研究与应用的重要源头。1.2 不只是排序一位图灵奖得主的完整生涯把托尼·霍尔简单称作“快速排序发明者”其实低估了他。他在1980年获得图灵奖获奖理由里明确提到他在编程语言定义、程序正确性验证和形式化方法上的贡献。这几项工作在当时的学界看来甚至比快速排序更“硬核”。霍尔逻辑在20世纪60年代末霍尔提出了一种用逻辑公式描述程序行为的方法。简单说你可以在代码之前写一个前置条件在代码之后写一个后置条件然后证明代码确实把“前置”变成了“后置”。今天很多静态分析工具和安全验证框架的底层思想依然源自霍尔逻辑。通信顺序进程CSP1978年他提出用“进程”和“通道”这两个抽象来描述并发系统。进程之间不共享变量只通过消息通信这会从根本上避免很多并发冲突。后来Go语言里的channel以及不少分布式系统设计都明确承认受CSP影响。空引用的反思1965年他在设计ALGOL W语言时引入了null引用。几十年后他在一次演讲中诚恳道歉说这可能是自己犯过的“十亿美元的错误”因为无数系统和语言因此多出了空指针异常。这个反思本身比很多“零失误”的技术人设更有价值。这些贡献让我觉得托尼·霍尔更像一个“定义问题边界的人”。他不在乎某个算法是否时髦而在乎一个抽象是否足够干净、是否能在复杂环境中经得住推敲。2. 快速排序核心思想为什么它这么快2.1 分而治之的直观理解快速排序的英文名Quicksort翻译成中文往往被理解为“快速”但它的精髓更接近“划分”。给你一副乱序的扑克牌你可以先随便抽一张比如抽到“红桃7”然后把所有比7小的牌放左边所有比7大的放右边。接下来左边那堆牌里再抽一张重复这个过程右边也重复。最终每堆只剩一张牌的时候整副牌也就排好了。这样做之所以快是因为每一轮比较之后大部分元素不需要再和全局所有其余元素比较。你只要保证“左边都小于某个数右边都大于某个数”这个条件在每一层递归里成立整体顺序就会自然浮现。归并排序同样是分治但归并排序需要额外的存储空间来合并结果快速排序是在原数组上通过交换完成额外空间主要消耗在递归栈上。2.2 一次分区到底做了什么“分区”是快速排序最核心的动作。以一个具体数组为例[5, 1, 4, 2, 8]假设我们取最后一个元素8作为基准pivot。分区要做的事情是把数组重新排列成这个样子基准左侧的元素都不大于它右侧的元素都不小于它然后返回基准最终的位置。指针i从数组头部开始指针j从头部开始遍历。每遇到一个小于等于基准的元素就把它换到左边区域。遍历结束后数组变成类似[5, 1, 4, 2, 8]基准8正好在最右位置索引是4。下一次递归时左侧对[5, 1, 4, 2]继续排序右侧为空。如果基准选得好比如每次都接近中位数那么递归深度是logn每一层每个元素最多参与常数次比较总复杂度就是O(n log n)。这个复杂度在排序领域属于理论最优之一因为基于比较的排序在最坏情况下不可能低于O(n log n)。2.3 平均快最坏也真的“很坏”快速排序最容易被面试官抓住的地方是最坏情况会退化到O(n²)。比如对一个已经排好序的数组如果每次取第一个或最后一个元素当基准那么分区根本没有起到“均衡切割”的作用每次只是筛掉一个元素剩下的仍然有序递归深度直接就变成了n。实际工程里怎么应对最简单的办法是“随机选基准”让最坏情况变成概率极低的事件或者“三数取中”从数组头、中、尾取三个元素的中位数当基准基本能避免平凡的最坏输入。我在后面的代码部分会都写出来方便你直接对照。3. 快速排序的Java实现从教科书版本到可靠工程版3.1 最直白的Lomuto分区写法先看一个绝大多数算法教材都会出现的版本。它逻辑清晰适合理解但不一定是最快的public static void quickSortLomuto(int[] arr, int low, int high) { if (low high) { return; } int pivotIndex partitionLomuto(arr, low, high); quickSortLomuto(arr, low, pivotIndex - 1); quickSortLomuto(arr, pivotIndex 1, high); } private static int partitionLomuto(int[] arr, int low, int high) { int pivot arr[high]; int i low; for (int j low; j high; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, high); return i; } private static void swap(int[] arr, int a, int b) { int temp arr[a]; arr[a] arr[b]; arr[b] temp; }这里的partitionLomuto选最后一个元素为基准。i代表“小于等于基准的区域的右边界”j负责扫描整个区间。遇到小于等于基准的值就把它丢到左边区域扫描结束后把基准从最右边换到i的位置。这样基准左边全是小于等于它的右边全是大于它的。这个版本有个小问题如果数组里有大量重复元素它的交换次数会偏高如果本身就是有序数组它还会退化到O(n²)。所以它适合教学不适合直接用到性能敏感场景。3.2 霍尔本人在论文中的分区方式Hoare Partition托尼·霍尔实现的原始方案其实和现代教材里常见的Lomuto分区不完全一样。他的分区用两个指针一个从左边找大于基准的元素一个从右边找小于基准的元素两者交换直到两个指针交错。public static void quickSortHoare(int[] arr, int low, int high) { if (low high) { return; } int pivotIndex partitionHoare(arr, low, high); quickSortHoare(arr, low, pivotIndex); quickSortHoare(arr, pivotIndex 1, high); } private static int partitionHoare(int[] arr, int low, int high) { int pivot arr[low]; int i low - 1; int j high 1; while (true) { do { i; } while (arr[i] pivot); do { j--; } while (arr[j] pivot); if (i j) { return j; } swap(arr, i, j); } }注意这个版本里pivot取的是区间最左元素。两个指针分别向中间推进左指针停在“大于等于基准”的位置右指针停在“小于等于基准”的位置然后交换。最终返回的j就是新分区点。后面递归时左区间是[low, j]右区间是[j 1, high]这和Lomuto版本的递归边界不太一样。Hoare分区的优势是交换次数通常更少尤其在随机数据上表现更好。但它的边界条件写起来比较绕不少人第一次写都会出现死循环。我建议如果你只在面试时用Lomuto版更容易写对如果真正要在项目里跑Hoare版加随机基准更接近库函数的实现思路。3.3 防止栈溢出的迭代实现递归版本简单优雅但当数据量很大且递归深度不可控时有可能直接抛出StackOverflowError。工程里更稳妥的做法是手动用栈模拟递归过程只把待排序区间的low和high压栈public static void quickSortIterative(int[] arr) { Dequeint[] stack new ArrayDeque(); stack.push(new int[]{0, arr.length - 1}); while (!stack.isEmpty()) { int[] range stack.pop(); int low range[0]; int high range[1]; if (low high) { continue; } int pivotIndex partitionHoare(arr, low, high); // 先把较大的区间压栈再把较小区间压栈可以减少栈的最大深度 if (pivotIndex - low high - pivotIndex - 1) { stack.push(new int[]{low, pivotIndex}); stack.push(new int[]{pivotIndex 1, high}); } else { stack.push(new int[]{pivotIndex 1, high}); stack.push(new int[]{low, pivotIndex}); } } }这段代码用ArrayDeque当栈每个元素是一个长度为2的数组保存区间上下界。你可能会想既然用了栈空间复杂度是不是变成O(n)了其实不是这里栈里最多保存的区间数量和递归版本的调用栈深度是一个量级平均仍然是O(log n)因为“先压大区间”这种策略能有效控制栈的大小。最坏情况下如果基准选得极差栈还是会变大但至少不会压爆JVM的方法调用栈。4. 性能优化从能用到能用得稳4.1 随机化基准随机化是挫败最坏情况的最实用手段。每次分区前随机挑一个位置和当前区间最左元素交换然后再执行Hoare或Lomuto分区。private static void randomPivot(int[] arr, int low, int high) { int randomIndex low ThreadLocalRandom.current().nextInt(high - low 1); swap(arr, low, randomIndex); }调用位置放在quickSortHoare或普通递归的开头。这样输入数据哪怕本身是最坏有序数组你依然能大概率把基准选到接近中间的位置时间复杂度回到平均的O(n log n)。在对抗恶意输入时这招尤其有效。我在实际项目中见过一个问题有人觉得随机数生成太慢就省掉了这步结果线上某个模块每天都处理一批特殊结构的数据排序耗时从几十毫秒直接飙升到几秒。加了随机化之后耗时曲线瞬间变得平稳。这个教训我一直留着。4.2 三向切分应对大量重复元素如果你要排序的数据里重复值极多比如有一大批用户等级、状态码、年龄字段普通快速排序会在重复元素上做大量无意义交换。三向切分3-way partitioning专门解决这个问题把数组分成三块分别是小于基准、等于基准、大于基准递归时只需要处理小于和大于两块。public static void quickSort3Way(int[] arr, int low, int high) { if (high low) { return; } int lt low; int gt high; int i low 1; int v arr[low]; while (i gt) { if (arr[i] v) { swap(arr, lt, i); } else if (arr[i] v) { swap(arr, i, gt--); } else { i; } } quickSort3Way(arr, low, lt - 1); quickSort3Way(arr, gt 1, high); }这段代码的核心是三个指针lt所有小于基准的元素都交换到它左边。gt所有大于基准的元素都交换到它右边。i当前正在扫描的位置。当遇到等于基准的元素时直接跳过不做交换。这样相同元素不再参与后续递归排序性能会好很多。Dijkstra当年提出过类似思路后来被广泛应用在Java、C的排序库实现里可见这个优化有多重要。4.3 Java库里的双轴快速排序是怎么回事如果你用过Java自带的Arrays.sort它对新版本中基本类型数组的排序并不是传统快速排序而是DualPivotQuicksort双轴快速排序。它是Vladimir Yaroslavskiy在2009年提出的改进版每次选出两个基准把数组分成三块区域小于小基准、介于两个基准之间、大于大基准。这相当于把每次分区的“宽度”加大在大量数据上能减少递归层数对比普通快速排序平均能快10%到20%。但有些细节值得注意Arrays.sort对对象数组用的是归并排序或TimSort因为对象排序往往需要稳定性对基本类型数组用双轴快速排序因为基本类型完全不需要保持“相等元素之间的原始顺序”。这说明一个道理语言库的设计者并不是“只选最快算法”还会考虑稳定性、适配已有代码语义、JVM开销等多方面因素。5. 排序算法全景对比快速排序的江湖地位5.1 快速排序、归并排序、堆排序怎么选很多初学者会把排序算法当成一道数学题觉得“哪个时间复杂度低就选哪个”。但工程选型要考虑数据规模、是否需要稳定、内存限制、缓存友好程度。下面这张表是我做过几轮压测之后的经验总结算法平均时间复杂度最坏时间复杂度空间复杂度是否稳定特点快速排序O(n log n)O(n²)O(log 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)但它每次堆调整的逻辑跳跃性很强对CPU缓存很不友好实际速度往往不如快速排序。归并排序稳定但O(n)的额外空间在大数组上是硬伤。5.2 快速排序在真实系统里的应用快速排序不是只在教科书和面试里出现。很多数据库执行查询计划时如果需要对中间结果排序且数据能全部读进内存大概率会采用类快速排序的算法。Spark、Flink的部分算子底层排序也会参考快速排序的思路。操作系统的内核里用于管理页面、设备调度的一些排序逻辑同样能看到分区排序的影子。你可能会问既然有Arrays.sort这样的库函数我们平时还需要手写快速排序吗这个问题得分场合面试和算法竞赛必须会手写因为考察的是对分治、指针、边界的理解。项目里如果数据量不大用库函数就行别重复造轮子。如果你在做大数据管道、实时流处理或者需要定制排序规则理解并改造快速排序的能力会变得很重要。比如我只想取Top-K那么快速排序的“部分分区”版本比全排序快很多。6. 快速排序实践中的经典坑与排查思路6.1 递归栈溢出有一次我在一个老项目中看到线上服务频繁崩溃报错就是StackOverflowError。查了一圈发现问题出在一个递归排序函数上线上有一批特殊订单数据顺序几乎固定而代码里选的基准恰好是第一个元素于是每次分区都只剥离一个元素递归深度到了几万层。解决办法有两步把递归改成迭代版本同时随机化基准。这两步做完之后系统再也没有出现过栈溢出。如果你暂时不想改代码结构也可以临时调大JVM的线程栈大小比如用-Xss8m但这只是缓解根治还得看算法本身。6.2 边界条件写错导致死循环快速排序的边界条件是重灾区。最常见的错误是分区函数返回的基准位置已经归位但递归时还把它包含在子区间里就会导致无限递归。另一个问题是Hoare分区里两个指针在相等元素上互相卡住不交换也不前进。我写Hoare版时也有一些土办法防御在进入while循环之前先判断low high而在分区函数内部用do...while而不是先判断再执行保证每轮指针至少移动一次。调试时还可以在分区函数入口打印三个关键变量low、high、pivot一旦发现某次区间长度没有缩小立刻就能定位。6.3 稳定性要求快速排序是不稳定的这意味着两个相等的元素在排序后可能交换相对位置。如果业务要求稳定排序比如按时间排序之后再按金额排序并且相同金额要保持原来的时间顺序这时不能用快速排序应该用归并排序或者直接使用对象数组的Arrays.sort。我在处理财务对账数据时踩过这个坑。第一版用快速排序跑得快但宕机事故后上游数据重推结果报表里明细顺序和原始流水对不上排查半天才发现是稳定性问题。后来换用稳定排序或者给数据加一个自增序号作为次排序键才彻底解决。6.4 小数组上反而更慢快速排序在数据规模很小的时候递归调用的开销会超过排序本身的收益。很多成熟的排序库都设置了“阈值”比如当区间长度小于某个值时改用插入排序。Java的Arrays.sort就内置了这个优化通常阈值在16到32之间。如果你在自己的封装里也用这个思路可以这样写public static void quickSortWithThreshold(int[] arr, int low, int high) { if (high - low 20) { insertionSort(arr, low, high); return; } int pivotIndex partitionHoare(arr, low, high); quickSortWithThreshold(arr, low, pivotIndex); quickSortWithThreshold(arr, pivotIndex 1, high); }数据量小时插入排序的O(n²)并不可怕因为n很小常数极小。这种“混合排序”策略在很多工业级排序实现里都有属于典型的工程调优。7. 托尼·霍尔留给下一代工程师的启示7.1 程序设计验证的“纪律性”霍尔一直强调程序不仅要能跑还要能用逻辑证明它是对的。快速排序虽然出名但他并不认为“能跑”就是终点。我们今天做的单元测试、契约测试、静态分析其实都是这种理念的延续。你在写任何核心算法前先写下输入范围、输出语义、边界条件代码质量会高很多。7.2 对简单抽象保持敬畏CSP模型能对并发产生巨大影响靠的不是复杂的语法而是“进程之间不共享状态”这个极其简单的规则。很多系统设计出现问题往往是因为抽象不够干净。快速排序也是一个道理——它不到三十行的核心逻辑足以让无数专家研究几十年。一个简单但边界清晰的抽象真的能改变世界。7.3 null引用给我们的教训托尼·霍尔那番关于null引用的反思我每次看都觉得特别真实。他抱怨自己早年引入了null但后来所有主流语言都在使用它。这说明技术在现实传播中具有很强的惯性。你今天写代码时觉得“方便”的某个设计十年后可能成为整个系统的历史包袱。所以做技术选型时想想未来维护的人是值得的。快速排序的每一行代码里都藏着霍尔那个年代的严谨与直觉。他用最朴素的方式解决了最迫切的问题又用一生的时间去让“正确性”成为一门可以学习的学科。每次我手写快速排序想起这段历史都会希望自己也能写出那种“简单到让人惊叹”的方案。最后分享一个小技巧如果你在面试里拿到排序相关的题目先别急着写代码停两秒问清楚数据规模、是否稳定、是否有重复值。这三个问题问出口你至少比一半的候选人领先了因为这意味着你真的在“工程化地”思考算法而不是背模板。托尼·霍尔在地下有知大概也会点点头。