快速排序是那种“看起来只有十几行代码，但真让你手写，很容易翻车”的经典算法。我在某公司带新人做代码评审时，十次有八次会遇到 Quick Sort 相关的问题：要么边界条件写错，要么分区后递归范围没对，要么面对大量重复元素时性能崩掉。这篇就围绕 Quick Sort 的 Java 实现，把分治思路、三种主流写法、复杂度来源、工程优化和面试连环追问一次性讲透，让你不仅背得出代码，还能讲清楚每一步为什么这么写。

1. 快速排序到底在“快”在哪里

很多人学排序时都是先接触冒泡、选择这类简单排序，再到快速排序时，会觉得“分左右两边递归”这个动作有点抽象。其实快排的核心就是两个动作：选一个基准、把数组分成两拨。所有元素跟基准比较，小的放左边，大的放右边，然后左右两边各自重复这个过程。用一句话概括：每轮分区都会让基准元素落到它最终该待的位置上。

1.1 基准元素与分区操作是怎么一回事

假设你手里有一个无序数组[3, 7, 8, 5, 2, 1, 9, 4]。快排的第一步是挑一个基准，比如固定选最左边的 3。然后通过一趟扫描，把比 3 小的元素挪到左边，比 3 大的元素挪到右边。分区结束后，3 会出现在索引 2 的位置，数组变成类似[1, 2, 3, 5, 8, 7, 9, 4]。这时关键点来了：3 的左边都是小于它的，右边都是大于它的，但左右两侧内部仍然是无序的，这就交给递归去处理。每次递归都让至少一个元素归位，所以递归深度最多是元素个数级别，配合上分区的“减半”特性，平均效率就在 O(n log n)。

这个过程可用生活类比来理解：想象你在整理一摞试卷，随手抽一张当作“标准线”，低于标准分的丢左边抽屉，高于或等于的放右边抽屉。放完之后，这张标准试卷就已经放在了整摞试卷最终该在的位置，剩下只需要分别整理左右两个抽屉里的试卷即可。

1.2 为什么选左端基准时性能会退化

固定选左端或右端基准，在工程上是最容易实现的，但也是最容易出现最坏情况的写法。比如数组已经有序[1, 2, 3, 4, 5, 6]，每次选最左边的 1 作为基准，分区后发现左边没有元素，右边是[2, 3, 4, 5, 6]，下一轮又选 2 做基准，又只分成右边一堆。这样每一轮只排好一个元素，递归深度变成 n，时间复杂度直接掉到 O(n²)。这种情况下快排比冒泡好不到哪去。

所以工程上不会老老实实固定选左端或右端，而是引入随机化基准，或者用“三数取中”法。随机化基准的思路很好理解：既然最坏情况是输入有序且基准固定，那我每次从区间里随机挑一个下标，就能让“每次选到极端值”的概率变得极低。对绝大多数输入，随机化后算法退化到 O(n²) 的概率几乎可以忽略，这也是教科书里常说的“随机化快排能避免最坏情况”的真正含义。

2. Java 实现快速排序的三种写法

很多初学者最大的困惑不是原理，而是“分区函数到底怎么写”。不同写法在处理边界条件和交换逻辑上差异很大。我个人建议先掌握最经典的 Lomuto 分区，虽然它在重复元素多的场景下表现一般，但代码最直观，适合用来理解算法；之后再过渡到 Hoare 分区，最后再看三路切分。

2.1 最经典的 Lomuto 分区实现

Lomuto 分区的特点是：选最右边的元素作为基准，用一个慢指针 i 表示“小于基准区间的末尾”，快指针 j 从左往右扫描。遇到比基准小的元素，就把 i 后移一位并交换array[i]和array[j]。扫描结束后，把基准放到 i+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 - 1; for (int j = left; j < right; j++) { if (arr[j] < pivot) { i++; swap(arr, i, j); } } swap(arr, i + 1, right); return i + 1; } private static void swap(int[] arr, int a, int b) { int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } }

注意几个关键点。递归退出条件必须是left >= right，因为当分区函数返回的基准位置可能在区间端点时，下一轮递归会出现left > right的情况。分区里用的是< pivot，不是<= pivot，这样能保证与基准相等的元素不会频繁跨越两侧，减少交换次数。如果你把<改成<=，对于全是相同元素的数组，分区后基准右边全是相等的元素，递归效率会明显变差。

2.2 Hoare 分区为什么更快

Hoare 分区是另一种经典写法，它选中间位置的元素作为基准，然后用两个指针分别从左右两端向中间移动。左指针找大于基准的元素，右指针找小于基准的元素，找到后交换。两个指针相遇时，分区结束。实现如下：

private static int hoarePartition(int[] arr, int left, int right) { int pivot = arr[left + (right - left) / 2]; int i = left - 1; int j = right + 1; while (true) { do { i++; } while (arr[i] < pivot); do { j--; } while (arr[j] > pivot); if (i >= j) { return j; } swap(arr, i, j); } }

Hoare 分区相比 Lomuto 有两大优势。第一，它每次交换会把大于基准和小于基准的元素一次性放到正确一侧，交换次数更少，对随机数据的常数系数更低。第二，它返回的索引不一定是基准元素的最终位置，而是“左半区间与右半区间的分界”，所以递归时要注意：一边是[left, j]，另一边是[j + 1, right]，不能照搬 Lomuto 的pivotIndex - 1和pivotIndex + 1。这块是手写时最容易犯错的地方。

我自己在项目里封装排序工具时，默认不会用 Lomuto，而是用 Hoare。原因很简单：在数据量达到百万级时，两种分区方式在时间上的差异可以从几十毫秒拉开到一两百毫秒。虽然绝对时间都不长，但排序往往只是整个处理链路的一环，能省一点是一点。

2.3 三路切分处理重复元素

实际业务数据里“大量重复元素”是非常常见的，比如按订单状态排序、按用户等级排序，字段本身取值范围很小。这种情况下，前面两种二路分区都会出现问题：Lomuto 会把相等元素全堆到某一侧，Hoare 虽然稍好，但也没法把相等的元素集中管理。这时就该用三路切分。

三路切分的思路是维护三个区间：小于基准、等于基准、大于基准。一趟扫描后，小于基准的放左边，等于基准的放中间，大于基准的放右边。下一轮递归只需要处理左边和右边，中间这一整块相等的元素直接跳过。代码可以这样写：

public static void quickSort3Way(int[] arr, int left, int right) { if (left >= right) { return; } int pivot = arr[left]; int lt = left; int gt = right; int i = left + 1; while (i <= gt) { if (arr[i] < pivot) { swap(arr, lt, i); lt++; i++; } else if (arr[i] > pivot) { swap(arr, i, gt); gt--; } else { i++; } } quickSort3Way(arr, left, lt - 1); quickSort3Way(arr, gt + 1, right); }

这段代码里的变量含义要反复确认：lt指向等于基准区间的第一个位置，gt指向等于基准区间的最后一个位置，i是当前待扫描元素。当arr[i] > pivot时，把当前元素和gt位置的元素交换，但交换过来的新元素还没被扫描过，所以 i 不能自增，要留在原地继续比较；只有当arr[i] < pivot或arr[i] == pivot时，i 才前进。这是三路切分最容易被写错的细节。

如果面试时被问到“快排在大量重复元素下性能怎么样”，三路切分就是标准答案。Java 自带的Arrays.sort在对基本类型排序时，底层也用了类似的双轴快排思想来处理重复元素的场景。

3. 复杂度分析不能只背结论

快排的时间复杂度分析比冒泡、归并都要微妙，因为它依赖分区是否均衡。很多候选人能说出“平均 O(n log n)、最坏 O(n²)”，但被追问“为什么平均是 O(n log n)”时就卡住了。

3.1 平均、最好、最坏复杂度从哪来

最好情况是每次分区都把数组分成完全相等的两半，这种场景下递归深度是 log n，每一层总共要处理 n 个元素，所以总时间是 O(n log n)。最坏情况是每次分区都极度不平衡，比如固定选最小元素做基准，每轮只排好一个元素，递归深度变成 n，总时间变成 O(1 + 2 + ... + n)，即 O(n²)。

平均情况稍微复杂一点。我们可以用数学期望的角度理解：对随机排列的数据，每个元素作为基准被选中的概率相等，分区的“分裂比例”虽然每次不完全一样，但在期望意义上，每次分区后两个子问题的规模大约各占一半。于是递推式可以写成 T(n) = T(k) + T(n-1-k) + O(n)，通过对 k 取期望可以解出 T(n) = O(n log n)。面试时不需要推导太细，但至少要把“递归树深度为 log n”和“每层总扫描量为 n”两个要点讲清楚。

空间复杂度也要注意。快排是原地排序，不需要额外的大数组，但递归调用会占据调用栈空间。最好情况下的递归深度是 log n，所以额外空间是 O(log n)；最坏情况下递归深度是 n，额外空间是 O(n)。这也是为什么工程实现里要刻意做优化，避免递归层数过深导致栈溢出。

3.2 工程优化：随机基准、插入排序截止、尾递归

实际封装排序组件时，不可能裸写一个基础快排就上生产。有几个优化手段是必须考虑的：

• 随机基准：在前面说了，能让最坏情况出现的概率趋近于零。实现时可以用Random或ThreadLocalRandom生成区间内的随机下标，然后和区间端点交换。
• 插入排序截止：当待排序区间长度小于某个阈值（常见值是 10 到 20）时，不再递归调用快排，改用插入排序。因为小规模数据下递归调用的函数开销反而比直接插入排序更大。插入排序在小规模数据上常数极小，实测效果明显。
• 尾递归优化：递归快排时只对较短的子区间继续递归，较长的子区间用循环处理。这样可以有效控制递归深度不超过 O(log n)。

这里给一个融合了随机基准和插入排序截止的工程化实现示例：

import java.util.concurrent.ThreadLocalRandom; public class OptimizedQuickSort { private static final int INSERTION_SORT_THRESHOLD = 12; public static void sort(int[] arr, int left, int right) { while (left < right) { if (right - left + 1 <= INSERTION_SORT_THRESHOLD) { insertSort(arr, left, right); return; } int pivotIndex = partition(arr, left, right); if (pivotIndex - left < right - pivotIndex) { sort(arr, left, pivotIndex - 1); left = pivotIndex + 1; } else { sort(arr, pivotIndex + 1, right); right = pivotIndex - 1; } } } private static int partition(int[] arr, int left, int right) { int randomIndex = ThreadLocalRandom.current().nextInt(left, right + 1); swap(arr, left, randomIndex); int pivot = arr[left]; int i = left; int j = right + 1; while (true) { do { i++; } while (i <= right && arr[i] < pivot); do { j--; } while (arr[j] > pivot); if (i >= j) { break; } swap(arr, i, j); } swap(arr, left, j); return j; } private static void insertSort(int[] arr, int left, int right) { for (int i = left + 1; i <= right; i++) { int cur = arr[i]; int j = i - 1; while (j >= left && arr[j] > cur) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = cur; } } private static void swap(int[] arr, int a, int b) { int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } }

这里的while (left < right)配合递归短区间，其实是把“尾递归优化”用循环模拟了出来。每次只递归较短的一侧，较长的一侧留在循环里继续分区，这样递归深度被压缩到 log n 级别。

4. 手写快排时最常踩的五个坑

我做过很多次模拟项目评审，也帮不少同事排查过线上排序相关的 bug。下面这些问题出现的频率最高，每一个都值得记下来。

4.1 递归边界写错导致栈溢出

最常见的问题是：分区函数返回的基准位置如果正好在区间左端点，那么quickSort(arr, left, pivotIndex - 1)就会变成quickSort(arr, left, left - 1)。如果递归退出条件只写了left == right，这个边界就会漏掉，导致无限递归，最终 StackOverflowError。

正确写法是if (left >= right) return;。类似的，Hoare 分区返回的索引 j 之后，递归范围应该是[left, j]和[j + 1, right]，因为返回的 j 并不像 Lomuto 那样明确指向基准元素。用错递归范围会直接导致死循环或漏排序。

4.2 基准元素交换位置后指针移动错误

三路切分里最常见的错误是：当arr[i] > pivot，与arr[gt]交换后，gt--了，但i没有保持原地。这会导致交换到当前位置的新元素没有被比较就直接跳过。排查这类问题最好的办法就是拿一个长度为 5 的小数组，在纸上逐步演算交换过程。

// 错误示范：交换后 i 直接自增 if (arr[i] > pivot) { swap(arr, i, gt); gt--; i++; // 错误，交换过来的元素没被检查 }

4.3 忽略小数组性能

快排在数组长度小于 10 左右时，递归调用产生的函数栈帧开销和基准交换逻辑反而会让排序变慢。我有一次在性能测试里对 100 万长度的数组排序，基础快排耗时约 80 毫秒，加上插入排序截止之后降到 50 毫秒左右。这是因为大量尾部小数组都改走了插入排序，省掉了大量无谓的递归调用。

4.4 对基本类型使用不合适的比较方式

Java 的Arrays.sort对基本类型数组使用双轴快排，对对象数组使用归并排序或 TimSort。这是因为对象排序通常要求稳定，而基本类型不需要稳定。如果你自己写工具类，排序对象时要特别注意稳定性需求，不要随手拿快排去排对象数组，否则相同键值的对象顺序会被打乱。

4.5 用递归实现时没考虑大数组的栈深度

我在某项目里对一个含有千万级元素的 int 数组排序，直接递归深了之后出现了 StackOverflowError。后来改成“递归较短区间 + 循环处理较长区间”的写法，问题立刻解决。如果不想改循环，也可以显式扩大线程栈大小，但工程上更推荐从算法层面控制递归深度。

5. 与 Java 标准库排序的对比

很多时候我们根本不需要自己写排序，直接调用Arrays.sort就行。但理解标准库为什么要“绕来绕去”，对深入理解快排非常有帮助。

5.1 Arrays.sort 底层做了什么

Arrays.sort(int[])在 JDK 8 之后的实现里采用了双轴快排的思路。所谓双轴，就是每次分区不止选一个基准，而是选两个基准，把元素分成三段区间：小于 pivot1、介于 pivot1 和 pivot2 之间、大于 pivot2。因为一次分区能处理更多元素，而且对重复元素和部分有序数据做了特殊优化，实际性能比单轴快排更好。但双轴快排的实现细节非常繁琐，正常工程代码没必要自己造轮子。

还需要注意，Arrays.sort(int[])对长度小于 47 的数组会直接走插入排序；对于接近有序的数组还会用更激进的优化方式。这些阈值都是经过大量基准测试调出来的，不是随便拍脑袋定的。

5.2 什么时候值得自己实现快排

如果只是业务代码里偶尔排序，直接调用标准库就够了。自己写快排的场景通常有几种：面试现场手撕算法、算法竞赛或刷题时需要控制常数、嵌入式或特殊环境中不能依赖标准库、需要对排序行为做个性化定制（例如按业务权重排序加截断）。我在做一个模拟数据生成项目时，就自己封装了一个三路切分快排，因为需要对千万级模拟记录按多个字段做分层排序，标准库的通用排序无法直接满足我的中间截断需求。

5.3 稳定性问题怎么跟面试官解释

快排不是稳定排序，因为交换过程可能把相同键值的元素原始相对顺序打乱。比如一个对象数组里有两条记录都等于“等级 A”，分区交换后，这两条记录的先后顺序可能颠倒。如果业务要求稳定排序，优先用归并排序或 Java 对象排序的 TimSort。面试时这个点几乎必问，最好能主动补一句：“正因如此，JDK 对对象数组排序用归并而不用快排。”

6. 快排的常见扩展题型

面试官出题不会只让你干写排序。他们更关心你能不能把快排思想迁移到别的算法问题上。这里挑两个最高频的扩展题聊一聊。

6.1 用快排思想解决 Top K 问题

求一个无序数组中第 K 大的元素，经典的快速选择算法就是快排的变体。思路是：执行分区之后，基准元素落在某个位置，如果这个位置正好是目标位置，直接返回；如果目标位置在左侧，就只在左侧递归；否则只在右侧递归。平均时间复杂度是 O(n)，比排序后取值要快不少。结合前面的 Hoare 分区写出来这样：

public static int quickSelect(int[] arr, int left, int right, int targetIndex) { if (left == right) { return arr[left]; } int pivotIndex = hoarePartition(arr, left, right); if (targetIndex <= pivotIndex) { return quickSelect(arr, left, pivotIndex, targetIndex); } else { return quickSelect(arr, pivotIndex + 1, right, targetIndex); } }

注意这里因为 Hoare 分区返回的索引语义是“左分区末尾”，所以判等逻辑和 Lomuto 版不同。求第 K 大时，需要把目标下标换算成从 0 开始的索引，这块换算错误也很常见。

6.2 为什么快排实际比归并快

面试官常拿快排和归并对比。归并排序的时间复杂度稳定在 O(n log n)，而且稳定，但实际工程中大量排序场景却用快排，原因在于：快排是原地排序，不需要像归并那样开辟额外 O(n) 的临时数组来合并；快排对缓存的局部性也更好，扫描和交换都集中在连续内存区域。在数据量不大且内存敏感的场合，快排的常数优势很明显。但反过来，如果数据量极大、外部排序场景多，归并的稳定性和可预测性又更有利。

6.3 如何证明快排的平均时间复杂度

如果面试官要求简要证明，可以这样说：快排的递归式是 T(n) = T(分区左侧规模) + T(分区右侧规模) + cn。最理想是两侧各 n/2，得到 T(n) = 2T(n/2) + cn，展开后是 O(n log n)。最坏情况下递归式退化成 T(n) = T(n-1) + cn，展开后是等差数列求和，O(n²)。平均情况下，分区位置均匀分布在 0 到 n-1 上，对概率加权后可以用积分或递归展开得到 T(n) ≈ 2n ln n，同样属于 O(n log n)。表达时重点说清楚“分区规模随递归逐渐减半”这个直观逻辑，比死背公式更容易让面试官认可。

7. 动手实验：一个 Java 快速排序对比测试

理论知识聊再多，不如亲手跑一遍。我建议你在本地做个简单实验：生成三种测试数据——随机数组、有序数组、大量重复元素数组，分别用基础 Lomuto 快排、随机化 Hoare 快排、三路切分快排跑一遍，记录耗时。实验框架可以很简陋，核心代码如下：

public static void main(String[] args) { int size = 500_000; int[] random = generateRandomArray(size); int[] sorted = generateSortedArray(size); int[] duplicate = generateDuplicateArray(size); long timeLomuto = benchmark(random.clone()); long timeHoare = benchmarkHoare(sorted.clone()); long time3Way = benchmark3Way(duplicate.clone()); System.out.println("Lomuto on random: " + timeLomuto + " ms"); System.out.println("Hoare on sorted: " + timeHoare + " ms"); System.out.println("3Way on duplicate: " + time3Way + " ms"); }

比较有意思的结果是：基础 Lomuto 在“有序数组”上会跑到几秒甚至超时，因为固定选右端基准导致退化；而随机化 Hoare 在同样数据上几十毫秒就能跑完。大量重复元素场景下，三路切分明显胜出。我自己第一次跑这个实验时，看到 Lomuto 在有序数组上的耗时比随机数组多了两个数量级，才真正理解“输入决定快排生死”这句话。也推荐你把INSERTION_SORT_THRESHOLD调成 1、5、15、30 各跑一遍，能直观看出小数组阈值对整体性能的影响。

最后再分享一个小技巧：如果你要在自己的工具类里写快排，尽量把分区函数做成 private 方法，并在注释里写清楚“返回索引的语义”。因为这个索引，Lomuto 版本和 Hoare 版本的用法完全不同，半年后你自己回来看代码，大概率也会记混。我就是因为在某次重构里混淆了这两种分区的返回值，导致线上一个统计任务排序结果错乱。那次之后，我再封装算法工具类时，都会在方法命名和注释里把版本类型写写清楚，这比临时看实现逻辑高效多了。