这次我们不背模板把快速排序“画”出来先看动画里的指针怎么移动再对照写 C 语言和 Java 实现最后跑随机批量测试和性能观察。很多朋友能背出快排的两层递归但一旦自己写就会卡在“为什么从右往左先找小”“为什么最后要把 pivot 回填”这类细节上。其实这些问题靠文字很难记住动画一旦跑起来逻辑会清楚很多。快速排序是面试和工程里最常见的排序算法之一又常被叫作快排、分区交换排序核心思路是分治从数组里选一个基准值把小于等于它的元素放到左边大于等于它的放到右边然后对左右两个子区间继续做同样操作。平均时间复杂度是 O(n log n)但它是一种不稳定排序最坏情况下会退化到 O(n²)。本文会用一段可直接运行的 Python 动画脚本把分区过程可视化再给出对应快速排序 C 语言代码和 Java 实现并配备随机批量测试与常见错误排查清单。如果你正在准备算法面试或者需要给别人讲排序这篇文章可以当作一份完整的演示资料。1. 快速排序核心特征速览先给一张快速排序核心特征速览表方便你快速判断这个算法的定位、复杂度和实现难点。特征项说明算法类别比较类排序、分治排序、原地排序核心思想选基准、分区、递归处理子区间平均时间复杂度O(n log n)最坏时间复杂度O(n²)常出现在已经有序且基准选择不佳时平均空间复杂度O(log n)来自递归调用栈最坏空间复杂度O(n)当递归深度退化为数组长度时稳定性不稳定相同值的相对顺序可能改变常用优化随机基准、三数取中、三向切分、小区间插入排序实现难点左右指针移动顺序、相等值处理、递归边界适合读者算法学习者、面试准备者、需要自定义排序的场景快速排序最精彩的地方不是“分治”这个抽象概念而是它通过一次分区就能让基准值回到最终位置。动画演示时红色柱子就是当前挑出来的基准橙色区域是仍需要排序的区间已经离开橙色区域的柱子说明它所在的分区已经结束可以不用再关注。这个可视化视角非常适合理解为什么快排结束后每个元素都各归其位。2. 快速排序原理动画里到底发生了什么看动画之前先把快速排序的核心流程拆成三步。第一步从当前区间里选一个元素作为基准 pivot最简单的做法是取区间第一个元素。第二步把小于基准的放到基准左侧大于基准的放到基准右侧这就是 partition 分区操作。第三步对基准左侧和基准右侧分别递归执行快速排序直到子区间只有一个元素或为空。一个常见的动画讲法是这样的画一列高低不同的柱子每根柱子代表数组里的一个数字。首先把第一个柱子标成红色表示它是本轮基准然后左边出现一个指针 low右边出现一个指针 high。high 从右往左移动碰到第一个比基准小的柱子就停下来low 从左往右移动碰到第一个比基准大的柱子就停下来。接着发生交换或填坑直到两个指针在某个位置相遇。相遇位置就是本轮基准应当回到的最终位置。把基准放回去之后数组自然就被分成了左右两块。这个过程只需要记住一条准则红色基准放回中间后左边所有柱子都不大于它右边所有柱子都不小于它。2.1 选基准与两个指针快排有很多写法但动画最容易讲清楚的是“挖坑填数法”。假设当前区间是 [low, high]我们把 arr[low] 当作基准 pivot并把 arr[low] 先取出来。此时 arr[low] 的位置可以理解成一个“空坑”。high 从右向左移动每遇到一个大于等于 pivot 的元素就继续左移直到找到小于 pivot 的元素把这个小于 pivot 的元素放进 low 位置的坑此时 high 位置又成为新的坑。接着 low 从左向右移动每遇到一个小于等于 pivot 的元素就继续右移直到找到大于 pivot 的元素把这个大于 pivot 的元素放进 high 位置的坑。如此反复low 和 high 会向中间靠拢。当 low 和 high 相遇时把一开始取出的 pivot 回填到相遇位置这一轮分区就完成了。动画里的核心观察点是这轮分区结束后不管左右两边内部是否有序pivot 本体的位置一定正确。也就是说pivot 的最终下标不会再改变后面的递归只需要处理它左边和右边的区间。这就是快速排序能放心递归的原因。2.2 一轮分区逐动作拆解用一组示例来看会更直观。假设当前数组是49, 38, 65, 97, 76, 13, 27, 49区间一开始是 [0, 7]取 arr[0] 49 作为 pivot。右边 high 从下标 7 开始扫描发现 49 不小于 pivot继续移动直到下标 6 的 27 小于 49于是 27 被填到 low 位置。左侧 low 再从左向右找大于 49 的元素找到下标 2 的 65 后65 又会被填到 high 位置。这个过程会一直持续到 low 与 high 相遇。最终分区结果大致是左侧区间27, 38, 13 pivot49 右侧区间76, 97, 65, 49之后左区间 [0, 2] 和右区间 [3, 7] 会继续重复相同流程。动画跑到这里时你会看到红色柱子的左右两部分被分开随后动画进入某个子区间把小区间的第一个柱子再标成红色继续下一轮分区。这样递归下去直到所有区间都处理完柱子就会呈现升序排列。3. 动画演示快速排序的环境准备与脚本动画可视化并不需要很重的依赖Python 环境加 matplotlib 就足够。下面的脚本会随机生成一批数字然后用柱状图播放快速排序每一轮分区完成后的状态。你不需要手动安装 CUDA、模型权重这类东西只需要一个能跑 Python 的本地环境。3.1 Python 环境准备建议先创建一个独立的虚拟环境避免把库装进系统环境。执行下面的命令python -m venv venv source venv/bin/activateWindows 下激活命令是venv\Scripts\activate然后安装依赖pip install matplotlib numpy如果希望把动画保存为 GIF还需要 Pillowpip install pillow这里不强制写死 Python 大版本实际操作时建议使用 Python 3.9 及以上版本。如果只跑动画脚本matplotlib 和 numpy 是主要依赖Pillow 仅在导出 GIF 时使用。3.2 完整 Python 动画脚本下面的脚本完整实现了挖坑填数版的快速排序同时记录每一轮分区完成后的状态再用 matplotlib 播放出来。脚本不到 80 行建议直接保存为quick_sort_visual.py。import random import copy import matplotlib.pyplot as plt from matplotlib.animation import FuncAnimation random.seed(7) # 数组长度24 比较合适太小看不出分区过程太大柱子拥挤 arr [random.randint(1, 100) for _ in range(24)] init_state copy.copy(arr) # snapshots 里保存的是动画帧(数组状态, low, high, pivot_index) snapshots [] def record(low, high, pivot_index-1): snapshots.append((copy.copy(arr), low, high, pivot_index)) def quick_sort(low, high): if low high: return pivot arr[low] i, j low, high # 挖坑法核心右指针找小左指针找大交替填坑 while i j: # 从右向左找第一个小于 pivot 的元素 while i j and arr[j] pivot: j - 1 arr[i] arr[j] # 从左向右找第一个大于 pivot 的元素 while i j and arr[i] pivot: i 1 arr[j] arr[i] # i 与 j 相遇pivot 回到最终位置 arr[i] pivot # 每完成一次分区记录一帧动画 record(low, high, i) # 递归处理左右两个子区间 quick_sort(low, i - 1) quick_sort(i 1, high) # 排序前记录随后完成排序 snapshots.insert(0, (init_state, 0, len(arr) - 1, -1)) quick_sort(0, len(arr) - 1) snapshots.append((copy.copy(arr), 0, len(arr) - 1, -1)) fig, ax plt.subplots(figsize(10, 5)) def draw(frame): state, low, high, pivot_idx snapshots[frame] ax.clear() colors [] for i in range(len(state)): if i pivot_idx: # 红色当前轮次基准的最终位置 colors.append(#e63946) elif low i high: # 橙色本轮仍在处理的区间 colors.append(#f4a261) else: # 蓝色已经完成的区域 colors.append(#457b9d) ax.bar(range(len(state)), state, colorcolors) ax.set_ylim(0, max(state) * 1.2) ax.set_title( Quick Sort #%d, low%d, high%d, pivot_idx%s % (frame 1, low, high, none if pivot_idx 0 else pivot_idx) ) ani FuncAnimation( fig, draw, frameslen(snapshots), interval400, repeatFalse, ) plt.show() # 如果想把动画保存成 gif把上面的 plt.show() 替换为下面这行 # ani.save(quick_sort.gif, writerpillow, fps3)运行命令python quick_sort_visual.py运行时你会看到一个窗口弹出柱子按随机高度排列动画会一帧一帧展示快速排序的分区结果。3.3 运行后看什么第一次运行动画时建议重点看四个地方。第一第一帧全部柱子都是橙色表示整个数组都在当前处理区间内。第二红色柱子出现后观察它如何逐渐移动到某根柱子上那根柱子就是当前基准值的最终位置。第三橙色区域会越来越小蓝色区域越来越大这说明递归已经处理完一部分排序。第四动画标题中的 low、high 越来越接近甚至出现 low 大于 high 的递归返回情况这是正常的。如果动画播放速度太快可以调大interval比如从 400 改成 800。如果觉得柱子太多可以把range(24)改成range(16)如果想让排序更直观可以把随机种子去掉每次运行都会生成不同的初始序列。运行动画后你会发现快速排序最大的视觉特征是“基准先归位再分治”并不是每轮都整体有序而是每轮都有一些元素被放到正确位置。4. 手写 C 语言快速排序对应动画逐行看动画脚本里的quick_sort是 Python 实现但代码逻辑和 C 语言几乎一一对应。下面给出一份标准的快速排序 C 语言代码其中 partition 直接写在递归函数内部没有单独封装子函数这样更适合和动画逐行对照。4.1 快速排序 C 语言代码#include stdio.h void quick_sort(int arr[], int low, int high) { if (low high) { return; } int pivot arr[low]; int i low; int j high; while (i j) { // 从右向左找第一个小于 pivot 的元素 while (i j arr[j] pivot) { j--; } arr[i] arr[j]; // 从左向右找第一个大于 pivot 的元素 while (i j arr[i] pivot) { i; } arr[j] arr[i]; } // i 与 j 相遇回填 pivot arr[i] pivot; // 递归处理左右区间 quick_sort(arr, low, i - 1); quick_sort(arr, i 1, high); } int main() { int arr[] {49, 38, 65, 97, 76, 13, 27, 49}; int n sizeof(arr) / sizeof(arr[0]); quick_sort(arr, 0, n - 1); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }编译运行gcc -o quick_sort quick_sort.c ./quick_sort预期输出13 27 38 49 49 65 76 97这份代码里最关键的一行是arr[i] pivot。动画中的“回填”体现在这里。如果不理解前面两段填坑逻辑这一行容易写错位置。只要 i 和 j 没有相遇就不能回填一旦相遇相遇点就是基准的最终落点。4.2 C 代码与动画的对照对照动画看代码会非常轻松动画里的橙色区间对应递归函数中的low到high红色柱子在代码里对应arr[i] pivot右侧扫描