企业官网建设流程全解析

关于排序这件事，很多开发者工作几年后可能已经不怎么手写排序算法了，但面试时“请手写一个快速排序”依旧是高频题。快速排序作为经典的分治排序算法，除了应付面试，在实际工程里也是很多排序库的底牌，比如 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 核心流程与分区操作

快速排序主流程可以用四步概括：

1. 选取基准 pivot。
2. 分区（partition）：一次扫描后，把数组调整成“左边都小于等于 pivot，右边都大于等于 pivot”的状态。
3. 对左右两部分递归执行同样的操作。
4. 子数组长度小于等于 1 时递归终止，此时数组已经全部有序。

分区是快排的核心操作，实现方式主要有两种：Lomuto 分区和 Hoare 分区。

Lomuto 分区一般选最后一个元素当 pivot，用一个索引 i 标记“小于等于 pivot 区域的尾部”。扫描过程中，一旦发现当前元素小于等于 pivot，就把这个元素交换到 i 的位置，i 再前移一位。循环结束后，把 pivot 从数组末尾交换到 i+1 的位置，分区就完成了。它的优点是代码清晰、不容易出错，缺点是在某些情况下交换次数偏多。

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 位置的元素换到 i+1 位置，左侧区域扩大一位。扫描完成后，arr[low..i] 全部小于等于 pivot，arr[i+1..high-1] 全部大于 pivot，最后把 pivot 从 high 位置换到 i+1，数组就变成了“左小右大”的形态，同时返回 pivot 的最终下标。

建议你拿一组小数据在纸上走一遍，比如 [4, 10, 3, 5, 1]，把每次交换后的数组状态写出来。这样的手动模拟比看十遍代码都有效，能彻底解决“为什么返回 i+1”的疑惑。初学阶段不要跳过这一步，我在带新人时发现，凡是动手模拟过一遍的人，后面写快排基本都不再犯边界错误。

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 这三个字，就是我掌握整个快排体系的关键。

最后再分享一个小习惯：每当我写完一个排序算法，不会只看它能跑通，而是会故意丢给它一些“刁钻”输入，比如空数组、单元素、全相同元素、逆序数组、超大数组。这些边界测试会逼着你把边界条件和退化问题处理到位。如果你也能养成这样的习惯，快排对你来说就不再是背代码，而是真正长在手上的技能。