★ FEATURED ARTICLE 关于排序这件事很多开发者工作几年后可能已经不怎么手写排序算法了但面试时“请手写一个快速排序”依旧是高频题。快速排序作为经典的分治排序算法除了应付面试在实际工程里也是很多排序库的底牌比如 Java 对基本类型排序就用了双轴快排。这篇就把快速排序从头到尾拆开讲从分治思想、基准选择、Java 实现、优化策略到常见坑点一次聊透。适合看这篇文章的朋友有几类刚学排序算法、想彻底搞懂快排原理的同学准备面试、需要快速复习手写代码的开发者以及工作中要处理数据分析、批量排序想选对排序策略的技术人。我会用“生活化类比 代码逐段拆解 实测经验”的方式展开不堆术语但也不会为了好懂而丢失关键细节。看完你不仅能手写快排还能说出为什么这样写、什么时候它慢、怎么优化。1. 快速排序的核心思想是分治1.1 先搞懂分治策略快速排序英文是 Quick Sort核心思想总结成四个字就是“分而治之”。什么叫分而治之就是把一个大问题拆成若干小问题先解决小问题再合并结果。对应到排序场景快排不直接对整体排序而是先选一个元素出来当“基准”pivot然后扫描整个数组把所有比基准小的放左边所有比基准大的放右边这样基准就落到了它最终该在的位置。接下来左右两半再分别重复这个过程直到子数组只剩一个元素或者空排序自然完成。这和你整理一堆文件很像。假设面前有 100 份编号混乱的合同你想整齐排好。第一步先抓一份出来当参照比如编号 50然后扫一遍编号小于 50 的丢左边大于 50 的丢右边。50 这个位置就固定了。接着对左边那堆再做同样的操作右边那堆也一样不断拆分下去每堆都越来越小最终全部有序。关键点在于每次划分后基准元素不用再参与后续排序因为它已经回到了最终位置。这个“每轮至少固定一个元素”的性质是快排高效的重要基础。分治并不难理解但难在实现边界。很多初学快排的人写递归时容易出问题就是没想清楚“基准在分区后到底该放在哪里”“递归区间怎么分割”。后面我会结合代码细讲。1.2 基准元素怎么选是有讲究的基准元素的选择直接决定快排的“快慢”。最常见的方案有三种。第一种是固定选第一个或最后一个元素。实现最省事但存在致命缺陷如果数据本身有序或接近有序每次划分都只会产生一边空、一边 n-1 的极端结构递归深度退化成数组长度 n时间复杂度直接从 O(n log n) 掉到 O(n²)。面试中常见的“快排什么时候最慢”答案就是这里。第二种是随机选基准。思路是随机挑一个元素当 pivot从而让数据的有序性不再影响划分质量。这种做法能有效降低退化概率工程中也常用。但要注意随机数生成本身也有成本所以需要权衡。第三种是三数取中法。从子数组的第一个、中间位置、最后一个元素中取中间大小的那个值作为基准。这个方法不需要随机数大多数情况下能避免有序数据带来的退化代价也只是多比较几次非常划算。如果你想在面试中展示一点工程师思维推荐提三数取中。我个人在实际项目里习惯的做法是小的排序用插入排序兜底大的排序用三数取中选基准递归深度过深时切换堆排序。这套组合策略其实和很多工业级排序库的做法一脉相承。理解基准选择的重要性才能理解快排为什么会有这么多“优化版本”。2. 快速排序的算法流程与复杂度2.1 核心流程与分区操作快速排序主流程可以用四步概括选取基准 pivot。分区partition一次扫描后把数组调整成“左边都小于等于 pivot右边都大于等于 pivot”的状态。对左右两部分递归执行同样的操作。子数组长度小于等于 1 时递归终止此时数组已经全部有序。分区是快排的核心操作实现方式主要有两种Lomuto 分区和 Hoare 分区。Lomuto 分区一般选最后一个元素当 pivot用一个索引 i 标记“小于等于 pivot 区域的尾部”。扫描过程中一旦发现当前元素小于等于 pivot就把这个元素交换到 i 的位置i 再前移一位。循环结束后把 pivot 从数组末尾交换到 i1 的位置分区就完成了。它的优点是代码清晰、不容易出错缺点是在某些情况下交换次数偏多。Hoare 分区则是双指针从两端向中间逼近。左指针向右扫描找到大于等于 pivot 的元素右指针向左扫描找到小于等于 pivot 的元素两边都找到后交换这对元素然后继续移动指针直到左右指针交错。Hoare 分区的交换次数通常更少性能更高但代码逻辑和递归边界比 Lomuto 绕一些。工程上两种都有应用初学者建议先从 Lomuto 入手理解分区思想后再挑战 Hoare。这里顺带提一个常被忽略的点快速排序不是稳定排序。分区交换过程中相等的元素相对位置可能发生变化。如果你在处理对象排序时要求“相同关键字的先后顺序不变”那应该选择归并排序而不是快排。这个点也是面试的加分项。2.2 时间复杂度与空间复杂度分析快速排序的复杂度是面试必问内容我把结论整理一下。最好情况是每次分区都恰好把数组对半分这时递归树高度是 log n每层整体扫描 n 个元素总时间就是 O(n log n)。空间复杂度主要是递归调用栈的深度在最好情况下是 O(log n)。平均情况同样是 O(n log n)这也是快排被称为“快速”的原因。最坏情况则是每次分区都极端失衡例如一个已经有序的数组如果固定取第一个元素当基准产生的结果就是递归深度为 n时间复杂度退化为 O(n²)空间复杂度也变成 O(n)。为什么最坏情况实际中很少遇到因为只要基准选得不过分偏快排的复杂度就在 n log n 级别。随机化基准和三数取中就是用来压制坏情况的。如果你真遇到了快排性能崩掉的场景可以检查两个方向一是基准选择是否太死板二是数据分布是否已经有序或大量重复。大量重复元素时如果分区不做特殊处理相等的值也可能导致划分不平衡这种情况可以引入“三路快排”来解决也就是把数组分成小于、等于、大于三个区域。想深入了解的话这部分值得单独钻研。3. 快速排序的 Java 实现详解3.1 Lomuto 基础版面试够用思路清晰下面这段 Java 代码是 Lomuto 分区的经典递归实现也是我建议初学者第一个手写通过的版本。public class QuickSortLomuto { public static void quickSort(int[] arr, int low, int high) { if (low high) { int pivotIndex partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex 1, high); } } private static int partition(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; } private static void swap(int[] arr, int left, int right) { int temp arr[left]; arr[left] arr[right]; arr[right] temp; } }这段代码里最关键的是 partition 方法中的变量 i。i 表示“最后一个已归位到左侧区域的元素下标”开始时 low - 1也就是左侧区域为空。for 循环里的 j 负责从 low 扫描到 high - 1每当发现 arr[j] 小于等于 pivot就把 j 位置的元素换到 i1 位置左侧区域扩大一位。扫描完成后arr[low..i] 全部小于等于 pivotarr[i1..high-1] 全部大于 pivot最后把 pivot 从 high 位置换到 i1数组就变成了“左小右大”的形态同时返回 pivot 的最终下标。建议你拿一组小数据在纸上走一遍比如 [4, 10, 3, 5, 1]把每次交换后的数组状态写出来。这样的手动模拟比看十遍代码都有效能彻底解决“为什么返回 i1”的疑惑。初学阶段不要跳过这一步我在带新人时发现凡是动手模拟过一遍的人后面写快排基本都不再犯边界错误。3.2 Hoare 双指针版性能更优细节更绕如果你希望在面试中展示更扎实的功底可以再掌握 Hoare 分区实现。它用两个指针从两端同时扫描遇到逆序对就直接交换交换次数明显比 Lomuto 少。public class QuickSortHoare { public static void quickSort(int[] arr, int low, int high) { if (low high) { int mid partition(arr, low, high); quickSort(arr, low, mid); quickSort(arr, mid 1, high); } } private static int partition(int[] arr, int low, int high) { int pivot arr[low]; int left low - 1; int right high 1; while (true) { do { left; } while (arr[left] pivot); do { right--; } while (arr[right] pivot); if (left right) { return right; } swap(arr, left, right); } } private static void swap(int[] arr, int left, int right) { int temp arr[left]; arr[left] arr[right]; arr[right] temp; } }这段代码最需要留意的是递归边界Hoare 分区返回的 right 不是基准元素的最终位置而是左右子数组的分界点。所以递归调用是quickSort(arr, low, mid)和quickSort(arr, mid 1, high)而不是 Lomuto 那种pivotIndex - 1的写法。很多人在改写这段代码时习惯性沿用了 Lomuto 的边界结果要么漏排一个元素要么陷入无限递归。这是 Hoare 版本最大的坑。另外还要注意Hoare 分区里左右指针的移动条件是严格小于、严格大于 pivot等于 pivot 的元素不会被交换。这样做的好处是可以避免大量重复元素时出现无限循环。如果你把条件写成小于等于、大于等于指针可能会在相等元素上卡住导致死循环。3.3 两种实现实测对比与选择建议我在本机用随机生成的 10 万、100 万个整数分别跑过 Lomuto 和 Hoare 两个版本。结论是在随机数据上 Hoare 的耗时比 Lomuto 少大约 15% 到 20%而且数据量越大差距越明显。但在接近有序的数据上如果不加优化两个版本的性能都会下降Hoare 同样会退化只是退化幅度略好一点。选型建议很直接如果你要写一个教学示例或面试基础答案Lomuto 足够而且代码更短、更好解释如果你要在实际项目中手写快排并追求性能用 Hoare 加三数取中更合适。但如果你真的在 Java 工程里需要排序我的建议是直接用Arrays.sort它内部的双轴快排经过反复优化远超我们自己手写的版本。手写快排的意义更多在于理解算法本质和应对面试。4. 常见问题、性能坑与优化策略4.1 递归边界和死循环怎么排查快排最常见的运行时问题一个是栈溢出一个是死循环。这两个问题的根源几乎都出在递归边界和分区实现上。栈溢出的典型场景是递归边界写错。比如递归前不判断low high或者在 Lomuto 版本里把quickSort(arr, low, pivotIndex - 1)写成了quickSort(arr, low, pivotIndex)。后者会导致基准元素重复参与排序因为 pivotIndex 位置的元素在分区后已经归位不需要再排序。一旦子数组一直无法变小递归就会越来越深最终栈溢出。死循环则更多出现在 Hoare 分区的指针移动条件上。刚才说过左右指针遇到等于 pivot 的元素时最好用严格小于和严格大于来移动。如果写成了非严格比较指针可能在等于 pivot 的位置卡住左指针不往前走右指针也不往回走while (true) 循环就永远不会退出。排查思路也有讲究先构造最小规模的用例比如两个元素、三个元素、全部相等、逆序排列。每一种情况都手动走一遍看分区后 low 和 high 是否在向中间缩小。不要直接在大数据上调试那样很难定位。我在实践中就吃过这个亏后来养成了“先跑小用例再跑随机大用例”的习惯排查速度提升了不少。4.2 最坏情况优化三数取中与随机基准前面反复提到最坏情况 O(n²)那怎么针对性优化最常见的手段是随机基准和三数取中。随机基准就是在分区前随机挑一个下标把该下标元素与当前区间的第一个元素交换然后继续原来流程。这样的好处是无论输入数据是否有序每次分区都带有随机性最坏情况的概率变得极低。代码改动很小成本只是生成一个随机数。三数取中则更“确定”一些取 low、middle、high 三个位置的元素排序后取中间值作为 pivot并把它换到 low 位置。这个方法不需要随机数而且能有效避免“有序数组配固定基准”的退化问题。编译器或排序库更偏好这类确定性的做法因为随机数在调试和复现时会让行为不好预测。如果想更进一步还可以用三路快排。三路快排把数组分成“小于 pivot”、“等于 pivot”、“大于 pivot”三个区间相等区间不再递归处理。这在大量重复元素的数据上表现极好比如一个全是相同数字的数组普通快排会退化但三路快排一轮结束线性时间就搞定了。Java 的Arrays.sort使用的双轴快排也融合了防退化和重复元素处理的思路。4.3 工程级优化技巧插入排序兜底与双轴快排思路另一个容易被忽略的优化是小数组时切换插入排序。快排的递归调用是有开销的当子数组长度小于某个阈值常见的是 10 到 16插入排序的常数小、缓存友好反而比继续递归快排更快。所以在很多工业级实现里快排会写成类似这样private static final int INSERTION_SORT_THRESHOLD 10; public static void quickSort(int[] arr, int low, int high) { if (high - low 1 INSERTION_SORT_THRESHOLD) { insertionSort(arr, low, high); return; } int pivotIndex partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex 1, high); }对长度小于 10 的数组直接走插入排序能省掉大量递归调用整体性能通常能提升 10% 左右。这种“混合策略”在经典算法优化中很常见也体现了真实工程中并不只依赖单一算法。双轴快排则是 JavaArrays.sort对基本类型排序所用的思路选取两个基准把区间分成三段理论上减少了比较次数。不过双轴快排实现更复杂普通业务代码里没必要手写。理解它只需要明白一件事快排的优化方向一直围绕着“基准选择”和“减少交换/比较次数”这两个核心。掌握了这些你再看任何快排变体都不会觉得陌生。5. 什么时候用快排什么时候别用5.1 适用场景与不适场景快排最适合的场景是数据量较大、存储在数组或内存连续结构中、对稳定性没有要求。典型例子包括对基本类型数组进行排序、对数值型统计数据做快速排序、实现 Top K 或第 K 大元素的快速选择。不适合快排的场景也很多。首先链表排序不建议用快排。因为快排需要频繁随机访问元素而链表的随机访问 O(n) 代价很高虽然快排分区在链表上也能实现但性能通常不如归并排序。其次对稳定性有需求时比如按成绩对学生排序成绩相同还想保留原先后顺序那就不能用快排而要用归并排序或 TimSort。第三数据量很小时也不必动用快排的递归逻辑插入排序或选择排序表现更好。我在实际工作中总结了一条经验用排序之前先问自己三个问题——数据规模多大是否要求稳定数据有什么分布规律三个问题想清楚排序算法的选择基本就自然浮现出来了。5.2 快排思想的延伸快速选择 Top K快排的 partition 操作还有一个意想不到的用途快速选择。我们不需要对整个数组排序只想找到第 K 大的元素那就可以重复使用分区思想。思路是这样的执行一次分区后pivot 落在下标 p。如果 p 恰好等于 K那么 pivot 就是第 K 大的元素直接返回。如果 p 大于 K就在左区间继续找如果 p 小于 K就在右区间找。平均时间复杂度是 O(n)比排序后再取 K 的 O(n log n) 快一大截尤其适用于大数据量 Top K 问题。这个技巧在实战中非常常用。我之前统计日志中的热点 IP 时就是先把 IP 的访问次数放到数组里然后做快速选择几百万条数据轻松拿到 Top 10。相比先全量排序内存和时间都省了很多。你在面试中如果能提到这个延伸用法也会让面试官觉得你对算法的理解不止停留在表面。另外快排的分区思路还能用来处理“荷兰国旗问题”三色排序把三种元素按序排列。这就是三路快排的原型。所以学快排不只是学一个排序而是在掌握一套实用的分治和分区技巧。我个人在实际使用中的体会是快排最迷人的地方不在于它能排序而在于它把“划分”这件事做到了极致。数组排序一次划分确定一个元素的位置找第 K 大一次划分确定一个候选区间处理重复元素三路划分让区间更精准。理解 partition 这三个字就是我掌握整个快排体系的关键。最后再分享一个小习惯每当我写完一个排序算法不会只看它能跑通而是会故意丢给它一些“刁钻”输入比如空数组、单元素、全相同元素、逆序数组、超大数组。这些边界测试会逼着你把边界条件和退化问题处理到位。如果你也能养成这样的习惯快排对你来说就不再是背代码而是真正长在手上的技能。
阅读完成 · 觉得有帮助？
