企业官网建设流程全解析

这次我们不背模板，把快速排序“画”出来：先看动画里的指针怎么移动，再对照写 C 语言和 Java 实现，最后跑随机批量测试和性能观察。很多朋友能背出快排的两层递归，但一旦自己写就会卡在“为什么从右往左先找小”“为什么最后要把 pivot 回填”这类细节上。其实这些问题靠文字很难记住，动画一旦跑起来，逻辑会清楚很多。

快速排序是面试和工程里最常见的排序算法之一，又常被叫作快排、分区交换排序，核心思路是分治：从数组里选一个基准值，把小于等于它的元素放到左边，大于等于它的放到右边，然后对左右两个子区间继续做同样操作。平均时间复杂度是 O(n log n)，但它是一种不稳定排序，最坏情况下会退化到 O(n²)。本文会用一段可直接运行的 Python 动画脚本把分区过程可视化，再给出对应快速排序 C 语言代码和 Java 实现，并配备随机批量测试与常见错误排查清单。如果你正在准备算法面试，或者需要给别人讲排序，这篇文章可以当作一份完整的演示资料。

1. 快速排序核心特征速览

先给一张快速排序核心特征速览表，方便你快速判断这个算法的定位、复杂度和实现难点。

快速排序最精彩的地方不是“分治”这个抽象概念，而是它通过一次分区就能让基准值回到最终位置。动画演示时，红色柱子就是当前挑出来的基准；橙色区域是仍需要排序的区间；已经离开橙色区域的柱子，说明它所在的分区已经结束，可以不用再关注。这个可视化视角非常适合理解为什么快排结束后每个元素都各归其位。

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 pivot：49 右侧区间：76, 97, 65, 49

之后，左区间 [0, 2] 和右区间 [3, 7] 会继续重复相同流程。动画跑到这里时，你会看到红色柱子的左右两部分被分开，随后动画进入某个子区间，把小区间的第一个柱子再标成红色，继续下一轮分区。这样递归下去，直到所有区间都处理完，柱子就会呈现升序排列。

3. 动画演示快速排序的环境准备与脚本

动画可视化并不需要很重的依赖，Python 环境加 matplotlib 就足够。下面的脚本会随机生成一批数字，然后用柱状图播放快速排序每一轮分区完成后的状态。你不需要手动安装 CUDA、模型权重这类东西，只需要一个能跑 Python 的本地环境。

3.1 Python 环境准备

建议先创建一个独立的虚拟环境，避免把库装进系统环境。执行下面的命令：

python -m venv venv source venv/bin/activate

Windows 下激活命令是：

venv\Scripts\activate

然后安装依赖：

pip install matplotlib numpy

如果希望把动画保存为 GIF，还需要 Pillow：

pip 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, color=colors) 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, frames=len(snapshots), interval=400, repeat=False, ) plt.show() # 如果想把动画保存成 gif，把上面的 plt.show() 替换为下面这行： # ani.save("quick_sort.gif", writer="pillow", fps=3)

运行命令：

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；右侧扫描