尧图网页设计 
快速排序是那种看起来代码只有十几行、背起来也能背但自己动手写就很容易在边界条件上翻车的经典算法。不管是笔试、面试、期末考试还是日常开发里的 TopK、大数据分治它都是绕不开的基础。网上有很多“动画讲解快速排序”的形式把交换过程一帧一帧放出来确实比纯文字好懂但很多人看完动画还是会犯同一个问题动画看懂了自己写代码还是不对。这篇文章我准备换一种方式不是贴一个动态图就结束而是把“动画”拆成指针移动、交换、递归分治这几个步骤再落成 C 语言和 Java 的实现。我会把每一步为什么要这么写、什么时候会踩坑、数组下标为什么容易差一位都讲清楚。适合刚学完数据结构但还没吃透快排的新手也适合准备手写快排但经常被边界条件搞乱的读者。先说结论快速排序的核心不是递归也不是“拿一个数当基准比较大小”而是分区。你能不能在一次遍历里把数组整理成“基准左边都小于等于它、右边都大于等于它”的样子直接决定快排能不能排对。动画最好看的部分也在这里左右两个指针相遇的瞬间就是一趟分区结束的瞬间。1. 动画视角下的快速排序先让它在脑海里动起来1.1 快排不是“从中间切一刀”而是“按基准分成两堆”很多人对快速排序的直觉理解是取数组中间值左边排一遍右边排一遍然后就完成了。这个理解方向对了一半但“中间值”往往不是数组真实存在的元素而且把数组切分成两半并不等于把比基准小的放左边、比基准大的放右边。我建议你在脑子里建立这样一个画面整列待排序的数据像一排高低不同的柱子随机挑出一根柱子作为基准然后把比它矮的都挪到它左边比它高的都挪到它右边。挪完之后基准已经回到它最终应该待的位置。注意是最终位置因为它左边全部不高于它右边全部不低于它即使左右两部分内部还是乱的这个基准也永远不会再移动了。这就是快排第一层核心partition中文一般叫分区操作。一趟分区完成之后数组变成三个逻辑部分左区间值都小于等于基准。基准已经放在了正确位置。右区间值都大于等于基准。然后对左区间和右区间重复同样的操作。由于左右区间内部依然是“大乱中有小序”递归处理会让每个子区间最终只剩下一个元素或空区间排序结束。这也是为什么快速排序属于分治算法。它不是像归并排序那样先拆后合并而是在拆的过程中就已经完成大部分“跨元素比较”所以更省额外空间。1.2 动画播放时你真正应该盯住的是两个指针看快速排序动画最值得关注的不是最后那一下“变成了整齐序列”的爽快感而是每一轮里那两个指针的移动方式。大多数经典动画会选数组的第一个或最后一个元素当基准然后左右两边各有一个指针向中间移动左指针往右走找第一个大于等于基准的值。右指针往左走找第一个小于等于基准的值。左指针和右指针没有相遇就把两个位置的元素交换。继续走直到两个指针相遇或交错。把基准换到相遇位置这一趟结束。这里最容易看漏的一点是不是所有实现都采用这种“双指针交换法”。有的教材用的是“挖坑法”左边留一个坑从右往左填再从左往右填。这两种方式动画看起来不一样但目标一致都在完成一趟分区。我看网上不少动画演示用的是双指针交换代码却是挖坑法初学者对不上就会产生“动画里的交换次数和代码怎么不一样”的疑惑。所以学快排之前最好先固定一个你喜欢、且和代码对应的动画模型。我个人建议新手先掌握双指针交换法因为它和“交换”这个动作绑定得最紧密后面解释为什么一次交换能同时满足左右两侧有序逻辑时也更直观。注意不要同时学三种 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 大于 6rightIndex 继续向左移到 411 大于 6继续移到 325 大于 6继续移到 28 大于 6继续移到 117 大于 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 左边没有任何元素右边全部大于等于 66 确实已经回到最终位置。但这种做法效率不高因为 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右指针移到 57 小于 19右指针停在 5。 第 3 步左指针下标 0 小于右指针下标 5交换 25 和 7。此时数组[7, 3, 17, 12, 28, 25, 31, 19]继续第 4 步左指针从 0 继续向右移动。3 小于 19左指针变成 117 小于 19左指针变成 212 小于 19左指针变成 328 大于 19左指针停在 3。 第 5 步右指针从 5 继续向左移动。25 大于 19右指针变成 428 大于 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; } } } // 把基准放到 i1 的位置 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)但由于基准选择不同表现波动可以很大。这也是为什么很多标准库里的排序会用混合策略比如先快排区间较小就换插入排序。情况时间复杂度空间复杂度触发条件最好O(n log n)O(log n)每次分区接近等分平均O(n log n)O(log n)随机基准 / 常规数据最坏O(n²)O(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]和[pos1, right]不能把pos再放进去排否则基准已经归位还会被移动导致递归无法收敛。在递归入口处也要判断if (left right) { return; }这里left right表示只有一个元素不需要排序left right表示区间为空。如果源码里写成if (left right)而漏掉了left right当空区间传入时方法还会继续执行从而越界访问数组。5.3 partition 结果不符合“左小右大”时先检查什么如果你运行完发现数组没有完全有序可以用最小样例排查。我一般会这样做打印每次 partition 结束后基准下标左右两侧的区间值。检查左侧所有元素是否都小于等于基准。检查右侧所有元素是否都大于等于基准。如果左右某侧不满足说明指针扫描和交换逻辑有问题。如果有越界优先看right位置是不是最后一个元素递归区间是否把pos排除了。举个例子[2, 1]选最后一个元素 2 为基准i 0j 0。左指针扫描arr[0] 1 2i 变成 1进入右指针循环时 i 1j 0循环条件不满足。循环结束后 swap(arr[i], arr[right])结果是 [1, 2]正确。再比如[1, 2]选最后一个元素 2 为基准i 0j 0。左指针扫描arr[0] 1 2i 变成 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) { Dequeint[] 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 面试手写快排时可以先说清楚三件事如果面试时遇到手写快排我建议你先和面试官确认以下问题再动笔排序的是基本类型数组还是对象数组基本类型可以用不稳定排序对象数组如果需要稳定优先说归并而不是快排。允许额外空间吗如果只允许常数级额外空间那就必须用原地 partition。数组大概是什么形态如果已经知道几乎有序可以主动说采用随机基准或者三数取中避免退化。先确认这几点能让你的代码更贴合场景而不是只背一个模板。6.3 快速排序的扩展三路快排和双轴快排三路快排把数组分成三部分小于基准、等于基准、大于基准。它对重复元素多的数组非常高效。经典 Java 标准库对基本类型数组的排序改造思路也和类似方向相关但不是完全相同。三路快排的核心逻辑是维护三个区间指针lt小于区的右边界。i当前扫描元素。gt大于区的左边界。扫描过程中当前元素小于基准和lt1交换然后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 我个人建议的学习顺序如果你正在学快排我建议按这个顺序走看一段动画或手推动画建立对“分区”的动态画面。用 [6, 2, 8, 3, 9, 1] 这种小数组在纸上模拟一次完整排序至少写 4 到 6 行的中间状态。用 C 或 Java 写一个能跑通的递归版本。加打印日志观察每一轮基准位置和左右区间。用随机数据测试 1000 次排除边界隐患。再研究随机基准、三数取中、三路快排和非递归实现。这样一轮走下来比看十个动画都更能帮你形成稳定记忆。快排不是一个靠背代码能稳定的知识点它的价值在于你真正能控制递归和分区的过程。尤其当你遇到海量数据排序、TopK、手写标准库排序这类问题这种控制力会直接体现为代码质量和排错效率。 快速排序从动画到代码：分区、双指针与边界条件全解析
快速排序是那种看起来代码只有十几行、背起来也能背但自己动手写就很容易在边界条件上翻车的经典算法。不管是笔试、面试、期末考试还是日常开发里的 TopK、大数据分治它都是绕不开的基础。网上有很多“动画讲解快速排序”的形式把交换过程一帧一帧放出来确实比纯文字好懂但很多人看完动画还是会犯同一个问题动画看懂了自己写代码还是不对。这篇文章我准备换一种方式不是贴一个动态图就结束而是把“动画”拆成指针移动、交换、递归分治这几个步骤再落成 C 语言和 Java 的实现。我会把每一步为什么要这么写、什么时候会踩坑、数组下标为什么容易差一位都讲清楚。适合刚学完数据结构但还没吃透快排的新手也适合准备手写快排但经常被边界条件搞乱的读者。先说结论快速排序的核心不是递归也不是“拿一个数当基准比较大小”而是分区。你能不能在一次遍历里把数组整理成“基准左边都小于等于它、右边都大于等于它”的样子直接决定快排能不能排对。动画最好看的部分也在这里左右两个指针相遇的瞬间就是一趟分区结束的瞬间。1. 动画视角下的快速排序先让它在脑海里动起来1.1 快排不是“从中间切一刀”而是“按基准分成两堆”很多人对快速排序的直觉理解是取数组中间值左边排一遍右边排一遍然后就完成了。这个理解方向对了一半但“中间值”往往不是数组真实存在的元素而且把数组切分成两半并不等于把比基准小的放左边、比基准大的放右边。我建议你在脑子里建立这样一个画面整列待排序的数据像一排高低不同的柱子随机挑出一根柱子作为基准然后把比它矮的都挪到它左边比它高的都挪到它右边。挪完之后基准已经回到它最终应该待的位置。注意是最终位置因为它左边全部不高于它右边全部不低于它即使左右两部分内部还是乱的这个基准也永远不会再移动了。这就是快排第一层核心partition中文一般叫分区操作。一趟分区完成之后数组变成三个逻辑部分左区间值都小于等于基准。基准已经放在了正确位置。右区间值都大于等于基准。然后对左区间和右区间重复同样的操作。由于左右区间内部依然是“大乱中有小序”递归处理会让每个子区间最终只剩下一个元素或空区间排序结束。这也是为什么快速排序属于分治算法。它不是像归并排序那样先拆后合并而是在拆的过程中就已经完成大部分“跨元素比较”所以更省额外空间。1.2 动画播放时你真正应该盯住的是两个指针看快速排序动画最值得关注的不是最后那一下“变成了整齐序列”的爽快感而是每一轮里那两个指针的移动方式。大多数经典动画会选数组的第一个或最后一个元素当基准然后左右两边各有一个指针向中间移动左指针往右走找第一个大于等于基准的值。右指针往左走找第一个小于等于基准的值。左指针和右指针没有相遇就把两个位置的元素交换。继续走直到两个指针相遇或交错。把基准换到相遇位置这一趟结束。这里最容易看漏的一点是不是所有实现都采用这种“双指针交换法”。有的教材用的是“挖坑法”左边留一个坑从右往左填再从左往右填。这两种方式动画看起来不一样但目标一致都在完成一趟分区。我看网上不少动画演示用的是双指针交换代码却是挖坑法初学者对不上就会产生“动画里的交换次数和代码怎么不一样”的疑惑。所以学快排之前最好先固定一个你喜欢、且和代码对应的动画模型。我个人建议新手先掌握双指针交换法因为它和“交换”这个动作绑定得最紧密后面解释为什么一次交换能同时满足左右两侧有序逻辑时也更直观。注意不要同时学三种 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 大于 6rightIndex 继续向左移到 411 大于 6继续移到 325 大于 6继续移到 28 大于 6继续移到 117 大于 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 左边没有任何元素右边全部大于等于 66 确实已经回到最终位置。但这种做法效率不高因为 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右指针移到 57 小于 19右指针停在 5。 第 3 步左指针下标 0 小于右指针下标 5交换 25 和 7。此时数组[7, 3, 17, 12, 28, 25, 31, 19]继续第 4 步左指针从 0 继续向右移动。3 小于 19左指针变成 117 小于 19左指针变成 212 小于 19左指针变成 328 大于 19左指针停在 3。 第 5 步右指针从 5 继续向左移动。25 大于 19右指针变成 428 大于 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; } } } // 把基准放到 i1 的位置 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)但由于基准选择不同表现波动可以很大。这也是为什么很多标准库里的排序会用混合策略比如先快排区间较小就换插入排序。情况时间复杂度空间复杂度触发条件最好O(n log n)O(log n)每次分区接近等分平均O(n log n)O(log n)随机基准 / 常规数据最坏O(n²)O(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]和[pos1, right]不能把pos再放进去排否则基准已经归位还会被移动导致递归无法收敛。在递归入口处也要判断if (left right) { return; }这里left right表示只有一个元素不需要排序left right表示区间为空。如果源码里写成if (left right)而漏掉了left right当空区间传入时方法还会继续执行从而越界访问数组。5.3 partition 结果不符合“左小右大”时先检查什么如果你运行完发现数组没有完全有序可以用最小样例排查。我一般会这样做打印每次 partition 结束后基准下标左右两侧的区间值。检查左侧所有元素是否都小于等于基准。检查右侧所有元素是否都大于等于基准。如果左右某侧不满足说明指针扫描和交换逻辑有问题。如果有越界优先看right位置是不是最后一个元素递归区间是否把pos排除了。举个例子[2, 1]选最后一个元素 2 为基准i 0j 0。左指针扫描arr[0] 1 2i 变成 1进入右指针循环时 i 1j 0循环条件不满足。循环结束后 swap(arr[i], arr[right])结果是 [1, 2]正确。再比如[1, 2]选最后一个元素 2 为基准i 0j 0。左指针扫描arr[0] 1 2i 变成 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) { Dequeint[] 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 面试手写快排时可以先说清楚三件事如果面试时遇到手写快排我建议你先和面试官确认以下问题再动笔排序的是基本类型数组还是对象数组基本类型可以用不稳定排序对象数组如果需要稳定优先说归并而不是快排。允许额外空间吗如果只允许常数级额外空间那就必须用原地 partition。数组大概是什么形态如果已经知道几乎有序可以主动说采用随机基准或者三数取中避免退化。先确认这几点能让你的代码更贴合场景而不是只背一个模板。6.3 快速排序的扩展三路快排和双轴快排三路快排把数组分成三部分小于基准、等于基准、大于基准。它对重复元素多的数组非常高效。经典 Java 标准库对基本类型数组的排序改造思路也和类似方向相关但不是完全相同。三路快排的核心逻辑是维护三个区间指针lt小于区的右边界。i当前扫描元素。gt大于区的左边界。扫描过程中当前元素小于基准和lt1交换然后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 我个人建议的学习顺序如果你正在学快排我建议按这个顺序走看一段动画或手推动画建立对“分区”的动态画面。用 [6, 2, 8, 3, 9, 1] 这种小数组在纸上模拟一次完整排序至少写 4 到 6 行的中间状态。用 C 或 Java 写一个能跑通的递归版本。加打印日志观察每一轮基准位置和左右区间。用随机数据测试 1000 次排除边界隐患。再研究随机基准、三数取中、三路快排和非递归实现。这样一轮走下来比看十个动画都更能帮你形成稳定记忆。快排不是一个靠背代码能稳定的知识点它的价值在于你真正能控制递归和分区的过程。尤其当你遇到海量数据排序、TopK、手写标准库排序这类问题这种控制力会直接体现为代码质量和排错效率。