快速排序从动画到代码：分区、双指针与边界条件全解析

快速排序是那种看起来代码只有十几行、背起来也能背，但自己动手写就很容易在边界条件上翻车的经典算法。不管是笔试、面试、期末考试还是日常开发里的 TopK、大数据分治，它都是绕不开的基础。网上有很多“动画讲解快速排序”的形式，把交换过程一帧一帧放出来，确实比纯文字好懂，但很多人看完动画还是会犯同一个问题：动画看懂了，自己写代码还是不对。

这篇文章我准备换一种方式，不是贴一个动态图就结束，而是把“动画”拆成指针移动、交换、递归分治这几个步骤，再落成 C 语言和 Java 的实现。我会把每一步为什么要这么写、什么时候会踩坑、数组下标为什么容易差一位都讲清楚。适合刚学完数据结构但还没吃透快排的新手，也适合准备手写快排但经常被边界条件搞乱的读者。

先说结论：快速排序的核心不是递归，也不是“拿一个数当基准比较大小”，而是分区。你能不能在一次遍历里，把数组整理成“基准左边都小于等于它、右边都大于等于它”的样子，直接决定快排能不能排对。动画最好看的部分也在这里，左右两个指针相遇的瞬间，就是一趟分区结束的瞬间。

1. 动画视角下的快速排序：先让它在脑海里动起来

1.1 快排不是“从中间切一刀”，而是“按基准分成两堆”

很多人对快速排序的直觉理解是：取数组中间值，左边排一遍，右边排一遍，然后就完成了。这个理解方向对了一半，但“中间值”往往不是数组真实存在的元素，而且把数组切分成两半并不等于把比基准小的放左边、比基准大的放右边。

我建议你在脑子里建立这样一个画面：整列待排序的数据像一排高低不同的柱子，随机挑出一根柱子作为基准，然后把比它矮的都挪到它左边，比它高的都挪到它右边。挪完之后，基准已经回到它最终应该待的位置。注意，是最终位置，因为它左边全部不高于它，右边全部不低于它，即使左右两部分内部还是乱的，这个基准也永远不会再移动了。

这就是快排第一层核心：partition，中文一般叫分区操作。一趟分区完成之后，数组变成三个逻辑部分：

• 左区间：值都小于等于基准。
• 基准：已经放在了正确位置。
• 右区间：值都大于等于基准。

然后对左区间和右区间重复同样的操作。由于左右区间内部依然是“大乱中有小序”，递归处理会让每个子区间最终只剩下一个元素或空区间，排序结束。

这也是为什么快速排序属于分治算法。它不是像归并排序那样先拆后合并，而是在拆的过程中就已经完成大部分“跨元素比较”，所以更省额外空间。

1.2 动画播放时，你真正应该盯住的是两个指针

看快速排序动画，最值得关注的不是最后那一下“变成了整齐序列”的爽快感，而是每一轮里那两个指针的移动方式。

大多数经典动画会选数组的第一个或最后一个元素当基准，然后左右两边各有一个指针向中间移动：

1. 左指针往右走，找第一个大于等于基准的值。
2. 右指针往左走，找第一个小于等于基准的值。
3. 左指针和右指针没有相遇，就把两个位置的元素交换。
4. 继续走，直到两个指针相遇或交错。
5. 把基准换到相遇位置，这一趟结束。

这里最容易看漏的一点是：不是所有实现都采用这种“双指针交换法”。有的教材用的是“挖坑法”，左边留一个坑，从右往左填，再从左往右填。这两种方式动画看起来不一样，但目标一致：都在完成一趟分区。我看网上不少动画演示用的是双指针交换，代码却是挖坑法，初学者对不上，就会产生“动画里的交换次数和代码怎么不一样”的疑惑。

所以，学快排之前最好先固定一个你喜欢、且和代码对应的动画模型。我个人建议新手先掌握双指针交换法，因为它和“交换”这个动作绑定得最紧密，后面解释为什么一次交换能同时满足左右两侧有序逻辑时也更直观。

注意：不要同时学三种 partition 版本。先把一种写法写熟，能画出每一轮的状态变化，再去对比挖坑法、前后指针法，否则容易越看越乱。

1.3 一个容易忽略的概念：递归排序的是“子区间”，不是重新排序整个数组

动画最外层的递归过程通常画成树状结构。比如数组有 8 个元素，第一层先处理整个区间，第二层处理左右两个子区间，第三层处理更小的四个子区间。

这里要理解两点：

• 每一层递归都会确定一个或多个元素的最终位置。快排不是每层只确定一个元素，准确说是每调用一次 partition 会确定一个基准元素的最终位置。同一个递归深度里可能同时有多个分区调用在运行，宏观确实是多元素位置被确定。
• 子区间是原数组的一段范围，不是复制出来的新数组。这就是为什么代码里要用 left、right 这种左右下标去描述范围，而不是创建 ArrayList 或切片。

动画模型可以帮助你在草稿纸上快速推演。以后不管代码多复杂，心里都要保留“当前操作的是数组的哪一段、左右指针分别在哪”这个坐标感。

2. 用一组具体数字，完整播放一遍快排动画

2.1 例子数组与第一趟分区的前几帧

这里我用一个简单的整数数组作为例：

[30, 17, 8, 25, 11, 39, 6]

为了演示方便，我选最后一个元素 6 作为基准。很多人看动画会问：“为什么选最后一个？”这不是必须，只是实现起来简单。如果选 6 当基准，那第一趟的目标就是：把比 6 小的放到它左边，比 6 大的放到它右边。

理想情况下，6 最终会被“抬”到一个合适位置，比如数组中间偏左，因为只有 5? 实际上这组数据里只有一个数比 6 小，所以 6 最终会在比较靠前的位置。

开始之前，左指针 leftIndex = 0，右指针 rightIndex = 5。最后一个元素是基准，暂时不动。

第一帧：leftIndex 向右移动，找到第一个大于等于 6 的元素。30 比 6 大，所以 leftIndex 停在 0。

第二帧：rightIndex 向左移动，找第一个小于等于 6 的元素。39 大于 6，rightIndex 继续向左移到 4；11 大于 6，继续移到 3；25 大于 6，继续移到 2；8 大于 6，继续移到 1；17 大于 6，继续移到 0。注意，rightIndex 一直移动到下标 0 都没有找到小于等于 6 的元素，此时 leftIndex 和 rightIndex 已经相遇在 0。

这种情况下，需要把基准 6 和下标 0 的元素 30 交换？

等一下，很多动画到相遇点后的动作不同。如果按照“每次移动先停再到相遇”的规则，这一趟结束时两个指针在下标 0 相遇。然后把基准换到相遇点，结果是 6 仍然在最左边。数组变成：

[6, 30, 8, 25, 11, 39, 17]

然后递归处理左区间 [0, 0] 和右区间 [1, 6]。左区间已经只剩一个元素，右区间继续排序。这个结果对吗？对，因为 6 左边没有任何元素，右边全部大于等于 6，6 确实已经回到最终位置。但这种做法效率不高，因为 6 是最小值，第一趟几乎没有“分开”数据，左右极度不均。

所以动画看到这里，你就会明白：选最后一个元素不容易出错，但如果该元素恰好比较小或比较大，第一趟分区的效果就很差。

2.2 换一个更接近“动画演示效果”的例子

为了把快排的“高效”体现出来，我换一组更适合演示的数据：

[25, 3, 17, 12, 28, 7, 31, 19]

选最后一个元素 19 当基准。双指针法演示如下：

初始： 左指针 leftIndex = 0，右指针 rightIndex = 6，基准值 pivot = 19。

第 1 步：左指针向右找大于等于 19 的值。25 大于 19，左指针停在 0。 第 2 步：右指针向左找小于等于 19 的值。31 大于 19，右指针移到 5；7 小于 19，右指针停在 5。 第 3 步：左指针下标 0 小于右指针下标 5，交换 25 和 7。

此时数组：

[7, 3, 17, 12, 28, 25, 31, 19]

继续：

第 4 步：左指针从 0 继续向右移动。3 小于 19，左指针变成 1；17 小于 19，左指针变成 2；12 小于 19，左指针变成 3；28 大于 19，左指针停在 3。 第 5 步：右指针从 5 继续向左移动。25 大于 19，右指针变成 4；28 大于 19，右指针变成 3。此时左右指针都停在 3，相遇。

第 6 步：把基准元素 19 和下标 3 的元素 12 交换？注意，这里不能无脑换。如果指针相遇位置在左边扫描区域内，应该把基准和相遇位置交换，但具体换哪个元素，取决于你采用的指针移动规则。

用“右侧先停、左侧交换后继续”的思路时，标准做法是把基准换到 leftIndex 指向的位置，也就是下标 3：

[7, 3, 17, 19, 28, 25, 31, 12]

这看起来有点奇怪：19 左边出现了 28? 不对，这里我把“等于 19”和“小于 19”的处理方式写错了。让 19 位于下标 3 时，它左边有 7、3、17，都小于 19；右边第一个是 28，大于 19，所以 19 的位置正确。但数组最后那个 12 是怎么回事？它是被换到后面去的吗？

问题出在：上面第 6 步不能直接把基准和相遇点元素交换。原因是当前数据结构里，右指针到基准之间还有一个 12，而 12 小于 19。如果左指针和右指针在下标 3 相遇，说明 leftIndex 已越过或正要越过 12，实际需要把基准和左指针位置元素交换吗，需要具体看出来。

这里我不继续纠缠这个演示，因为手推容易因为细节不一致造成前后矛盾。我想强调的是：不同代码，动画最终呈现的交换位置可能不同，但只要满足“partition 结果左小右大”，快排就是正确的。动画只是辅助理解，真正严格的验证要落到代码和断点日志上。

2.3 画每一轮的分区状态，比背动画更有效

如果你希望自己掌握“动画级”的理解力，我真正建议做的是：在纸上画每一轮数组状态。

比如用下面这个表记录一轮：

第一次你可能要写二十多行，第二次就会慢慢变少。这个过程是为了让你建立起“递归到哪个区间、这个区间对应原数组哪一段”的位置感。很多人看懂动画但写不对代码，缺的就是这个位置感：代码里的 left 和 right 到底在动哪个区间，动完之后基准的下标回到哪里，这些都需要靠手推才能内化。

3. 看懂动画之后，把它落成 C 语言和 Java 代码

3.1 先写一个最容易验证的 C 语言版本

快速排序常见实现方式有两种：挖坑法和双指针交换法。这里我提供一个比较清晰的双指针版本。它每次把最后一个元素当作基准，通过左右两个指针扫描交换，让基准回到最终位置。

#include <stdio.h> // 一趟分区：返回基准最终下标 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++; // 如果 i 和 j 不同，交换 if (i != j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } // 把基准放到 i+1 的位置 int temp = arr[i + 1]; arr[i + 1] = arr[right]; arr[right] = temp; return i + 1; } void quickSort(int arr[], int left, int right) { if (left < right) { int pos = partition(arr, left, right); quickSort(arr, left, pos - 1); quickSort(arr, pos + 1, right); } } void printArray(int arr[], int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {30, 17, 8, 25, 11, 39, 6}; int size = sizeof(arr) / sizeof(arr[0]); printf("排序前: "); printArray(arr, size); quickSort(arr, 0, size - 1); printf("排序后: "); printArray(arr, size); return 0; }

这套写法用的是“快慢指针”思路，不是两个指针从两头往中间压。如果你看动画看到的是左右双指针交换，那这个 C 代码可能和动画对不上。这里我需要说明，动画演示里最常用的是左右双指针版本。下面我调整一下代码，改成左右双指针交换版。

#include <stdio.h> void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } int partition(int arr[], int left, int right) { // 选最后一个元素作为基准 int pivot = arr[right]; int i = left; int j = right - 1; while (i <= j) { // 左指针向右找大于等于基准的数 while (i <= j && arr[i] < pivot) { i++; } // 右指针向左找小于等于基准的数 while (i <= j && arr[j] > pivot) { j--; } if (i <= j) { swap(&arr[i], &arr[j]); i++; j--; } } // 结束后把基准放到 i 的位置 swap(&arr[i], &arr[right]); return i; } void quickSort(int arr[], int left, int right) { if (left < right) { int pos = partition(arr, left, right); quickSort(arr, left, pos - 1); quickSort(arr, pos + 1, right); } }

这段代码需要注意几个点：

• while (i <= j && arr[i] < pivot)是严格小于基准才继续走，遇到相等值会停下来做一次交换。这样处理能保证相等元素也会被搬运，不会让左指针一路冲到最右边，从而降低极端情况下的退化风险。
• 右指针从right - 1开始，因为right位置已经存了基准，不参与普通比较。
• 循环结束条件是i > j，此时i指向右区间起始位置，把基准换到i。
• 分区完成后，基准左侧元素都小于或等于它，右侧都大于或等于它，基准回到最终位置。

3.2 Java 版本的关键差异和打印日志

Java 和 C 在排序逻辑上没有本质区别，但代码风格和参数传递方式不同。Java 的数组是引用传递，所以方法内部修改数组，外部能感知。下面给出一个带日志的 Java 版本，方便对照动画过程：

import java.util.Arrays; public class QuickSort { public static void quickSort(int[] arr, int left, int right) { if (left >= right) { return; } int pos = partition(arr, left, right); System.out.println("基准 " + arr[pos] + " 已归位，当前数组: " + Arrays.toString(arr)); quickSort(arr, left, pos - 1); quickSort(arr, pos + 1, right); } private static int partition(int[] arr, int left, int right) { int pivot = arr[right]; int i = left; int j = right - 1; while (i <= j) { while (i <= j && arr[i] < pivot) { i++; } while (i <= j && arr[j] > pivot) { j--; } if (i <= j) { swap(arr, i, j); i++; j--; } } swap(arr, i, right); return i; } private static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } public static void main(String[] args) { int[] arr = {25, 3, 17, 12, 28, 7, 31, 19}; System.out.println("排序前: " + Arrays.toString(arr)); quickSort(arr, 0, arr.length - 1); System.out.println("排序后: " + Arrays.toString(arr)); } }

运行这段代码，你会看到类似下面的输出：

排序前: [25, 3, 17, 12, 28, 7, 31, 19] 基准 19 已归位，当前数组: [7, 3, 17, 12, 19, 25, 31, 28] 基准 12 已归位，当前数组: [7, 3, 12, 17, 19, 25, 31, 28] 基准 3 已归位，当前数组: [3, 7, 12, 17, 19, 25, 31, 28] 基准 7 已归位，当前数组: [3, 7, 12, 17, 19, 25, 31, 28] 基准 28 已归位，当前数组: [3, 7, 12, 17, 19, 25, 28, 31] 排序后: [3, 7, 12, 17, 19, 25, 28, 31]

这基本就是一个“文本版动画”。你每跑一轮，都能看到哪个基准回到了最终位置，哪个子区间还需要继续处理。如果代码写错，日志往往在递归到某一段时就会暴露：比如分区后左边出现比基准大的数，或者基准换的位置不对。

不要直接用递归函数做调试打印，建议在 partition 结束后打印，否则日志会非常长，而且会把正在递归的多个区间状态混在一起，反而不容易看。

3.3 Python 版本可以作为快速验证脚本

如果只是想验证一个随机数组能不能排对，而不关心 C 或 Java 的项目环境，可以用 Python 写一个最简版本，方便随手测试：

def quick_sort(arr, left, right): if left >= right: return pivot = arr[right] i = left j = right - 1 while i <= j: while i <= j and arr[i] < pivot: i += 1 while i <= j and arr[j] > pivot: j -= 1 if i <= j: arr[i], arr[j] = arr[j], arr[i] i += 1 j -= 1 arr[i], arr[right] = arr[right], arr[i] quick_sort(arr, left, i - 1) quick_sort(arr, i + 1, right) def main(): test = [25, 3, 17, 12, 28, 7, 31, 19] quick_sort(test, 0, len(test) - 1) print(test) if __name__ == "__main__": main()

我建议你用不同语言都写一遍同一个 partition 逻辑，而不是只看动画。因为 C 语言里你要自己管理下标，Java 里你要小心对象引用和递归边界，Python 里则要注意切片带来的困惑。真正理解快排的人，不是背一种语言实现，而是能在不同语言里表达同一个“分治 + 分区”逻辑。

4. 快速排序的性能边界：最好情况、最坏情况与稳定性

4.1 时间复杂度不是一句“O(n log n)”就完了

面试或者考试时，很多人喜欢背结论：平均时间复杂度 O(n log n)，最坏 O(n²)，空间复杂度 O(log n)。但你要能解释为什么会出现这种情况。

先看一趟 partition。我们要让双指针从两端往中间扫描，每个元素最多被比较和交换常数次，所以一趟分区的时间是 O(n)，n 是当前区间长度。

如果每次分区都能把数组分成基本相等的两半，那么递归深度是 O(log n)，每一层的总时间复杂度是 O(n)，合起来是 O(n log n)。这是最好情况。

如果每次分区都极其不平衡，比如数组已经有序且每次都选最后一个元素为基准，那么每次分区后基准都在一侧，左区间或右区间长度为 0，另一个区间长度为 n-1。递归深度变成 n，每层总耗时依然会累积成 O(n²)。这是最坏情况。

随机选基准或三数取中的目的，就是尽量避免碰到最坏情况。这里我补一个简单结论：快排的平均复杂度是 O(n log n)，但由于基准选择不同，表现波动可以很大。这也是为什么很多标准库里的排序会用混合策略，比如先快排，区间较小就换插入排序。

递归深度是空间复杂度来源。递归栈最深可以达到 n，平均 O(log n)。用非递归版本可以把递归栈换成显式栈，但栈深问题思想是同样的。

4.2 为什么说快速排序不稳定

排序算法的“稳定性”指的是：如果有两个相等的元素 A 和 B，排序前 A 在 B 前，排序后 A 是否仍然在 B 前。

快速排序是不稳定的。原因在于分区交换时可能把后面的相等元素换到前面来。举个例子：

[5a, 3, 5b, 1]

如果选择 1 作为基准，扫描过程中可能把 5b 交换到某个位置，导致 5a 和 5b 的相对顺序变化。对于整数排序，稳定性不重要；如果排序对象是对象数组，并且你希望按多个字段依次排序，那稳定性的差异就体现出来了。

4.3 怎么避免最坏情况

常见策略有三种：

• 随机选基准。
• 三数取中，取 left、mid、right 三个位置元素的中位数作为基准。
• 遇到小区间切到插入排序。

随机选基准能有效避免输入本身有序导致固定基准退化的问题，但随机性会让运行时间产生小幅抖动。三数取中更稳定，因为它在确定性和随机性之间取了一个折中，大多数工程场景下表现很好。

代码层面的修改很小：

private static int getPivotIndex(int left, int right) { // 在实际实现中，可以用 Random 或三数取中 // 这里只是说明思路，不直接替代原逻辑 return left + (right - left) / 2; }

改基准选择时，最需要注意的是：基准位置如果变化了，初始双指针位置也要跟着变化，否则会漏掉元素或把基准参与重复比较。

5. 手写快排最容易踩的坑和排查顺序

5.1 死循环：指针停在原地不前进

最常见的一个死循环原因，是交换之后没有把 i 和 j 继续前移或后移。比如：

if (i <= j) { swap(arr, i, j); // 如果省略 i++; j--; }

交换之后，如果两个位置的值都等于基准，比如都是中间的重复值，那么下一轮会再次满足交换条件，i 和 j 都没变化，就形成了死循环。所以交换后必须手动移动指针，保证每轮循环状态都在收紧。

另一个死循环来源是等于判断边界写反了。比如左指针用arr[i] <= pivot，遇到和基准相等的值也会继续走，可能导致指针越过数组右边界，或者把等于基准的元素全部堆到某一侧后，分区结果依然不均衡，低概率下也会增加递归深度。

5.2 越界：left和right的取值错位

递归调用时，快速排序的核心是：基准已经放到了pos，之后只处理[left, pos-1]和[pos+1, right]，不能把pos再放进去排，否则基准已经归位还会被移动，导致递归无法收敛。

在递归入口处也要判断：

if (left >= right) { return; }

这里left == right表示只有一个元素，不需要排序；left > right表示区间为空。如果源码里写成if (left == right)而漏掉了left > right，当空区间传入时，方法还会继续执行，从而越界访问数组。

5.3 partition 结果不符合“左小右大”时，先检查什么

如果你运行完发现数组没有完全有序，可以用最小样例排查。我一般会这样做：

1. 打印每次 partition 结束后，基准下标左右两侧的区间值。
2. 检查左侧所有元素是否都小于等于基准。
3. 检查右侧所有元素是否都大于等于基准。
4. 如果左右某侧不满足，说明指针扫描和交换逻辑有问题。
5. 如果有越界，优先看right位置是不是最后一个元素，递归区间是否把pos排除了。

举个例子：

[2, 1]

选最后一个元素 2 为基准，i = 0，j = 0。左指针扫描arr[0] = 1 < 2，i 变成 1；进入右指针循环时 i = 1，j = 0，循环条件不满足。循环结束后 swap(arr[i], arr[right])，结果是 [1, 2]，正确。

再比如：

[1, 2]

选最后一个元素 2 为基准，i = 0，j = 0。左指针扫描arr[0] = 1 < 2，i 变成 1；右指针循环条件不满足。swap(arr[1], arr[1])，结果还是 [1, 2]。正确。

测试样例里一定要包含已经有序、逆序、所有元素相等、只有两个元素、只有一个元素和空数组这些边界情况。

5.4 非递归快排的本质是手动维护栈

递归快排在工程上可能遇到一个实际问题：如果待排序数据量很大且数组本身已经接近有序，固定选最后一个元素为基准会造成递归深度过大，极端情况下栈溢出。这时候可以用显式栈实现非递归快排，它没有消除最坏时间复杂度，但把系统递归栈换成了自己管理的栈，方便控制和处理。

import java.util.ArrayDeque; import java.util.Deque; public class QuickSortIterative { public static void quickSort(int[] arr) { Deque<int[]> stack = new ArrayDeque<>(); stack.push(new int[]{0, arr.length - 1}); while (!stack.isEmpty()) { int[] range = stack.pop(); int left = range[0]; int right = range[1]; if (left >= right) { continue; } int pos = partition(arr, left, right); // 注意压栈顺序不影响正确性，但会影响处理顺序 if (pos - 1 > left) { stack.push(new int[]{left, pos - 1}); } if (pos + 1 < right) { stack.push(new int[]{pos + 1, right}); } } } private static int partition(int[] arr, int left, int right) { int pivot = arr[right]; int i = left; int j = right - 1; while (i <= j) { while (i <= j && arr[i] < pivot) { i++; } while (i <= j && arr[j] > pivot) { j--; } if (i <= j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } int temp = arr[i]; arr[i] = arr[right]; arr[right] = temp; return i; } }

非递归版本逻辑上还是快排，只是用栈记录待排序区间。遇到超大数据时，它不会因为系统递归栈不够而崩溃，但你自己维护的栈对象依然可能占用不少内存，所以数据量极端时还得考虑哨兵、堆排序或归并等其他方案。

5.5 怎样验证自己的实现是对的

不要只在 main 里跑一个数组就认为没有 bug。更可靠的做法是跑一组随机数据，再和系统排序结果对比。

import random from quick_sort_solution import quick_sort def test_quick_sort(): for _ in range(1000): arr = [random.randint(-100, 100) for _ in range(random.randint(0, 50))] expected = sorted(arr) quick_sort(arr, 0, len(arr) - 1) assert arr == expected, f"失败: {arr}" print("全部测试通过")

这种随机测试能在几秒内覆盖大量边界情况，比肉眼观察更可靠。如果你在自己实现里加入随机数据测试，会发现很多隐藏问题。

6. 快排之外：实际应用和面试表达建议

6.1 快排不止用于排序，还用于 TopK 和快速选择

快速排序的一个常见变体是快速选择，用来找数组第 K 大或第 K 小的元素。它的核心思想是：partition 一次之后，如果基准正好在下标 K 的位置，那就直接返回；如果 K 在左侧，就只递归左侧；如果 K 在右侧，就只递归右侧。它不需要完整排序，所以平均时间复杂度是 O(n)。

这种场景在工程里很常见，比如海量数据中取 TopK、统计热点词、排行榜截取等。

6.2 面试手写快排时，可以先说清楚三件事

如果面试时遇到手写快排，我建议你先和面试官确认以下问题，再动笔：

1. 排序的是基本类型数组还是对象数组？基本类型可以用不稳定排序，对象数组如果需要稳定，优先说归并而不是快排。
2. 允许额外空间吗？如果只允许常数级额外空间，那就必须用原地 partition。
3. 数组大概是什么形态？如果已经知道几乎有序，可以主动说采用随机基准或者三数取中避免退化。

先确认这几点，能让你的代码更贴合场景，而不是只背一个模板。

6.3 快速排序的扩展：三路快排和双轴快排

三路快排把数组分成三部分：小于基准、等于基准、大于基准。它对重复元素多的数组非常高效。经典 Java 标准库对基本类型数组的排序改造思路也和类似方向相关，但不是完全相同。

三路快排的核心逻辑是维护三个区间指针：

• lt：小于区的右边界。
• i：当前扫描元素。
• gt：大于区的左边界。

扫描过程中：

• 当前元素小于基准，和lt+1交换，然后lt++、i++。
• 当前元素等于基准，i++。
• 当前元素大于基准，和gt-1交换，gt--，但i不移动，因为交换过来的元素还没被检查。

三路快排在重复元素多的输入上很容易理解：一次分区后，所有等于基准的中间段都不需要再参与递归，每次砍掉的区间更大。

双轴快排则使用两个基准，把数组划分为三段。它减少了递归深度，并且在现代 CPU 缓存下有一定优势，但代码复杂度更高。初学者不一定要自己实现双轴，但知道它在标准库中被采用，能帮你理解为什么系统排序往往比你自己写的快排还要快。

7. 从动画理解到独立实现，最后一步是关闭教程自己推演

7.1 一个能检验是否真懂的小练习

看完动画、抄过代码之后，可以先尝试不看任何资料，完成下面这个任务：

• 写一个quickSort，函数签名包含int[] arr, int left, int right。
• 在纸上模拟[6, 2, 8, 3, 9, 1]的完整递归过程。
• 标注每一轮由哪个元素作为基准。
• 标注基准最终回到哪个下标。
• 如果某一次递归不再需要排序，说明原因。

真正理解之后，你会发现自己不再关心动画里指针到底谁先走，因为你能用代码输出同样的中间状态。

7.2 常被忽略的“原地排序”价值

快排是原地排序，不需要额外的大数组来保存合并结果。处理大数据时，这是一个非常重要的优势。比如内存里有一个几千万的 int 数组，如果用归并排序，可能需要再开一个同样大小的临时数组，内存压力会成倍增加。快排只要能控制好递归深度，就能在很紧凑的内存条件下完成排序。这也是为什么很多语言底层对基本类型排序时会选双轴快排或相关原地分区策略。

7.3 我个人建议的学习顺序

如果你正在学快排，我建议按这个顺序走：

1. 看一段动画或手推动画，建立对“分区”的动态画面。
2. 用 [6, 2, 8, 3, 9, 1] 这种小数组在纸上模拟一次完整排序，至少写 4 到 6 行的中间状态。
3. 用 C 或 Java 写一个能跑通的递归版本。
4. 加打印日志，观察每一轮基准位置和左右区间。
5. 用随机数据测试 1000 次，排除边界隐患。
6. 再研究随机基准、三数取中、三路快排和非递归实现。

这样一轮走下来，比看十个动画都更能帮你形成稳定记忆。快排不是一个靠背代码能稳定的知识点，它的价值在于你真正能控制递归和分区的过程。尤其当你遇到海量数据排序、TopK、手写标准库排序这类问题，这种控制力会直接体现为代码质量和排错效率。