很多同学在学排序算法时都会有这种体验快速排序的静态图、小动画看了好几遍感觉“懂了”可真到面试或作业里自己手写一份partition指针一推就乱递归边界也经常差 1。本文就不只贴代码而是把快速排序的完整过程做成可直接运行的“控制台动画”用 Python 逐帧展示基准值如何把数组切分然后再给 C 语言和 Java 版本实现。无论你是期末复习、面试突击还是想彻底搞懂快速排序的分治思想这篇文章都值得照着敲一遍。1. 为什么要反复啃快速排序快速排序是很多教科书和数据机构课程里的重点排序算法也是面试中最高频的手写算法之一。它的思想并不复杂选一个基准值把小于等于基准值的元素放到左边把大于基准值的元素放到右边然后递归处理左右两部分。核心是“分治”两个字。实际应用里快速排序也频繁出现数据库、搜索引擎、各类中间件在内存数据排序时普遍会使用快速排序或其改进版本Java 的Arrays.sort对基本类型数组的默认排序实现就和快速排序有很深关系很多面向大数据、高并发场景的排序工具也往往先通过快速排序思路做分区再配合插入排序、归并排序做优化。所以快速排序不只是应付考试的知识点而是阅读底层源码、解决海量数据 TopK、实现自定义排序逻辑的基础。真正理解快速排序后再看系统库里的排序源码会轻松很多。本文希望帮你达到三个目标理解快速排序的分治流程掌握基准值、左右指针这些核心概念通过一个“动画版” Python 演示程序看到每一轮交换究竟发生了什么掌握快速排序 C 语言和 Java 实现包括递归版、非递归版以及容易踩的坑。2. 快速排序的核心思想分治与挖坑2.1 什么是“分治”快速排序Quick Sort由 Tony Hoare 在 1959 年提出属于“分而治之”型算法。把一个规模较大的数组拆成规模较小的子数组只要子数组排序正确整个数组自然有序。它的步骤可以概括为三句话从数组中选择一个元素作为“基准值”pivot重新排列数组使得左侧元素都小于等于基准值右侧元素都大于基准值这个过程叫做“分区partition”对基准值左边和右边的子数组分别递归执行上述操作。算法在每一轮都把问题规模减半这是它平均时间复杂度为 O(n log n) 的基础。为了直观理解我用一份长度为 7 的数组逐步演示。2.2 手动走一遍“挖坑法”先看数组[6, 2, 4, 7, 1, 5, 3]如果选择第一个元素作为基准值那么pivot 6。挖坑法的意思是先把arr[0]这个位置当成一个“坑”基准值 6 单独拿出来。接着从右侧开始找比基准值小的元素右侧第一个元素是 3小于 6于是把 3 填入最左侧的坑[3, 2, 4, 7, 1, 5, 3]此时右侧arr[6]位置变成新坑。再从左侧向右找比基准值大的元素找到 7把 7 填入右侧坑[3, 2, 4, 7, 1, 5, 7]数组在表面上出现重复元素不用紧张因为其中一个位置是“新坑”逻辑上是被挖空的位置。继续从右侧向左找小于 6 的元素5 符合条件把 5 填到左侧坑[3, 2, 4, 5, 1, 5, 7]此时左侧位置变成新坑继续从左侧向右找大于 6 的元素一直找到左右指针相遇没再找到。最后把基准值 6 放回坑里[3, 2, 4, 5, 1, 6, 7]这一轮分区后6 的左边都比 6 小右边只有 7 比 6 大。接下来分别对[3, 2, 4, 5, 1]和[7]递归排序就能得到最终的有序数组。2.3 关键概念区分很多初学者会把快速排序和归并排序搞混。归并排序是“先拆后合”先不断对半划分然后合并两个有序数组快速排序是“先分区后递归”每一层都在移动元素不需要显式的合并动作。快速排序还有几个重要特点原地方向大部分实现是通过交换数组内部元素完成的额外空间主要用于递归调用栈不稳定性相等的元素在分区过程中可能改变相对顺序所以如果需要稳定排序要谨慎使用最坏情况每次选择的基准值都是当前区间最小值或最大值时递归会退化成 O(n^2)。3. 动画讲解思路怎样用代码“看见”快速排序静态代码和动态演示最大的区别在于代码只告诉我们“结果”动态演示能展示“过程”。为了让快速排序的过程清晰可见最容易实现的一种方式就是控制台动画。整体思路是让程序在关键节点暂停并打印当前数组形成多帧画面用下标行显示每个元素的位置用数值行显示数组当前内容用柱状图显示元素大小关系用标记行显示当前“坑”、左右指针等关键位置。每打印一帧后程序sleep一小段时间视觉上就形成了动态效果。虽然比不上网页动画华丽但它的优势是零依赖、可复制、能看清每一次交换前后的状态特别适合学习算法时对照代码观察。动画演示不追求一次性跑出动画重点在于让你能暂停观察。因此下面的 Python 程序会在每次数组变化时输出一帧非常适合教学。如果你用的是命令行终端建议把窗口拉大、选择等宽字体效果会更好。4. 环境准备与实验目录结构本教程涉及的代码主要使用 Python、C 和 Java。快速排序算法本身没有复杂的第三方依赖只要有对应语言的编译器或解释器即可。版本没有统一要求你可以根据自己电脑环境调整Python 3.8用于运行动画演示GCC 或 Clang用于编译 C 语言示例JDK 8用于编译和运行 Java 示例为了便于对照我建议创建下面的目录结构quick-sort-demo/ ├── python/ │ └── animation_demo.py ├── c/ │ ├── quick_sort_recursive.c │ └── quick_sort_iterative.c ├── java/ │ ├── QuickSort.java │ └── QuickSortIterative.java如果你本机没有安装 GCC 或 JDK只想学习思路也可以跳过对应语言的运行步骤只阅读核心代码。重点是把分区思想理解透语言反而是次要的。5. 动画演示快速排序分区过程可视化这一份 Python 代码会完整展示挖坑法快速排序的每一帧。为了方便在各种终端环境运行程序没有使用清屏函数而是用长分隔线区分每一帧这样输出记录还能保留下来。运行后你会看到数组慢慢从无序变为有序。# 文件路径quick-sort-demo/python/animation_demo.py import time SLEEP_SEC 0.6 def render(arr, title, markersNone): 打印当前数组状态形成动画中的一帧 print( * 60) print(title) marker_map {} if markers: marker_map dict(markers) idx_line 下标: val_line 数值: bar_line 柱状: mark_line 标注: for i in range(len(arr)): cell str(i).center(4) val_cell str(arr[i]).center(4) bar_cell (# * max(arr[i], 1)).center(8) mark_cell marker_map.get(i, ).center(6) idx_line cell val_line val_cell bar_line bar_cell mark_line mark_cell print(idx_line) print(val_line) print(bar_line) print(mark_line) print() time.sleep(SLEEP_SEC) def quicksort_animated(arr, low, high): if low high: render(arr, f区间 [{low}, {high}] 只剩 0 个或 1 个元素直接返回, [(low, 结束)] if low high else None) return pivot arr[low] i, j low, high render( arr, f对区间 [{low}, {high}] 开始分区基准值 pivot {pivot}先挖出 arr[{low}], [(low, 坑)] ) while i j: while i j and arr[j] pivot: j - 1 if i j: arr[i] arr[j] render( arr, f右侧 arr[{j}] {arr[i]} 小于基准值 {pivot}移动到 arr[{i}]新坑位置是 {j}, [(j, 新坑), (i, 已移入)] ) while i j and arr[i] pivot: i 1 if i j: arr[j] arr[i] render( arr, f左侧 arr[{i}] {arr[j]} 大于基准值 {pivot}移动到 arr[{j}]新坑位置是 {i}, [(i, 新坑), (j, 已移入)] ) arr[i] pivot render(arr, f左右指针相遇于 {i}把基准值 {pivot} 放回坑中, [(i, pivot)]) quicksort_animated(arr, low, i - 1) quicksort_animated(arr, i 1, high) if __name__ __main__: test_arr [6, 2, 4, 7, 1, 5, 3] print(快速排序动画演示初始数组) print( .join(str(v) for v in test_arr)) print(f每帧间隔 {SLEEP_SEC} 秒可通过修改 SLEEP_SEC 调整速度\n) quicksort_animated(test_arr, 0, len(test_arr) - 1) print(排序完成, test_arr)运行命令cd quick-sort-demo/python python animation_demo.py如果你希望动画慢一点或快一点可以直接修改SLEEP_SEC。例如把0.6改成1.2能更加仔细地观察每一步。从动画输出中你能看到几个重要现象每次分区会锁定一个基准值并且这个基准值在分区结束后会落在最终位置右侧小元素填到左侧左侧大元素填到右侧本质上就是“把每个元素搬运到它应该在的一侧”当左右指针相遇说明这一轮分区已经把所有元素扫描完毕。想真正理解快速排序不要只看最后的正确结果多关注“坑在哪儿”“为什么移动它”。6. 快速排序 C 语言实现6.1 递归版快速排序C 语言的快速排序是面试、考研、计算机等级考试中常见的代码题型。下面的实现和动画演示用的思路一致都是挖坑法以数组第一个元素为基准值。不同编译器环境都能直接编译。// 文件路径quick-sort-demo/c/quick_sort_recursive.c #include stdio.h // 挖坑法分区返回基准值最终所在下标 int partition(int arr[], int low, int high) { int pivot arr[low]; int i low; int j high; while (i j) { // 从右向左找第一个小于 pivot 的元素 while (i j arr[j] pivot) { j--; } if (i j) { arr[i] arr[j]; } // 从左向右找第一个大于 pivot 的元素 while (i j arr[i] pivot) { i; } if (i j) { arr[j] arr[i]; } } // i j 时就是最终基准值的坑位 arr[i] pivot; return i; } void quickSort(int arr[], int low, int high) { if (low high) { return; } int pivotIndex partition(arr, low, high); // 递归排序基准值左侧和右侧 quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex 1, high); } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {6, 2, 4, 7, 1, 5, 3}; int n sizeof(arr) / sizeof(arr[0]); printf(原始数组: ); printArray(arr, n); quickSort(arr, 0, n - 1); printf(排序后: ); printArray(arr, n); return 0; }编译运行cd quick-sort-demo/c gcc -o quick_sort_recursive quick_sort_recursive.c ./quick_sort_recursive运行结果预期是原始数组: 6 2 4 7 1 5 3 排序后: 1 2 3 4 5 6 76.2 非递归版快速排序递归虽然直观但极端情况下可能造成栈溢出。生产中如果数据量非常大或者递归深度受限可以用栈来模拟递归过程。C 语言里需要手动维护一个栈本文给一个基于数组栈的版本逻辑和递归版完全等价。// 文件路径quick-sort-demo/c/quick_sort_iterative.c #include stdio.h #include stdlib.h int partition(int arr[], int low, int high) { int pivot arr[low]; int i low; int j high; while (i j) { while (i j arr[j] pivot) { j--; } if (i j) { arr[i] arr[j]; } while (i j arr[i] pivot) { i; } if (i j) { arr[j] arr[i]; } } arr[i] pivot; return i; } void quickSortIterative(int arr[], int low, int high) { // 用数组模拟栈每个元素保存一个待排序区间的左右边界 int *stack (int *)malloc((high - low 1) * 2 * sizeof(int)); if (stack NULL) { return; } int top -1; stack[top] low; stack[top] high; while (top 0) { high stack[top--]; low stack[top--]; if (low high) { continue; } int pivotIndex partition(arr, low, high); // 先把右区间入栈再把左区间入栈 if (pivotIndex 1 high) { stack[top] pivotIndex 1; stack[top] high; } if (low pivotIndex - 1) { stack[top] low; stack[top] pivotIndex - 1; } } free(stack); } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {9, 3, 7, 1, 8, 5, 2, 6, 4}; int n sizeof(arr) / sizeof(arr[0]); printf(原始数组: ); printArray(arr, n); quickSortIterative(arr, 0, n - 1); printf(排序后: ); printArray(arr, n); return 0; }编译运行cd quick-sort-demo/c gcc -o quick_sort_iterative quick_sort_iterative.c ./quick_sort_iterative非递归版特别适合那些显式设置了线程栈大小或者不希望使用深层递归的场景。它能帮助你把“递归栈”这个过程理解得更扎实。7. 快速排序 Java 实现Java 版本的实现思路同样不变。类里可以放两个方法一个对外暴露排序入口一个对内实现递归和分区。为了方便复用我用int[]数组做演示读者自己练习时也可以改成泛型版本。// 文件路径quick-sort-demo/java/QuickSort.java import java.util.Arrays; public class QuickSort { public static void quickSort(int[] arr) { if (arr null || arr.length 0) { return; } quickSort(arr, 0, arr.length - 1); } private static void quickSort(int[] arr, int low, int high) { if (low high) { return; } 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[low]; int i low; int j high; while (i j) { while (i j arr[j] pivot) { j--; } if (i j) { arr[i] arr[j]; } while (i j arr[i] pivot) { i; } if (i j) { arr[j] arr[i]; } } arr[i] pivot; return i; } public static void main(String[] args) { int[] arr {6, 2, 4, 7, 1, 5, 3}; System.out.println(原始数组: Arrays.toString(arr)); quickSort(arr); System.out.println(排序后: Arrays.toString(arr)); } }运行命令cd quick-sort-demo/java javac QuickSort.java java QuickSort预期输出原始数组: [6, 2, 4, 7, 1, 5, 3] 排序后: [1, 2, 3, 4, 5, 6, 7]Java 中的Arrays.toString(arr)很实用方便直接查看数组内容。实际开发中如果你需要排序一个数组通常不建议再造轮子但学习阶段手动实现能帮你理解 JDK 源码里的各种优化。7.1 非递归版 Java 快速排序Java 里可以用Dequeint[]模拟栈每个元素保存一段待排序区间的[low, high]。代码比递归版稍长但本质上完全一致。// 文件路径quick-sort-demo/java/QuickSortIterative.java import java.util.ArrayDeque; import java.util.Arrays; import java.util.Deque; public class QuickSortIterative { public static void quickSortIterative(int[] arr) { if (arr null || arr.length 0) { return; } Dequeint[] stack new ArrayDeque(); stack.push(new int[]{0, arr.length - 1}); while (!stack.isEmpty()) { int[] range stack.pop(); int low range[0]; int high range[1]; if (low high) { continue; } int pivotIndex partition(arr, low, high); // 先压入右区间后压入左区间下次弹出时优先处理左区间 if (pivotIndex 1 high) { stack.push(new int[]{pivotIndex 1, high}); } if (low pivotIndex - 1) { stack.push(new int[]{low, pivotIndex - 1}); } } } private static int partition(int[] arr, int low, int high) { int pivot arr[low]; int i low; int j high; while (i j) { while (i j arr[j] pivot) { j--; } if (i j) { arr[i] arr[j]; } while (i j arr[i] pivot) { i; } if (i j) { arr[j] arr[i]; } } arr[i] pivot; return i; } public static void main(String[] args) { int[] arr {9, 3, 7, 1, 8, 5, 2, 6, 4}; System.out.println(原始数组: Arrays.toString(arr)); quickSortIterative(arr); System.out.println(排序后: Arrays.toString(arr)); } }运行结果原始数组: [9, 3, 7, 1, 8, 5, 2, 6, 4] 排序后: [1, 2, 3, 4, 5, 6, 7, 8, 9]递归版和非递归版的partition函数几乎完全相同差别只在“如何保存待排序区间”。递归版借助系统调用栈非递归版借助显式栈。理解这一点后遇到其他递归转非递归的问题也会更顺手。8. 复杂度分析与基准值选择8.1 时间复杂度怎么看快速排序的时间复杂度主要取决于分区是否均匀。如果每次分区都能把数组大致分成两半递归层数大约是 log2 n 层每层遍历所有元素总时间复杂度就是 O(n log n)。最好情况与平均情况都是 O(n log n)。最坏情况是基准值每次恰好选到当前区间的最小值或最大值比如对已经有序的数组选择第一个元素作为基准值。此时每次分区只消除一个元素递归树退化成一条链时间复杂度变为 O(n^2)。空间复杂度方面递归版主要消耗在调用栈上。平均情况下栈深度是 O(log n)最坏情况下是 O(n)。如果你担心最坏情况可以使用非递归版或者想办法让基准值更靠近中位数。8.2 常见的基准值选择策略固定选第一个元素只是最简单的实现方式工程上容易遇到有序数组退化问题。常见的优化手段有随机选择基准值从[low, high]区间随机取一个下标再与arr[low]交换。从概率上避免最坏情况三数取中取low、mid、high三个位置的中位数作为基准值能在大多数场景下改善分区质量递归到小区间时改用插入排序当区间长度小于某个阈值比如 10 或 16直接使用插入排序减少递归带来的函数调用开销。不过这些优化都会让代码变得复杂。作为初学阶段优先把基础实现写对再逐步引入优化。8.3 快速排序的稳定性问题快速排序是不稳定排序。假设数组中有两个值相同的元素分区时它们可能被交换到不同位置导致相对顺序变化。如果需求要求保持相同元素的原本顺序比如先按时间排序又要按用户 ID 排序且不能破坏第一次排序结果那就不能直接使用快速排序。JDK 在对对象数组排序时也会优先考虑稳定性的 TimSort。因此在工程选型时“快不快”只是一方面“稳不稳定”同样重要。9. 常见错误与排查思路我在初学快速排序时几乎把能犯的错都犯了一遍。下面整理出几个高频问题并给出排查方向。问题现象常见原因解决思路递归栈溢出StackOverflow数组接近有序且固定选第一个元素作为基准值递归层数过深改用随机基准值或三数取中数据量特别大时使用非递归版排序后仍有元素错位partition内的指针移动条件写错例如右指针没有加等号检查while (i j arr[j] pivot)和左侧移动条件保证重复元素也能正确处理程序陷入死循环指针在遇到相等元素时无法前进或者缺少i j判断在左右移动条件中加入i j限制重复值场景要测试全相同数组C 语言下标越界/段错误递归或迭代时传入了错误边界分区返回位置没有正确减 1打印 low、high、pivotIndex 调试确认递归区间是[low, pivotIndex - 1]和[pivotIndex 1, high]Java 数组越界异常while (i j)写法导致 i 越过右边界统一使用while (i j)风格并且先移动右指针再移动左指针动画运行时看起来卡顿帧间 sleep 时间设置过长或终端输出缓冲把SLEEP_SEC调小到 0.3如果重定向日志可在 print 中加flushTrue排查快速排序问题时最有效的技巧是“缩小数组规模”。用长度为 5 以内的数组例如[5, 1, 4, 2, 3]在每轮分区前后打印数组状态。一旦发现某个数字的相对顺序不对立刻能定位到具体步骤。如果只想快速验证正确性可以用三组典型测试数据空数组[] 单元素[1] 全相同[3, 3, 3, 3, 3] 升序[1, 2, 3, 4, 5] 降序[5, 4, 3, 2, 1]这些边界用例能逼出大多数实现问题。10. 最佳实践与工程建议10.1 生产环境优先使用系统排序库学习阶段手写快速排序是必要的但真实项目里应当优先使用成熟实现。C 语言可以用标准库的qsortJava 可以多用Arrays.sortPython 则直接使用内置sorted或list.sort。现代语言标准库的排序实现会结合数据规模、元素类型等因素做大量优化。比如 Java 对基本类型数组的排序实现可能采用双轴快速排序思路而对象数组会优先保证稳定性。直接调用库函数比自己手写更安全、更快也更利于维护。10.2 手写排序前先设计测试用例如果你在面试或作业中需要手写快速排序千万不要只写一个方法就结束。先设计用例再写实现写完用用例验证。我建议测试用例至少包含随机乱序数组元素全部相同的数组升序数组降序数组包含负数和大整数的数组。这五类用例可以快速发现排序是否稳定、是否死循环、是否越界。实际工程中还可以用断言工具或单元测试框架把这些用例固化成自动化测试。10.3 警惕最坏情况与递归深度快速排序虽然平均性能优秀但最坏情况退化到 O(n^2)这并不仅仅是理论上的问题。如果外部输入可控攻击者可能故意提交接近有序的数据使你的排序服务变慢。在安全性要求较高的环境里推荐使用随机化基准值或在算法入口统一对数据做洗牌。递归深度也需要留意。很多生产环境的线程栈默认是 1MB 左右当对百万级数据排序时如果递归退化成链状很容易栈溢出。可以使用非递归版也可以调整 JVM 或系统的栈大小但在分布式系统中动栈大小不是最好的选择优先改写算法更优雅。10.4 用可视化方式巩固算法理解动画的最终价值不是“看起来很酷”而是帮你建立正确的心智模型。建议你在跑完 Python 动画后自己画一遍递归树把每一层基准值的位置标出来。你会发现一个有序数组的递归树恰好是从顶到底的分区路径而完全有序数组配合固定首元素基准值时递归树会变成一条长长的链。这张递归树图比任何文字都更能说明退化问题的来源。动手实验时可以把 Python 动画脚本里的test_arr改成其他数组观察每一轮输出。反复修改、反复观察几次后你对分区过程的理解会明显提升。11. 总结与后续学习路线本文从快速排序的分治思想出发先讲解了挖坑法的核心概念然后用 Python 实现了控制台动画演示让数组交换过程“逐帧可见”。接着给出了 C 语言递归版、非递归版以及 Java 的快速排序实现。通过复杂度分析和常见错误总结你应该能掌握快速排序从理论到代码的完整闭环。遇到排序相关场景可以先用下面的清单快速决策排序数据量很小直接用标准库的排序函数学习或面试需要手写优先掌握挖坑法partition担心有序数组退化基准值改用随机选择或三数取中递归深度受限改用显式栈的非递归版需要稳定排序不要使用普通快速排序考虑归并排序。后续你可以继续深入学习三路快速排序它专门优化大量重复元素场景也可以去读 JDKArrays.sort源码通过源码观察系统库如何在快速排序和插入排序之间做取舍还可以练习 LeetCode 上“数组中的第 K 个最大元素”这类题目体会快速排序分区思想在查找问题中的扩展。如果这篇文章对你有帮助可以收藏备用。等你把动画脚本跑起来再亲手画一遍递归树相信快速排序会真正变成你的“条件反射式”算法。