番言快速排序可能是排序算法里被讨论最多、面试中出现频率也最高的一个名字。很多人能默写出一段快速排序代码，但一旦追问“为什么这里要先移动右指针”“为什么主元选不好会退化到O(n²)”“大量重复元素时快排为什么慢”，就说不清楚了。这篇博文想把我自己深挖快速排序的完整过程梳理一遍：从分区思想到Java实现，从三路快排到工程中的混合策略，再到实测中遇到的栈溢出和死循环问题。适合正在准备算法面试、想搞清楚排序底层逻辑、或者写业务代码时想正确使用排序API的朋友。
1. 快速排序的核心思路：分治到底在分什么
1.1 分区操作才是快排的真正灵魂
快速排序的核心不是递归，而是“分区”。递归只是把分区的结果继续处理下去。我第一次学快排时，以为只要写出递归框架就算懂了，后来才发现，真正决定性能、稳定性、甚至会不会死循环的，全是分区函数里的细节。
分区做的事情可以这样理解：从数组里随便挑一个元素当“主元”（pivot），然后扫描整个数组，把所有比主元小的元素放到左边，所有比主元大的元素放到右边。经过这一步，主元本身已经站在了它最终该站的位置上。接下来只要递归处理左边和右边的子数组，整个数组就自然有序了。
这个模型很像整理书架：你随便抽出一本书，以它的厚度为基准，把更薄的书放左边，更厚的放右边。这本书放好后就不需要再动了，然后对左边那堆、右边那堆分别重复同样的事。慢慢整理到最后，每本书都在自己的位置。
快排和归并排序最本质的区别就在这里：归并排序是先拆到底，再一层层合并，合并过程需要额外数组；快速排序是边拆边把元素放到最终位置，拆分完成后不需要任何合并操作。这个“不需要合并”的特性，让快排可以不借助额外的大块内存，直接在原数组上完成排序，这也是它在工程上备受青睐的原因之一。
1.2 主元选择的蝴蝶效应
分区算法给定后，主元选谁就成了整个快排最大的变量。教科书上为了讲解方便，通常选第一个元素或者最后一个元素当主元。这个选择在绝大多数情况下没问题，但一旦碰上已经排好序的数组，问题就来了。
假设数组是升序的，你每次固定选最后一个元素当主元。第一轮分区后，主元是最大值，它右边没有任何元素，左边是剩下的n-1个元素。第二轮又选最大值，又拆出一个0和n-2的划分。整个过程就像一条链表，每层只排除一个元素，递归深度直接变成n。此时的时间复杂度不再是O(n log n)，而是O(n²)，递归深度也会让栈溢出风险暴增。
随机化、三数取中、甚至更复杂的取样策略，本质上都是在降低“每次选到极端值”的概率。这个概率问题不是理论上的杞人忧天，我在第五部分会放一组自己实测的数据，固定主元和随机主元在处理有序大数组时的表现差距极其夸张。
1.3 递归边界与“不用做合并”的妙处
快排的递归边界很朴素：当子数组只剩下一个元素或者为空的时候，就不需要再分了。
java复制public void quickSort(int[] a, int lo, int hi) {
if (lo >= hi) {
return;
}
int p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
}
这段代码的框架非常简单，但它背后有两个容易被忽略的点。第一，分区完成的那一刻，主元的位置就已经固定了，在后续所有递归中它都不会再参与移动，所以不需要向归并排序那样有一个合并步骤。第二，递归深度不是固定的，它取决于分区是否均衡。均衡时树高度是log n，不均衡时是n，这就是为什么快排的理论空间复杂度是O(log n)，但最坏情况下会退化到O(n)。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 快速排序的实现与细节：从伪代码到Java代码
2.1 Lomuto分区：教科书里最常见的实现
Lomuto分区是教学中最常见的版本，它的代码非常好懂。它选最后一个元素作为主元，然后用一个索引i维护“小于主元区域的右边界”，用另一个索引j遍历数组。只要发现比主元小的元素，就把i后移一位并交换。最终把主元和i+1位置的元素交换，主元就回到了正确位置。
java复制private static int partitionLomuto(int[] a, int lo, int hi) {
int pivot = a[hi];
int i = lo - 1;
for (int j = lo; j < hi; j++) {
if (a[j] < pivot) {
i++;
swap(a, i, j);
}
}
swap(a, i + 1, hi);
return i + 1;
}
private static vo