快速排序是我这些年面试别人时几乎必问的一个算法也是我自己刚入行时反复写、反复理解的一道题。这个问题看着简单所有教材里只有寥寥几行代码但真正面试聊起来很少有人能把基准选择、退化场景、递归深度这些点讲清楚。我是做Java开发的日常业务代码里手写排序的机会其实不多但这道题背后的分治思想、复杂度分析和对递归的理解是实打实地影响着我写代码的方式。这篇就把我对快排的理解、手写实现和调试经验完整整理出来希望对正准备面试或者刚接触算法的朋友有一点实在的帮助。1. 快速排序的核心原理一篇讲透分治思想的骨架1.1 一句话理解快排选基准、分区、递归快速排序的核心可以用一句话说清楚任取一个元素作为基准把数组分成两半左边都比基准小右边都比基准大然后对左右两边分别重复这个过程。这里的关键在于分成两半这个动作专业叫法叫分区。分区结束后基准元素的位置就是它最终的位置——因为左边的都比它小右边的都比它大不管后续怎么递归它都不需要再动了。这个性质很重要它意味着快排是原地排序不需要额外的数组来合并结果。拿生活里的场景打个比方你有一摞随机摆放的试卷想按学号排好。快排的思路就是随便抽一张出来把学号小的放左边、大的放右边那张抽出来的试卷就摆在了它该在的位置。接下来对左边那一堆和右边那一堆重复同样的操作直到每一堆只剩一张或没有试卷。这个分而治之的思路并不复杂但落地到代码里就会遇到几个实际问题基准怎么选分区怎么高效地做递归到底会不会爆栈这些问题才是快排真正的考点所在。1.2 分区操作的内功双指针到底在做什么分区的写法有很多种面试最常见的是Lomuto分区和Hoare分区。我用Lomuto的写法来解释一下逻辑因为它直观、好写、不容易出错。基本思路是维护两个指针一个慢指针i一个快指针j。j从基准的下一个位置一直往右扫每当遇到比基准小的元素就把i往前挪一个位置并交换i和j指向的元素。循环结束后把基准和i指向的元素交换这样基准左边全是小于等于它的右边全是大于它的。以数组 [5, 3, 8, 4, 2] 为例选最后一个元素2作为基准j扫描到3比2大不动j扫描到8比2大不动j扫描到4比2大不动j扫描到第一个元素5时j从0开始5比2大不动循环结束把2与i指向的位置交换但你数一下就会发现这个例子里比2小的元素一个都没有分区完成后基准2成了最小值左侧为空右侧是 [5, 3, 8, 4]。这样的分区效果很差因为基准选得太极端了。这也就是为什么固定选取基准在某些数据分布下会引发灾难性退化——后面我会专门讲。分区代码本身不复杂但注意细节i的初始值是left而不是left减1或者0。很多人这里写错导致分区结果完全不对。还有交换基准和a[i]这个动作一定要在循环结束之后做因为i停在的位置就是最后一个比基准小的元素的位置。2. 快速排序的Java实现从最简写法到优化版2.1 最经典的模板代码先写对再优化很多人一上来就想写优化版本我觉得不对。快排首先要写得对然后再考虑快。最简单的模板代码大概是这样的public class QuickSort { public static void quickSort(int[] arr, int left, int right) { if (left right) { return; } int pivotIndex partition(arr, left, right); // 基准已经在最终位置左右分别递归 quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 1, right); } private static int partition(int[] arr, int left, int right) { // 选择最右边的元素作为基准 int pivot arr[right]; int i left; for (int j left; j right; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, right); return i; } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } }在主函数里调用时传入的是数组下标边界quickSort(arr, 0, arr.length - 1)。注意是arr.length - 1不是arr.length这是一个我见过无数人踩过的边界错误。递归的终止条件是left right也就是区间里没有元素或只有一个元素时停止因为这个情况下不需要再排了。这个版本能跑通面试时能解释清楚原理就够了。但它在数据刚好有序或者全部元素相同的情况下性能会直线下滑到O(n²)。这个问题在真实场景中很致命。2.2 优化一随机基准解决有序数据的退化问题固定选最后一个元素作为基准如果数组已经完全有序那么每次分区都会产生一个空区间和一个n-1的区间递归深度变成n时间复杂度退化成O(n²)。解决办法很简单在分区前随机挑一个位置把它和最右边的元素交换然后再选最右边的作为基准。这样基准的值就不受数据初始分布的影响了。private static int partition(int[] arr, int left, int right) { // 随机基准把随机选中的元素交换到最右边 int randomIndex left (int) (Math.random() * (right - left 1)); swap(arr, randomIndex, right); int pivot arr[right]; int i left; for (int j left; j right; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, right); return i; }这里计算随机下标的公式是left (int)(Math.random() * (right - left 1))。注意括号里的right - left 1漏掉1会导致范围少一个数永远选不到right这个位置。我见过有同学写成right - left结果某个元素始终不会被选中为基准虽然不影响最终正确性但会引入统计偏差。随机基准的作用是让任何固定分布的数据都有机会被打散从概率上保证了快排的平均表现。实际工程中Arrays.sort()对基本类型数组用的就是一种被称为双轴快速排序的变体它选择两个基准把数组分成三段进一步优化了大数据量下的性能。我后面会讲。2.3 优化二三数取中对抗已经有序的数据随机基准虽然好但随机这个词总让人心里没底万一随机到极端值呢这时候三数取中是一种更稳健的做法从区间的左端、中间、右端各取一个元素选出它们的中位数作为基准。这种做法在数组相对有序的场景下表现极好因为中间位置的元素大概率接近整个区间的中位数。它额外消耗的只是三次比较换来的是更稳定的分区质量。实现也不复杂private static int medianOfThree(int[] arr, int left, int right) { int mid left (right - left) / 2; // 简单的三个数排序中位数放在left位置 if (arr[left] arr[mid]) { swap(arr, left, mid); } if (arr[left] arr[right]) { swap(arr, left, right); } if (arr[mid] arr[right]) { swap(arr, mid, right); } // 此时mid位置的值就是中位数 return mid; }然后在partition里这样用private static int partition(int[] arr, int left, int right) { int pivotIndex medianOfThree(arr, left, right); // 把基准交换到最右边后面逻辑不变 swap(arr, pivotIndex, right); int pivot arr[right]; int i left; for (int j left; j right; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, right); return i; }我个人的实践建议是面试回答时可以先写固定基准版本然后主动提随机基准的优化如果面试官追问还有什么优化方案再引出三数取中。这样既体现了基础扎实又展示了对性能退化问题的深入思考。实际项目的性能需求不高的地方随机基准已经足够用了。3. 复杂度分析与工程实战快排为什么快又在哪里翻车3.1 时间复杂度的直觉与证明从最好到最坏快速排序平均时间复杂度是O(nlogn)这个结论很多面试者能背出来但问一句为什么就卡住了。我尽量不堆公式用直观方式讲清楚。假设每次分区都能把数组均匀地分成两半。第一轮对整个数组做分区需要比较n次左右第二轮对两个半区分别分区每个半区大约n/2次比较总次数还是n第三轮是四个子区间总次数依然是n。一共会分多少层呢每次对半切从n到1需要log₂n层。每层做n次比较总次数约等于nlogn。最坏情况是每次分区都特别不均匀比如一边是0个元素另一边是n-1个元素。这样第一轮n次比较第二轮n-1次比较第三轮n-2次……加起来是n (n-1) (n-2) ... 1 ≈ n²/2。这是O(n²)的由来。这段推导对面试很重要。因为面试官真正想听到的不是背结论而是理解递归结构对复杂度的影响。我建议你在纸上画一下递归树把每次分区的比较次数标上很快就会对nlogn与n²的区别有肌肉记忆般的直觉。3.2 空间复杂度为什么是O(logn)递归栈的账要算清楚快排是原地排序不需要额外的辅助数组来存元素。但它是递归实现的每层递归都会占用调用栈空间。最好情况下递归深度是logn所以空间复杂度是O(logn)。最坏情况下递归深度是n空间复杂度变成O(n)。这里的空间指的是栈帧的额外开销虽然每个栈帧只存几个变量但n足够大时依然可能触发栈溢出。我遇到过的一个真实场景用固定基准的快排对100万个已经排好序的整数排序进程直接StackOverflowError。这就是退化到最坏情况后递归深度过大导致的。解决办法就是前面说的随机基准、三数取中或者改用非递归实现。在工程代码里还一定要关注排序数据量这只是另一个维度的输入约束。3.3 快排与Java标准库的相爱相杀Arrays.sort到底怎么排日常开发中谁也不会真的自己写快排去排业务数据。Java的Arrays.sort()封装了排序逻辑但它内部对不同类型用了完全不同的算法。对基本类型数组它用的是双轴快速排序。这个算法把数组分成三段分别小于基准1、介于两个基准之间、大于基准2。相比单轴快排它在很多数据分布下比较次数更少而且对重复元素多的场景处理得更好。对对象数组它用的是TimSort一种稳定的归并排序变体。为什么对象数组不用快排因为快排是不稳定的相同key的对象在排序后可能交换相对顺序。对一个已经按姓名排好序的对象列表如果你再按年龄排序而两个年龄相同的人原本按姓名的顺序被快排破坏了那结果就乱了。归并排序保持稳定性所以对象排序默认走TimSort。这个差异在面试中经常被追问到值得你整理进自己的知识库。在实际项目中如果你需要稳定排序但排序的是基本类型且无关紧要可以直接用Arrays.sort如果排序的是对象且要求稳定就老老实实用Collections.sort或Stream.sorted它们会处理稳定性。4. 快速排序的进阶话题与性能提升思路4.1 非递归实现怎么用栈模拟递归过程递归版的快排在数据量极大时可能栈溢出。解决办法之一是用显式栈来模拟递归过程把待排序区间的左右边界压入栈中循环代替递归。public static void quickSortIterative(int[] arr, int left, int right) { Dequeint[] stack new ArrayDeque(); stack.push(new int[]{left, right}); while (!stack.isEmpty()) { int[] range stack.pop(); int l range[0]; int r range[1]; if (l r) { continue; } int pivotIndex partition(arr, l, r); // 把子区间压栈注意先压右区间还是先压左区间不影响结果 if (l pivotIndex - 1) { stack.push(new int[]{l, pivotIndex - 1}); } if (pivotIndex 1 r) { stack.push(new int[]{pivotIndex 1, r}); } } }这种写法在思路清晰的前提下大约10分钟能写出来。它的空间复杂度依然是O(logn)层次的但因为用的是堆上分配的栈结构不受系统调用栈深度的限制可以处理更大的数组。我是建议作为练习写的但对普通业务场景不是必须因为Arrays.sort已经足够快。4.2 小数组切换到插入排序让快排在细节上再快一点工程实现中还有一个常见优化当待排序区间长度小于某个阈值比如16或32时不再递归调用快排而是改用插入排序。原因很简单递归调用本身有开销而且当区间很小时插入排序的常数因子远小于快排。快排在小区间上反复分区、递归净效果反而不如一个简单的插入排序。public static void quickSortOptimized(int[] arr, int left, int right, int threshold) { if (right - left 1 threshold) { insertionSort(arr, left, right); return; } int pivotIndex partition(arr, left, right); quickSortOptimized(arr, left, pivotIndex - 1, threshold); quickSortOptimized(arr, pivotIndex 1, right, threshold); } private static void insertionSort(int[] arr, int left, int right) { for (int i left 1; i right; i) { int key arr[i]; int j i - 1; while (j left arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }这个优化在实际大数据量排序中能省掉大量的递归调用实测提升5%左右是常态。但注意阈值别设太大我建议16到32之间。设太大反而让算法回到了O(n²)区间。4.3 重复元素过多的CASE著名的三路快排思路如果数组里全是重复元素比如100万个2快排会退化得非常严重。为什么因为常规分区只把等于基准的元素放在了某一侧另一侧全是大于或小于基准的元素。等于基准的元素越多分区越不均匀。解决方案是三路快排把数组分成三块——小于基准、等于基准、大于基准。等于基准的那块已经排列好不需要再递归这样重复元素越多子问题越小性能越好。三路快排的实现比双路复杂不少但思路值得理解思路到位后看一眼代码基本就能写出来。我当初是在一个练习平台上连续刷了几道排序题被迫去优化重复元素场景才真正体会到三路的妙处。如果你在工作中经常处理大量重复的分类数据这个思路值得收藏。5. 常见问题与排查技巧实录从学习到实战的手记5.1 栈溢出、性能跳水、边界错误三大经典翻车现场我来整理一份我亲测遇到的问题速查表都是这些年在代码和面试里反复出现的。症状根本原因解决方案栈溢出StackOverflowError固定基准遇上近乎有序的数据递归深度接近数组长度用随机基准或三数取中或改非递归实现性能从nlogn退化到n²分区极度不均基准总是最小或最大元素随机基准、三数取中、对重复元素考虑三路快排部分数据没排序partition返回的基准位置不对或者递归区间边界写错检查i的初始值和交换时机打印每次分区结果调试死循环分区后出现0长度区间却没有正确终止或者递归边界里leftright未处理检查递归终止条件left right才return全相同元素数组排序极慢常规分区把等于基准的值全部堆在一侧用三路快排或采用双轴快排排查排序bug有一个我常用的方法写一个测试用例数组长度取8左右每个元素限定在几个固定值里然后把每次分区后的数组打印出来。肉眼看几轮交换基本就能定位问题出在分区逻辑还是递归规则上。比瞎猜快得多。5.2 一个真实bug的复盘我为什么盯了半小时没看出来有一次我写完快排拿一个基础测试用例跑数组是 [3, 7, 8, 5, 2, 1, 9, 4]排出来的结果是 [1, 2, 3, 4, 5, 7, 8, 9]看着是对的。换个测试用例 [9, 8, 7, 6, 5, 4, 3, 2, 1]结果成了 [1, 2, 3, 4, 5, 6, 7, 8, 9]也对。再换 [1, 1, 1, 1, 1, 1, 1, 1]直接陷入了一场漫长的排序——因为分区永远分不出有效的左右子区间。这个案例说明一个关键点不要只拿随机数据测试排序算法。一定要专门准备几组“刁钻”数据完全升序、完全降序、全部相同、仅有两种值交替出现、只有一个元素、空数组。这些边界才是真正检验算法实现质量的试金石。另一个容易出错的地方是递归区间边界。写完快速排序后我习惯在递归调用前打印left、right和pivotIndex三个值肉眼验证一下左边子区间是left到pivotIndex-1右边是pivotIndex1到right没有重叠也没有遗漏。这个习惯帮我避免过很多次边界混乱的问题。5.3 面试话术提升三分钟把快排讲得让人记住最后说点面试技巧。面试官让你讲快排时不要上来就念代码而是按这个节奏组织语言先一句话概括分治思想然后手绘一个示例数组手动走一遍分区过程展示基准位置被固定的那一步。接着说出时间复杂度结论并解释为什么平均是nlogn、最坏是n²然后主动提出随机基准解决退化问题。再补充说明空间复杂度是logn并解释递归深度的含义。最后如果时间充裕提一下三路快排或双轴快排说明你对工程实现有了解。这份话术下来大概不到三分钟但信息密度远高于背完代码就沉默。我作为面试官最看重的其实就是候选人能不能把“为什么这么写”讲清楚尤其是退化和优化这个闭环。能讲清楚的人写代码时的思路一定是清晰的。6. 一些想说的实践体会快速排序这个算法我写了不下二三十遍了但每写一次都还能有新的理解。早年间我背代码、跑通就算完事后来认真分析复杂度、画递归树、研究数据分布对性能的影响才真正觉得算法是个“越嚼越有味道”的东西。如果你正在学排序我建议你别只满足于AC一道leetcode题目。试着用快排去排一百万条随机数据、一百万个全部相等的字符串、一百万个几乎有序的日志记录观察不同数据分布下算法的表现差异。这种动手实验比做十道题更有收获。还有一个小建议快排的代码看起来短但每一个细节都可能成为隐藏的bug源头。建议每隔一段时间默写一遍逼自己不看任何参考直接写完整个类然后用几组刁钻数据自测。能完整写对并且解释清楚的人算法基础基本是过关的。