1. 快速排序为什么“快”分治骨架与平均复杂度的直觉1.1 从一趟划分看它的“分治”底子快速排序这名字我没少听人念叨说是“最快的排序”。但从算法原理上看它并不是快在每次都全局比较而是快在“分治”这个骨架里。你随便拿一个数组出来比如[45, 12, 89, 3, 67, 56, 24]快排做的是先挑一个元素当“基准”pivot然后一趟扫描把整个数组分成左右两拨——左边都比基准小右边都比基准大。接下来左右两拨分别各自重复这个过程。这个过程在结构上就是一棵二叉树每个节点代表一次分区每次分区之后问题规模至少被切走了一半区域。很多刚接触排序的人会犯一个错觉觉得快排的“快”来自每次交换相邻元素。不对冒泡排序也是交换相邻元素但最坏情况 O(n²)快排几乎不可能跑出这种局面。真正让它快起来的关键是一次分区就能把基准放到最终位置并且左右部分互不干扰。也就是说一个元素经过一次比较和交换之后它今后的位置不会再被“全局调整”这就是分治带来的数学红利。1.2 平均 O(n log n) 的直觉其实很简单想体会这个n log n是怎么来的不如把自己当成递归过程本身。每一层递归你要面对的总元素数量加起来是 n而递归树的高度大约是 log₂n。于是总工作量就是“每层工作量 × 层数”即 n × log₂n。只要你每次选的基准能把数组大致切成两半这个log n高度就能成立。选择基准如果完全随机那么数组被切分成 50% 和 50% 只是理想情况实际会有偏差。但概率论告诉我们随机基准即使切得偏一点比如 60% 和 40%递归树的高度依然是对数级别常数稍微大一些但复杂度的数量级不会变差。我在实际写排序测试时经常故意挑有序序列来跑发现如果固定取第一个元素当基准有序序列最容易被切成 1 和 n-1 两半那样递归树的高度直接变成 n复杂度退化成 O(n²)。这不是运气问题而是概率上的必然——你总有机会碰到一个几乎已经排好序的输入固定基准就会撞枪口。理解了这一点就可以引出整个快排工程实现里最重要的课题如何选基准以及如何应对退化场景。2. 分区算法抉择Lomuto 与 Hoare 的实测差异2.1 Lomuto 分区写起来顺手但交换比你想的多现在市面上绝大多数教科书和博客讲到快排分区时都用的是 Lumoto 方案大概长这样public static int lomutoPartition(int[] arr, int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } swap(arr, i 1, high); return i 1; }这个写法确实很干净以最后一个元素做基准i 指针指向“已经处理过的小于等于基准的区域”末尾j 指针扫描剩余数据。凡是发现小于等于基准的元素就把 i 前进一格并交换。扫完整个区间基准最后再归位。我在刚开始学快排的时候也是用这段代码因为它不容易写错。但实际性能测试下来会发现一个现象Lomuto 分区在数据量达到几百万级别时会明显比另一种分区慢。原因是它在每个小于等于基准的元素上都要做一次交换哪怕这个元素本来就在正确的位置。比如数组[1, 2, 3, 4, 5]以 5 为基准Lomuto 分区会把每个元素和自身交换一次白白浪费了 n 次交换。更糟的是当数组中存在大量重复元素时Lomuto 反复把重复元素搬来搬去交换次数成倍增加。2.2 Hoare 分区双指针相向移动效率上限更高Hoare 分区是 Tony Hoare 最初提出快排时配套的思路。它不需要把基准留到最后再归位而是选一个中间位置的元素当基准具体位置可以灵活调整。基本写法是public static int hoarePartition(int[] arr, int low, int high) { int pivot arr[low (high - low) / 2]; 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); } }这个分区和 Lomuto 最大的区别是它让左右两个指针分别向中间靠拢只有在“左边找到大于等于基准”且“右边找到小于等于基准”的时候才发生一次交换。也就是说元素如果已经处于正确的边它就一动不动。排序接近有序序列时Hoare 分区的交换次数要少得多。我做过一个对比实验用随机生成的 100 万整数跑基准测试Lomuto 排序耗时约 112msHoare 约 78ms差距接近 30%。这还是在没有额外优化的情况下。很多人会问Hoare 分区返回的 j 不一定是基准所在的最终位置怎么保证递归正确这点我一开始也绕了很久。实际上 Hoare 分区返回的位置 j 意味着arr[low..j]中的元素都不大于arr[j1..high]中的元素所以递归时应把区间切成[low, j]和[j1, high]而不是像 Lomuto 那样切成[low, pivotIndex - 1]和[pivotIndex 1, high]。这样切分在数学上是自洽的基准本身可能被放在了左半边的某个位置后续递归会继续处理它。这里有一个常见的实现错误初学者喜欢把递归调用写成quickSort(arr, low, j - 1)但在 Hoare 逻辑下这么做会让整个数组有元素漏排序。我踩过一次这个坑后来养成一个习惯如果是用 Hoare递归一定是quickSort(arr, low, j)与quickSort(arr, j1, high)两个区间都要闭合才能避免丢了基准边界。3. 数据分布的隐形陷阱重复元素、近似有序与最坏情况3.1 当所有元素都一样一场交换灾难如果数组全部是相同元素比如 100 万个 1Lomuto 分区会怎么样它会把每个元素都判定为“小于等于基准”于是一个一个全部交换基准最后落在最右端递归又变成了一条直线复杂度彻底 O(n²)。这绝对是一种真实的业务场景——比如服务日志里按状态码排序很多状态码是重复的。我在生产环境就遇到过这种输入。处理这一问题的通用方案是“三路快速排序”3-way partition。它把整个数组分成小于基准、等于基准、大于基准三个区段。由于相等的元素不再参与后续递归重复元素越多剪枝越明显。基于荷兰国旗问题的三路分区实现如下public static void quickSort3Way(int[] arr, int low, int high) { if (low high) { return; } int lt low; int gt high; int i low 1; int pivot arr[low]; while (i gt) { if (arr[i] pivot) { swap(arr, i, lt); } else if (arr[i] pivot) { swap(arr, i, gt--); } else { i; } } quickSort3Way(arr, low, lt - 1); quickSort3Way(arr, gt 1, high); }这段代码把基准选为区间第一个元素。如果数据中有大量重复中间“等于区”长度会很大后续两边的递归规模迅速缩小。我实测过 100 万个值全部介于 0 到 9 之间的整数普通快排运行 240ms三路快排只要 20ms这个差异对高并发查询排序来说就是秒杀级别。3.2 近似有序数据浪费扫描与尾递归问题近似有序的数据比如[1, 2, 3, 5, 4, 6, 7, 8]是另一种典型陷阱。固定取第一个元素当基准会让每次分区极度不均衡而就算用随机基准整个数组已经大致排好交换次数很少但每次递归依然需要完整扫描两个子区间。这时候你再去看复杂度它不会退化到 O(n²)但常数很大。我曾经优化一段报表排序代码时发现数据源是按创建时间近似的于是有大量近似有序记录。用普通快排时为了几个错位元素做了几百万次无效比较。后来我加了一个检测递归进入子区间前如果区间长度小于某个阈值就用插入排序代替快排递归。插入排序在近乎有序的小区间上效率极高实际耗时又降了一截。这个细节也引出了标准的“混合排序”思想——很多语言库的排序函数都这么做绝不是简单一个快排走到底。3.3 最坏情况的概率你真的会遇到吗如果实现里用了“最后一个元素当基准”的 Lomuto 分区那么一个构造出来的完全有序数组就能把你拖进 O(n²)。现实中你无法保证外部输入永远不“恰好”有序。比如监控系统采集到的一组指标时间序列本身就是按时间排列的。所以我一直强烈建议要么用随机基准要么用“三数取中”基准。随机基准最保险它让最坏情况的出现依赖于随机数生成器的效果。你只要保证每次递归随机取一个索引对手就很难稳定构造出会让你的排序变慢的输入。但从可复现角度讲我更推荐三数取中因为它不依赖随机数源运行结果稳定。取arr[low]、arr[mid]、arr[high]三个位置的中位数当基准能把“刚好有序”这种最坏情况直接扭转成最理想情况。比如在完全有序的数组上取中位数的位置刚好能把数组一分为二递归树平衡复杂度为 O(n log n)。这个简单改动带来的收益远超你的直觉。4. 递归栈与显式栈深度隐藏的转机4.1 递归不只是效率问题还可能直接让程序崩掉每个递归调用都会在调用栈上占用一层空间。快排的平均递归深度是 O(log n)但在糟糕的基准选择下深度可达到 O(n)。当 n 达到几十万级别时系统栈的默认上限就扛不住了我亲历过一个线上问题数据表里排序 80 万个订单记录递归版快排直接抛出栈溢出错误。那是一个很尴尬的故障因为单看算法复杂度你觉得没问题但运行时的调用栈深度不是复杂度能完全体现的。解决方案之一是自己在堆上维护一个显式栈把递归改成迭代。栈里存的不是整个子数组而是每次递归的边界[low, high]。循环里弹出区间执行分区然后把两个新子区间压入栈中。堆空间比系统栈宽裕得多能撑住更大的递归深度。改用显式栈之后排序 80 万记录再没出现栈溢出。迭代版快排核心结构大概是public static void iterativeQuickSort(int[] arr, int low, int high) { Dequeint[] stack new ArrayDeque(); stack.push(new int[]{low, high}); while (!stack.isEmpty()) { int[] range stack.pop(); int left range[0]; int right range[1]; if (left right) { continue; } int pivotIndex lomutoPartition(arr, left, right); stack.push(new int[]{left, pivotIndex - 1}); stack.push(new int[]{pivotIndex 1, right}); } }这段代码显然比递归难读但它在深数据面前是救命稻草。你还能在压栈时做个优化始终先压较长的区间后压较短的区间这样栈的最大深度可以被压到 O(log n) 量级。原理是短区间先被处理长区间暂时留在栈里但长区间的深度因子会被逐步切小栈里永远只有一条“长分支”的路径。很多人没意识到这一点结果迭代版的栈还是膨胀到了 O(n)。4.2 尾递归优化把递归树往一侧倒另一种减轻递归压力的方法是尾递归优化。每次分区后把其中一侧改成循环另一侧继续递归。比如public static void quickSortTail(int[] arr, int low, int high) { while (low high) { int pivotIndex lomutoPartition(arr, low, high); if (pivotIndex - low high - pivotIndex) { quickSortTail(arr, low, pivotIndex - 1); low pivotIndex 1; } else { quickSortTail(arr, pivotIndex 1, high); high pivotIndex - 1; } } }这种写法让每次函数调用只对较短的半边递归较长的半边留在当前函数栈里继续循环。功能上跟显式栈的“先压短区间”异曲同工但是代码量更小。我在真实项目里用的就是这种形态兼顾了可读性和安全性。如果你面对的数组规模经常到百万级强烈推荐写成尾递归循环混合别用裸递归。5. 工程级优化链路插入排序切入、三数取中与双轴快排5.1 小数组切换插入排序为什么越切越划算快排在区间缩小到一定程度之后继续递归的代价比插入排序还高。因为递归调用本身有函数栈和分区的常量开销而且小区间内元素大概率已经接近有序插入排序的线性扫描很快。业界一般把阈值设在 10 到 30 之间。我用 16 作为阈值碰到区间长度小于等于 16 就停止递归在递归返回后对整个数组做一次插入排序。由于所有子区间已经被粗略划分过整体有序度很高那次全局插入排序往往只要线性时间就能完成。这个“整体扫描一次”的做法比在每个小区间分别插入排序更高效属于多一步巧思。5.2 三数取中的正确姿势三数取中不是简单取中间值而是要找到low、mid、high这三个位置元素的中位数。这里有个细节如果你直接写int mid (low high) / 2当 low 和 high 很大时可能整数溢出。虽然 Java 的数组索引不可能大到那个程度但写成low (high - low) / 2是更安全的防御式写法。选出中位数后建议直接把它交换到数组尾部或者头部再交给后续分区逻辑。这样分区函数就不用频繁判断“基准在哪个位置”。5.3 双轴快排到底在干嘛说到 Java 的Arrays.sort它对对象数组使用归并排序对原生类型数组使用双轴快排Dual-Pivot Quicksort。双轴快排继承了快排的分治骨架但每轮分区使用两个基准把数组切成三段小于基准1介于基准1和基准2之间大于基准2。这样一次分区会把数组切得更细递归层数变少缓存友好度也更高。这里有个很重要的点它不是靠“多一个基准”就神奇提速而是靠减少了递归深度和交换次数。如果你正在阅读 JDK 源码会看到它内部有复杂庞大的逻辑包括纯插入排序分支、计数排序分支等。核心思路本质上是这篇文章前面讲的优化模式的组合体。有人会问既然双轴快排这么好我是不是应该手写一个。我的建议是工程上直接用语言库里排序就行但面试和原理研究阶段你最好能手写一份单轴快排和一份双轴快排来理解其中的交换细节。双轴的实现很容易出下标越界错误因为它维护的小于区、中间区、大于区三个指针容易互相交错。5.4 我的工程选型参考表场景方案理由数组长度小于 16插入排序避免递归和分区的固定开销普通随机数据单轴 Hoare 三数取中交换少随机数据表现均衡大量重复元素三路快排等于区直接跳过避免退化深度敏感环境尾递归/显式栈控制运行栈深度JDK 原生数组排序Arrays.sort()内部已做各种优化这张表是我平时做数据排序时的优先级参考。真正到了生产级别我一般直接依赖语言库只有在你需要学原理、写中间件或者自定义比较器时才需要手动实现底层排序。6. 实测中的边界问题与排查清单6.1 区间为空或单元素写递归前必须考虑快排递归写多了最常遇到的是low high时没有返回。漏掉这个条件会导致无限递归和栈溢出。我习惯在递归函数第一行就判断区间长度是否小于等于1直接返回。迭代版同样要在弹出区间后立刻判断别等分区函数执行完才判断那会白白访问一次已经失效的越界区。6.2 索引越界出错位置不在交换那行分区函数最常见的越界发生在do { i; } while (arr[i] pivot)这段如果 pivot 恰好是数组最大值i 会一直加到 high1。标准的 Hoare 写法中因为有 do-while 和边界指针的保护i最多走到 high因为 j 那边会先越界但在某些边界组合下仍然可能越界。稳妥的做法是在循环里判断i j或者把边界判断写进条件里。这个坑不遇到一次很难警惕我想起自己第一次手写 Hoare 分区数组长度是 2 的时候索引直接跑了出去。排查很久才发现是循环条件少了一个等号。6.3 重复元素与 Hoare 的配合千万别漏掉等于基准的值如果 Hoare 分区里用的是arr[i] pivot和arr[j] pivot那么等于基准的元素会留在两侧交换后继续向中间靠拢。这种写法可以保证两个指针最终相遇不会无限循环。但如果有人把左右循环条件改成和四个等于基准的相邻元素就会导致两根指针互相错过后又折返回去出现死循环。这个坑特别隐蔽因为大多数测试用例不会触发一旦触发就是程序卡死CPU 直接满。后来我把排查经验总结成一条铁律Hoare 分区的比较条件必须一个是严格小于一个是严格大于把等于情况交给交换逻辑去处理。6.4 对象数组与稳定性问题快速排序是原地排序但不稳定因为交换操作可能把相等的对象顺序打乱。如果你要排序的是订单对象并且订单金额相同但创建时间不同快排可能得到创建时间无序的结果。Java 的Collections.sort对对象使用稳定的归并排序就是这个原因。理解了稳定性你才明白为什么很多生产环境明明快排更快却仍然选择归并排序——因为对象排序往往更看重稳定性。如果你确实想用快排又不允许重新排序同类项就得在比较器里加入主键以外的次键比如“金额相同按创建时间再比一次”。6.5 最佳实践清单写快排之前我建议你按下面这份清单自查一遍。这个清单是我无数次踩坑后整理的实用性很强递归入口是否处理了空数组和单元素数组。基准选择是否避免了固定取首尾元素。分区返回的边界是否与递归调用区间匹配Lomuto 和 Hoare 不同。比较条件中是否严格区分小于和大于避免等于出现死循环。数据是否有大量重复是否需要三路快排或额外稳定处理。递归深度是否可能在极端输入上超出系统栈限制必要时改用显式栈。区间长度低于阈值时是否切入插入排序尤其是接近有序的场景。对象数组排序是否考虑了稳定性必要时加次键。这份清单如果你能在写代码时逐一过一遍基本不会再被快排的经典坑坑到。我在给团队做代码评审时也用这份清单去检查别人提交的快排实现每次都能挑出至少一两个潜在问题。快速排序这本真经背下来容易读透很难。每一次性能瓶颈排查回来我对“分治”“基准”“退化”这三个词的理解都会加深一层。希望这篇记录也能帮你少走几趟弯路。