快速排序深度解析：从分区思想到工程优化与踩坑实录

快速排序可能是排序算法里被讨论最多、面试中出现频率也最高的一个名字。很多人能默写出一段快速排序代码，但一旦追问“为什么这里要先移动右指针”“为什么主元选不好会退化到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)。

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 void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

这个版本最大的优势是“不容易写错”，因为循环边界很清晰。但它有两个明显的短板。

第一，它对于“等于主元的元素”处理得不好。以升序数组和降序数组为例，如果数组中大量元素等于主元，它们会被全部堆到某一边，导致分区严重失衡。第二，Lomuto分区每发现一个小于主元的元素就要交换一次，交换次数偏多，性能上没有Hoare分区好。

2.2 Hoare分区：双向扫描的效率之选

Hoare分区是快排原始论文里的方案，也是工程中更常见的版本。它的思路是：从数组两端同时向中间扫描，左指针找大于等于主元的元素，右指针找小于等于主元的元素，找到一对就交换。两个指针相遇时，分区完成。

java复制private static int partitionHoare(int[] a, int lo, int hi) {
    int pivot = a[lo + (hi - lo) / 2];
    int i = lo - 1;
    int j = hi + 1;
    while (true) {
        do {
            i++;
        } while (a[i] < pivot);
        do {
            j--;
        } while (a[j] > pivot);
        if (i >= j) {
            return j;
        }
        swap(a, i, j);
    }
}

这里需要注意，递归调用左区间要包含j：

java复制public void quickSortHoare(int[] a, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int p = partitionHoare(a, lo, hi);
    quickSortHoare(a, lo, p);
    quickSortHoare(a, p + 1, hi);
}

这个细节我踩过很大的坑。Hoare分区返回的j并不像Lomuto那样“主元的位置”，而是“小于等于主元区域的边界”，所以左区间必须从lo递归到p，右区间从p+1开始。如果像Lomuto那样写成左区间到p-1、右区间从p+1开始，因为主元可能还在左区间里没有被固定，结果就会出错。

Hoare分区的交换次数比Lomuto少，整体常数更小，实际跑起来更快。但它的指针移动条件用的是严格小于和严格大于，目的是让等于主元的元素在两边都可以存在，避免指针卡死。如果改成a[i] <= pivot，在极端情况下来回移动会导致死循环。

2.3 递归实现与退化场景

完整的快排递归实现，我一般会封装成下面这样：

java复制public class QuickSort {
    public void sort(int[] a) {
        if (a == null || a.length < 2) {
            return;
        }
        quickSort(a, 0, a.length - 1);
    }

    private void quickSort(int[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int p = partitionLomuto(a, lo, hi);
        quickSort(a, lo, p - 1);
        quickSort(a, p + 1, hi);
    }
}

退化场景不是想象出来的。我自己第一次用固定选最后一个元素的方式，对一个100万大小的升序数组做排序，结果程序直接抛了StackOverflowError。原因是每一轮分区都只消掉一个最大元素，剩下的数组继续递归，递归深度达到了100万，栈自然撑不住。

如果只是为了验证退化，可以不用实际排序，只需要在递归函数里打印一下当前子数组的长度变化，你会发现每次只减少1，这就是典型的O(n²)形态。

2.4 迭代实现与自建栈

递归不是快排的唯一写法。用显式栈模拟递归，可以把空间复杂度控制在可控范围，并且彻底规避栈溢出问题。思路很简单：先把整个数组的起止下标压栈，然后循环弹出、分区、把左右子区间压回去。

java复制public void quickSortIterative(int[] a) {
    Deque<int[]> stack = new ArrayDeque<>();
    stack.push(new int[]{0, a.length - 1});
    while (!stack.isEmpty()) {
        int[] range = stack.pop();
        int lo = range[0];
        int hi = range[1];
        if (lo >= hi) {
            continue;
        }
        int p = partitionLomuto(a, lo, hi);
        // 小的区间先处理，大的区间后处理，控制栈的大小
        if (p - lo < hi - p) {
            stack.push(new int[]{p + 1, hi});
            stack.push(new int[]{lo, p - 1});
        } else {
            stack.push(new int[]{lo, p - 1});
            stack.push(new int[]{p + 1, hi});
        }
    }
}

栈版本并不是银弹，它的优点是栈深度不会因为数据规模而无限增长，但代价是要手动维护一个栈数据结构，代码可读性下降。工程上更多是用“尾递归优化”而不是完全改迭代，这在第三部分会讲。

3. 优化策略：从工程角度审视快速排序

3.1 随机化与三数取中

解决有序数组退化的最直接办法，是让主元随机化。Java里可以这样写：

java复制private static final Random RANDOM = new Random();

private static int randomPivot(int[] a, int lo, int hi) {
    int idx = lo + RANDOM.nextInt(hi - lo + 1);
    swap(a, idx, hi);
    return partitionLomuto(a, lo, hi);
}

随机化的价值在于：对任何固定的输入序列，出现极端分区的概率都极低。专业一点说，随机化让快排的期望时间复杂度稳定在O(n log n)，不再依赖输入数据的初始顺序。

三数取中是另一个常用策略。它的思路是从子数组的头、尾、中间三个位置取出元素，选择其中位数作为主元。例如数组是[3, 1, 4]，三个位置的值分别是3、1、4，中位数是3，那就把3换到主元位置。三数取中能有效避免主元是最大值或最小值的常见情况，代价只是多几次比较。在实际工程中，三数取中通常比纯随机化更稳定，因为随机数生成本身也有开销。

3.2 小区间插入排序

快排在子数组很小的时候，递归的开销开始变得不划算。每次调用partition要维护一堆指针、做多次比较和交换，而为几个元素做这些操作完全是浪费。这时候插入排序的简单循环反而更快。

工程上常见的做法是加一个阈值，比如16：

java复制private void quickSort(int[] a, int lo, int hi) {
    if (hi - lo <= 16) {
        insertionSort(a, lo, hi);
        return;
    }
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

插入排序代码：

java复制private void insertionSort(int[] a, int lo, int hi) {
    for (int i = lo + 1; i <= hi; i++) {
        int cur = a[i];
        int j = i - 1;
        while (j >= lo && a[j] > cur) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = cur;
    }
}

为什么阈值不要太大？因为插入排序是O(n²)复杂度，如果小区间很大，比如1000个元素，虽然常数很小，但平方复杂度依然不划算。经验上16到32之间是常见选择，我在自己的测试里用16和24差别不大。

3.3 三路快排解决大量重复元素

普通快排在处理大量重复元素时有一个隐蔽的坑。以Lomuto分区为例，条件判断是a[j] < pivot，等于主元的元素不会被交换到左边去，它们会一直留在右边，最终导致右区间特别大。最极端的情况是数组里所有元素都相等，每一轮分区后一边是0，一边是n-1，快排直接退化成O(n²)。

三路快排专门解决这个问题。它把整个数组分成三块：小于主元、等于主元、大于主元。等于主元的部分原地不动，下一次递归只需要处理左边小于区和右边大于区。

java复制private void quickSort3Way(int[] a, int lo, int hi) {
    if (hi <= lo) {
        return;
    }
    int lt = lo;
    int gt = hi;
    int pivot = a[lo];
    int i = lo + 1;
    while (i <= gt) {
        if (a[i] < pivot) {
            swap(a, lt, i);
            lt++;
            i++;
        } else if (a[i] > pivot) {
            swap(a, i, gt);
            gt--;
        } else {
            i++;
        }
    }
    quickSort3Way(a, lo, lt - 1);
    quickSort3Way(a, gt + 1, hi);
}

这个算法的边界条件需要特别小心。当a[i] > pivot时，把当前元素和a[gt]交换后，gt--，但是i不能增加，因为换过来的新元素还没有被比较过。当a[i] < pivot时，交换后lt++和i++可以同步推进。如果漏掉这个细节，会出现排序结果错误甚至死循环。

三路快排面对全部相等的数据时表现非常好，一次分区后lt和gt直接就夹住了整个数组，递归立刻结束，复杂度退化到O(n)。

3.4 内省排序与工程实现参考

实际工程中几乎不会用裸快排。C++标准库的std::sort用的是内省排序，它会记录递归深度，一旦超过2 log n就切换到堆排序，防止快排退化。同时，在排序过程中一旦子数组规模小于16，就直接改用插入排序。

Java的Arrays.sort对基本类型数组用的是双枢轴快速排序，对对象数组用的是TimSort。双枢轴快排一次选两个主元，把数组分成三块，虽然常数复杂度更复杂，但实际性能比单枢轴快排快不少。从这些工业级实现你可以看到，快排不是孤立算法，而是一个可以不断叠加优化策略的框架。

4. 复杂度分析：最好、最坏与平均的真相

4.1 递归树与每层工作量

要理解快排为什么通常是O(n log n)，画递归树最直观。假设每次分区都接近对半，第一层需要处理n个元素，第二层有两个子数组，加起来还是n个，第三层四个子数组，加起来还是n个。每一层的总工作量大约是n，一共有log n层，所以总复杂度是n乘以log n。

这个过程可以类比成公司开会：每次会议都把人员分成两组，每层所有人都会被安排到一次会议中，层数取决于分组的均衡程度。分组越均衡，层数越少；分组越失衡，层数越多，甚至变成n层。

4.2 平均复杂度为什么是O(n log n)

有人会问：如果每次分区不是精确对半，而是1比9的比例，复杂度还是O(n log n)吗？答案是肯定的。因为1比9的分区，最长的递归路径长度是log_{10/9} n，虽然比log2 n大一些，但依然是log n量级。每层总工作量依然是n，所以总复杂度仍然是O(n log n)。

只有像1比n-1这样的极端分区，递归路径长度才会接近n，导致总复杂度变成n²。换句话说，只要分区比例是一个常数比例，快排的复杂度就是O(n log n)；只有当每轮分区都严重失衡，才会退化成O(n²)。

随机主元的作用，就是把出现这种严重失衡的概率压到极低。哪怕恶意构造输入数据，只要主元是随机选的，对方也没法准确预测每一次分区结果。

4.3 空间复杂度与递归栈

快排的额外空间主要消耗在递归栈上，不是临时数组。最好情况下递归深度是log n，所以空间复杂度是O(log n)。最坏情况下递归深度是n，空间复杂度就变成O(n)。

这个点经常被误记为O(1)。我见过不少帖子说快排是原地排序所以空间复杂度O(1)，这是不对的。尽管它不需要额外数组来合并，但递归本身就要占用调用栈空间。如果你想严格做到O(1)辅助空间，必须写成完全迭代的版本，但那样代码复杂度会明显上升。

4.4 稳定性与比较次数

快排是不稳定的。比如数组里有三个元素值都是5，但是初始顺序是a1、a2、a3，分区过程中的交换可能让它们相对顺序改变。如果你的业务要求相同值的元素保持原有顺序，快排不是合适选择，归并排序才是。

快排的平均比较次数约为1.39n log n，这个常数主要是由“分区时元素和主元逐一比较”带来的。它比堆排序的比较次数少，同时又能很好地利用CPU缓存，因为快排的访问是线性的，不像堆排序那样频繁跳跃访问。这也是为什么多数语言内置排序会选择快排或快排变体，而不是堆排序。

5. 常见问题排查与实测经验

5.1 大数组栈溢出

我在前面提到过，用固定主元对100万升序数组排序时直接StackOverflowError。排查方法很简单：在递归入口打印当前深度和数组范围，你会看到深度持续攀升到接近数组长度。

解决办法有三个层次。第一，随机化或三数取中，避免最坏情况发生。第二，小区间用插入排序，减少递归深度。第三，做“尾递归优化”，只递归小的子区间，大的子区间用循环继续处理：

java复制private void quickSortTail(int[] a, int lo, int hi) {
    while (lo < hi) {
        int p = partitionLomuto(a, lo, hi);
        if (p - lo < hi - p) {
            quickSortTail(a, lo, p - 1);
            lo = p + 1;
        } else {
            quickSortTail(a, p + 1, hi);
            hi = p - 1;
        }
    }
}

这样做的原理是：递归深度只取决于较小的一侧，较大的一侧留在循环里继续分区，栈深度最多log n。

5.2 重复元素导致死循环

Hoare分区里最常见的死循环原因，是主元和数组元素相等时指针停不下来。如果left指针用while (a[i] <= pivot)，right指针用while (a[j] >= pivot)，当左右指针都落到一个等于主元的元素上时，交换后它们会继续卡在原地，永远无法相遇，最终死循环。

正确写法是用严格小于和严格大于。遇到等于主元的元素，指针可以跨过去，或者交换后自然错开。我建议刚接触Hoare分区时，先用几个极端数据测试：全部相等、升序、降序、只有两种值的数组。这些用例能很快暴露边界问题。

5.3 快排与归并、堆排序的选择

实际选型时，我习惯用下面这张表做参照。

这张表不是万能的。如果你的数据几乎有序，插入排序可能比快排更快。如果需要稳定性，只能上归并。如果内存极其有限，堆排序的空间优势就很关键。快排并不是所有场景的万能解，但它是综合性价比最高的通用排序。

5.4 实测数据与参数选择参考

我在本地用10万元素做过几组粗略测试，结果仅供参考，具体数据会因机器和JVM状态波动。

注意固定末位主元在全部相等数组上会退化成类似O(n²)的表现，因为Lomuto分区会把相等元素全部堆到一侧。随机主元虽然不会稳定选到极值，但当所有元素相等时，随机选到的主元依然全都是同一个值，照样会失衡。三路快排对这个场景有天然优势。

我自己这些年写排序代码最大的体会是，快排不是背出来的，是调出来的。第一次用Hoare分区写死循环，第一次用固定主元排有序数组直接栈溢出，这些坑踩一遍比读十遍理论管用。如果你正在准备面试，建议把Lomuto、Hoare、三路快排都自己动手实现一遍，然后用重复元素、升序、逆序这几组数据砸上去，看哪个版本会崩、哪里崩、为什么崩。把这个过程走完，才算真正“深究”过快速排序。