如果你现在正捧着教材在“排序”这一章来回翻页，多半是在期末复习、考研 408 备考，或者准备算法面试。数据结构里被点名频率最高的内容，就是这七大排序算法：直接插入、希尔、冒泡、快速、简单选择、堆排序、归并排序。它们按核心思想分成插入、交换、选择、归并四个门派，而交换门派里的冒泡排序和快速排序，又是很多人第一次接触“比较+交换”思路的起点。
这篇文章我会按“动图级拆解”的方式把这七个算法逐个讲透，尤其是交换排序，力求让你在脑子里形成画面感，而不是死记代码。最后还会给出复杂度对照表、期末考点、常见坑和一套可以直接写进实验报告的 C 语言框架。无论你用的是严蔚敏版《数据结构》，还是《数据结构与算法分析》的 Java 版，底层思路都是互通的，学完你会发现，排序并不难，难的是“为什么这样做”。
1. 先把七大排序放进一张表里看全貌
1.1 七大排序的四大门派
把七大排序按“一趟排序时的主导动作”分类，是最常见的分法：
| 门派 | 代表算法 | 核心动作 | 一句话记忆 |
|---|---|---|---|
| 插入排序 | 直接插入排序、希尔排序 | 把元素插入到已有序序列中 | 像理扑克牌 |
| 交换排序 | 冒泡排序、快速排序 | 通过交换相邻或跨位置的元素获得有序 | 大的往后沉，小的往前冒 |
| 选择排序 | 简单选择排序、堆排序 | 每一趟选出极值放到正确位置 | 每次挑最小的放前面 |
| 归并排序 | 二路归并排序 | 分治后合并两个有序序列 | 先拆分，再合并 |
这个分类在期末复习、考研真题里经常直接考。题目会问你“下列哪个属于交换排序”，或者“哪种排序可能出现在快速排序的分区结果里”。你只要记住门派归属，选择题基本不丢分。
1.2 稳定性：最容易记混的概念
“稳定性”是指：如果两个元素的值相等，排序结束后它们的相对顺序能不能保持原样。能保持，就称这个排序算法稳定；不能保持，就不稳定。
我举个例子：数组里有两条记录，都是成绩 90 分，其中甲记录在原数组里排在乙记录前面。排序后如果甲仍然在乙前面，这就是稳定排序。为什么实际中有人在乎？比如按“总分降序、语文成绩降序”两级排序时，你通常先按语文排一遍，再按总分排一遍。如果第二遍用了不稳定排序，第一遍的结果可能被破坏，语文的高低顺序就乱了。
七大排序里，直接插入、冒泡、归并是稳定的；希尔、快速、简单选择、堆排序不稳定。这个结论你最好背下来，因为很多题不会直接问你定义，而是给一个例子让你判断排序过程是否可能来自某个算法。
1.3 “一趟”到底是什么意思
学了排序以后，你经常看到“经过第一趟排序后结果是什么”这种题。这里的“趟”不同算法定义不一样：
- 冒泡排序：每跑完一次内层循环，就叫一趟，这时最大或最小元素已经沉到该去的位置。
- 快速排序：每调用一次 partition，确定一个枢轴元素的最终位置，就叫一趟。
- 简单选择排序：每选出一个最小值放到前部，就是一趟。
- 希尔排序里的“趟”和增量次数有关，理解上要更灵活。
所以做题时先确认它是哪个算法，再数趟，否则很容易算错。
2. 交换排序动图拆解：冒泡排序
2.1 冒泡排序“动图视角”的一趟完整过程
我无法在文档里放真正的 GIF，但可以把每一帧逻辑写得非常清楚，你按下面节奏在脑子里放动画。
假设初始数组是[ 5, 1, 4, 2, 8 ]。第一趟冒泡：
- 第 1 帧：比较 a[0]=5 和 a[1]=1，5>1，交换，数组变
[1, 5, 4, 2, 8]。 - 第 2 帧：比较 a[1]=5 和 a[2]=4，5>4，交换，数组变
[1, 4, 5, 2, 8]。 - 第 3 帧：比较 a[2]=5 和 a[3]=2，5>2，交换，数组变
[1, 4, 2, 5, 8]。 - 第 4 帧：比较 a[3]=5 和 a[4]=8，5<8，不交换。
第一趟结束时，最大值 8 到了最后一位。这就是“冒泡”名字的由来：大元素像一个气泡，一路向右浮到顶部。
第二趟只需要比较到倒数第二个位置，因为最后一位已经确定是最大。以此类推，最多跑 n-1 趟就能全部有序。
2.2 冒泡排序代码与两层优化
基础版冒泡排序 C 语言实现：
void bubbleSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } }内层循环的n - 1 - i是一个关键点：第 i 趟开始时，数组最后 i 个位置已经排好了，不需要再碰。初学者最常犯的错误就是写成j < n - 1，多做很多无意义的比较。
冒泡排序有个经典优化。当某趟扫描中一次交换都没发生，说明整个数组已经有序，可以直接退出：
void bubbleSortOptimized(int a[], int n) { for (int i = 0; i < n - 1; i++) { int swapped = 0; for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; swapped = 1; } } if (!swapped) break; } }这个优化对“几乎有序”的数组帮助巨大。比如输入本来就只有两处逆序，优化后可能跑一两趟就结束，时间接近 O(n)。
2.3 冒泡排序的复杂度和实际评价
冒泡排序的时间复杂度：
- 最好情况（数组已经有序）：O(n)，因为有了 swapped 标记，只跑一趟。
- 最坏情况（数组逆序）：O(n²)。
- 平均情况：O(n²)。
空间复杂度 O(1)，因为只用了常数个辅助变量。
冒泡排序是稳定排序。这一点很好理解：它只在 a[j] > a[j+1] 时交换，相等元素不会交换相对位置。
不过冒泡排序在实际开发里几乎不会被大规模使用，因为 O(n²) 的复杂度太吃亏。它最大的价值是教学，适合用来建立“比较-交换-有序”的直觉。如果面试官让你写一个排序，你写了冒泡，等于在告诉他“我追求的是稳妥而不是性能”，但通常他们更期待看到快排或归并。
3. 交换排序动图拆解：快速排序
3.1 快速排序的“挖坑填数”每一帧怎么走
快速排序是交换排序里的重头戏，也是考研和面试必考内容。它也是高阶排序，大家都用分治法。
我用的版本是“挖坑填数法”，最容易手写。
假设数组是[ 4, 7, 3, 8, 2, 1, 6 ]，取第一个元素 4 作为枢轴 key。
第一趟 partition 的过程：
- 第 1 帧：key=4，把它“挖”走，a[0] 变成一个坑。
- 第 2 帧：从右往左找比 key 小的元素，找到 a[5]=1，把 1 填到 a[0] 的坑里。现在 a[5] 变成新坑。
- 第 3 帧：从左往右找比 key 大的元素，找到 a[1]=7，把 7 填到 a[5] 的坑里。现在 a[1] 变成新坑。
- 第 4 帧：从右往左找比 key 小的元素，找到 a[4]=2，把 2 填到 a[1] 的坑里。现在 a[4] 变成新坑。
- 第 5 帧：从左往右找比 key 大的元素，找到 a[2]=3，不大于 key，继续；a[3]=8 大于 key，把 8 填到 a[4] 的坑里。现在 a[3] 是坑。
- 第 6 帧：左右指针相遇在 a[3]，把 key=4 填回去。
一趟结束后，数组变成[1, 2, 3, 4, 8, 7, 6]。注意，4 左边的元素都小于等于 4，右边的元素都大于等于 4，但左、右内部还不一定有序。接下来对左半部分[1, 2, 3]和右半部分[8, 7, 6]递归执行同样的过程。
3.2 快速排序代码实现
int partition(int a[], int low, int high) { int pivot = a[low]; // 挖坑：先保存枢轴 while (low < high) { while (low < high && a[high] >= pivot) high--; // 从右找小于pivot的 a[low] = a[high]; // 填坑 while (low < high && a[low] <= pivot) low++; // 从左找大于pivot的 a[high] = a[low]; // 填坑 } a[low] = pivot; // 把枢轴放回坑 return low; } void quickSort(int a[], int low, int high) { if (low < high) { int pos = partition(a, low, high); quickSort(a, low, pos - 1); quickSort(a, pos + 1, high); } }写这段代码有几个必须注意的细节：
- 内层两个
while必须带low < high条件，否则指针会越界。 - 找右半部分用
>=而不是>，目的就是避免遇到相等元素时反复交换，增加稳定性概率（虽然快排整体仍不稳定）。 - partition 里最后一步
a[low] = pivot不能漏掉，否则枢轴元素直接丢了。
3.3 快排为什么最快，又为什么退化
快速排序的平均时间复杂度是 O(n log n)，关键词是“平均”。它特别适合在随机数据上工作：每次 partition 大概能把数组分成一半一半，递归深度就是 log n，每一层比较总次数约 n，合起来是 n log n。
但最坏情况下，如果每次选的枢轴都是当前区间的最大或最小值，分区后一侧是 n-1 个元素，另一侧是 0 个，递归深度变成 n，复杂度退化成 O(n²)。比如对已经有序的数组，固定选第一个元素做枢轴，就会发生退化。
常见的改进手段有：
- 三数取中法：取 low、mid、high 三个位置元素的中位数做枢轴。
- 随机选枢轴：从区间内随机挑一个元素和 a[low] 交换，避免对手精心构造退化数据。
- 小区间改用插入排序：当区间长度小于某个阈值时，直接插入排序更快，能省掉大量递归调用。
快速排序的空间复杂度主要来自递归栈，平均 O(log n)，最坏 O(n)。它不稳定，这也是它和归并排序对比时最吃亏的地方：归并稳定，快排快但不稳定。
4. 插入排序的两种玩法：直接插入与希尔排序
4.1 直接插入排序：扑克牌整理法
直接插入排序的思想非常生活化。你打扑克牌整理手牌时，通常拿到一张新牌，就把它插到已经排好的牌堆中合适的位置。这就是直接插入排序。
假设数组是[ 7, 2, 5, 1, 8 ]：
- 第一轮：从第二个元素 2 开始，把 2 和前面的 7 比较，7>2，把 7 后移一位，把 2 插入到最前面，得到
[2, 7, 5, 1, 8]。 - 第二轮：处理 5，7>5，向后移；2<5，停止，把 5 插入索引 1 处，得到
[2, 5, 7, 1, 8]。 - 第三轮：处理 1，7、5、2 依次后移，1 插入最前，得到
[1, 2, 5, 7, 8]。 - 第四轮：处理 8，它比前面的都大，位置不动。
代码：
void insertSort(int a[], int n) { for (int i = 1; i < n; i++) { int temp = a[i]; int j = i - 1; while (j >= 0 && a[j] > temp) { a[j + 1] = a[j]; j--; } a[j + 1] = temp; } }这里有个教科书里很常见的“哨兵”技巧。如果数组下标从 1 开始存元素，a[0] 空出来当哨兵，就可以把内层循环条件从j >= 0 && a[j] > temp简化为a[j] > temp。哨兵位上必然是比你当前元素小的值，循环一定会停下，避免了每次判断下界是否越界。
直接插入排序最好情况 O(n)，最坏和平均 O(n²)，空间 O(1)，稳定。它最大的优势是：当数据规模小，或者数据基本有序时，效率非常好。
4.2 希尔排序：分组的艺术
希尔排序是对直接插入排序的改进。直接插入排序的问题在于，每次只能把元素搬动一位。如果最小的元素在数组末尾，它需要一次次往前挪，效率很低。
希尔排序的思路是：先把数组按一定间隔 gap 分成若干组，组内做直接插入排序，然后缩小 gap 再做，直到 gap=1 时做最后一次普通的插入排序。
我拿数组[ 9, 8, 7, 6, 5, 4, 3, 2, 1 ]，初始 gap=4 来演示第一轮：
- 分组：下标 0、4、8 一组；1、5 一组；2、6 一组；3、7 一组。
- 组内插入排序后，数组变为
[1, 4, 3, 2, 5, 8, 7, 6, 9]。可以看到小元素一次往前跳了 4 个位置，而不是只挪一格。
然后再取 gap=2，再取 gap=1。最终 gap=1 时，数组已经接近有序，插入排序会非常快。
代码：
void shellSort(int a[], int n) { for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int temp = a[i]; int j; for (j = i - gap; j >= 0 && a[j] > temp; j -= gap) { a[j + gap] = a[j]; } a[j + gap] = temp; } } }希尔排序里最值得研究的是 gap 序列的选择。最常见的是从一个集合选择开始，比如从 n/4 开始还是 n/2 开始，对整体性能影响很大。它比选择更好的增量模式，因为已经导出了不同的结论。用希尔排序模拟常见场景，很难推导出复杂的结论。
从这里可以看到，希尔排序还是基于比较、移动和插入的，但它比较的是同组内的问题。没有第二个原因的替代路径，希尔通常是九个。
直接插入排序实现原理简单、稳定，对于 n 较小的序列效率比排序优秀。写出希尔循环后，只需验证。
4.3 什么时候该用插入排序
直接插入或希尔排序的适用场景：
- n 很小（例如 10 到 50 个元素），直接插入的最坏开销可忽略。
- 元素基本有序，只有少量倒置。这种时候直接插入的 O(n) 效率超越 O(n log n) 复杂度的排序算法。
- 希尔排序适合中等规模数据，比如几千到几万个元素，对空间要求低但又要比 O(n²) 快。
很多生产级排序实现中，会做一个“混合策略”：当快速排序递归到小区间时，改用插入排序收尾。这个策略正是利用了插入排序对小数据理论的高效率。
5. 选择排序家族：简单选择与堆排序
5.1 简单选择排序：每趟挑最小的放前面
选择排序的思路更直接：第 i 趟从剩余元素中找出最小值的下标，和第 i 个位置交换。
数组[ 29, 10, 14, 37, 13 ]的过程：
- 第一趟：在 [29,10,14,37,13] 中找到最小值 10 的下标 1，与 a[0] 交换，得到
[10, 29, 14, 37, 13]。 - 第二趟：在 [29,14,37,13] 中找到最小值 13 的下标 4，与 a[1] 交换，得到
[10, 13, 14, 37, 29]。 - 第三趟：在 [14,37,29] 中找到最小值 14，位置不用动。
- 第四趟：在 [37,29] 中找到最小值 29，交换得到
[10, 13, 14, 29, 37]。
代码：
void selectSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[minIndex]) { minIndex = j; } } if (minIndex != i) { int temp = a[i]; a[i] = a[minIndex]; a[minIndex] = temp; } } }简单选择排序无论数据是否有序，都要扫描 n-i-1 次来找最小值，所以最好、最坏、平均都是 O(n²)。空间 O(1)，不稳定。举一个不稳定例子：数组[5, 5, 1]，第一趟把 1 与第一个 5 交换，两个 5 的相对顺序就变了，后面的 5 跑到了前面。
5.2 堆排序：把数组看成完全二叉树
堆排序是七大排序里唯一和数据结“树”强相关的。它把数组看成一颗完全二叉树，然后反复建大根堆，把堆顶最大值放到数组末尾。
大根堆的定义是：每个节点的值都大于等于它的左右孩子。堆顶就是最大值。
两个关键操作：
- 向下调整：从某个节点开始，与其左右孩子比较，把最大的孩子提上来，直到合适位置。
- 建堆：从最后一个非叶子节点开始，倒序对所有非叶子节点执行向下调整。
代码：
void heapAdjust(int a[], int i, int n) { int temp = a[i]; for (int j = 2 * i + 1; j < n; j = 2 * j + 1) { if (j + 1 < n && a[j] < a[j + 1]) j++; if (temp < a[j]) { a[i] = a[j]; i = j; } else { break; } } a[i] = temp; } void heapSort(int a[], int n) { // 建大根堆 for (int i = n / 2 - 1; i >= 0; i--) { heapAdjust(a, i, n); } // 逐个把堆顶换到末尾 for (int i = n - 1; i > 0; i--) { int temp = a[0]; a[0] = a[i]; a[i] = temp; heapAdjust(a, 0, i); } }注意这里数组下标从 0 开始，所以左孩子是2*i+1，右孩子是2*i+2，最后一个非叶子节点是n/2-1。
排序过程粗略展开：
- 建堆后，例如
[ 91, 60, 85, 24, 37, 78, 62 ]，堆顶 91 是最大值。 - 第一步：把 91 和数组末尾元素交换，9 变为堆尾，当前调整范围减少到前 6 个元素。
- 第二步：对堆顶执行向下调整，新的堆顶变成剩余元素中的最大。
- 重复 n-1 次，数组逐步从后往前有序。
堆排序时间复杂度是 O(n log n)，且建堆过程只需 O(n) 的线性时间，之后每趟调整 O(log n)。空间复杂度 O(1)。它不稳定，因为堆调整过程中元素的父子关系很容易破坏相同值的相对顺序。
5.3 堆排序的易错点
写堆排序最容易错的地方有三个：
- 下标搞混。从 1 开始计数和从 0 开始计数的代码差异很大，面试和考试前提前定好一种写法，别来回切换。
- 调整堆时忘记限定当前堆的大小 n。堆排序过程中 n 在逐渐变小，必须把它作为参数传入。
- 建堆时从
n/2 - 1开始，而不是从 n-1 开始。叶子节点没有孩子，不需要调整。
堆排序虽然代码稍长，但它是“原地排序”里最稳定的 O(n log n) 算法之一，不需要额外大内存，这是它相比归并排序的优势所在。
6. 归并排序：分治合并的经典代表
6.1 归并排序的两步走：拆分与合并
归并排序遵循“分治法”。先把数组不断从中间拆成左右两个子数组，直到每个子数组只剩一个元素，然后再两两合并成有序数组。
一个只有两个元素的小数组，比如[3, 1]，拆分后是[3]和[1]，合并时比较 3 和 1，得到[1, 3]。这就是整个算法的最小单元。
合并两个有序数组[1, 5, 9]和[2, 6, 8]的过程很像双指针：
- 比较 1 和 2，取 1；
- 比较 5 和 2，取 2；
- 比较 5 和 6，取 5；
- 比较 9 和 6，取 6；
- 比较 9 和 8，取 8；
- 最后剩下 9。
每次把较小的那个拿出来，就能得到整体有序的新数组。
6.2 归并排序代码实现
void merge(int a[], int left, int mid, int right) { int len = right - left + 1; int temp[len]; int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (a[i] <= a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } while (i <= mid) temp[k++] = a[i++]; while (j <= right) temp[k++] = a[j++]; for (k = 0; k < len; k++) { a[left + k] = temp[k]; } } void mergeSort(int a[], int left, int right) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(a, left, mid); mergeSort(a, mid + 1, right); merge(a, left, mid, right); } }写归并最要注意 merge 函数里的拷贝操作。很多人把a[left + k]写成a[k]，会导致结果出现大量 0 或垃圾值，因为 temp 数组是从 0 开始的，而原数组是从 left 开始的。
6.3 归并排序的复杂度与外部排序思想
归并排序的时间复杂度是严格的 O(n log n)，无论最好、最坏、平均都一样。它的空间复杂度是 O(n)，因为 merge 过程需要额外申请一个和子数组长度相同的临时数组。
归并排序是稳定性排序，这一点在 O(n log n) 级别的排序里非常珍贵。面试官如果要求“稳定且高效”，归并就是标准答案。
还有一个知识延伸：归并排序的思想不只用在内存排序。当数据量大到无法全部装入内存时，可以先把文件分成多个小块，每块分别排序，再用多路归并合并成一个大文件。这在大数据处理场景里叫“外部排序”，底层框架很多都沿用了归并思路。
7. 一表记住复杂度与稳定性，期末复习直接背
7.1 八大性能对照表
| 排序算法 | 平均时间 | 最好时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 希尔排序 | 约 O(n^1.3) | O(n) | O(n²) | O(1) | 不稳定 |
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n)~O(n) | 不稳定 |
| 简单选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
这张表建议你抄一遍。考试和面试经常直接问，或把时间复杂度和稳定性混在一起考，比如“以下排序中，不稳定又是 O(n log n) 的是哪个”。
另外有些人会看到“八大排序”，那是在这七个之外加了一个基数排序。基数排序不基于比较，而是按位分配，时间复杂度是 O(d×(n+r))，稳定性取决于实现。七大排序里通常不包含基数，但不排除试卷扩充考察，顺手了解一下没坏处。
7.2 记忆口诀与选型逻辑
我记复杂度时有一句顺口溜：插冒选，稳不稳，冒插归是稳定军；快选堆希不稳定，归排堆快 log n 分。
- 稳定：直接插入、冒泡、归并。
- 不稳定：希尔、快速、选择、堆。
- 平均 O(n²)：直接插入、冒泡、简单选择。
- 平均 O(n log n)：快速、堆、归并。
- 希尔排序复杂度不是固定值，通常教材写约 O(n^1.3)，面试时你可以说“取决于增量序列”。
实际选型也有一条成熟经验链：
- 数据基本有序或数量很小 -> 直接插入排序。
- 一般大规模乱序数据 -> 快速排序，配合随机枢轴和小区间插入优化。
- 内存紧张但要求 O(n log n) -> 堆排序。
- 要求稳定 -> 归并排序。
- 不想写太多代码且数据量不大 -> 冒泡或选择。
7.3 408 和期末考试的常见考法
考研 408 里排序考点主要集中在：
- 一趟快排后的结果序列判断。
- 大根堆在插入、删除后的调整过程。
- 给初始序列，让你写出归并排序每轮合并结果。
- 比较各排序算法的时间、空间、稳定性。
建议你复习时动手做两个经典练习：
- 随便写一个数组，自己完整画一遍快速排序第一趟的挖坑过程，再和代码输出对照。
- 对同一个数组，分别用四个门派算法排序，打印每趟结果，观察它们对相同输入的“轨迹”有多么不同。
这两个练习做完，你会发现以前背不住的规则都变成了画面感。
8. 实验报告与 C 语言实战框架
8.1 一个可以直接跑的排序性能测量框架
期末很多课程要求交排序实验报告，最常见的要求是：实现至少四种排序，比较不同数据规模下的耗时，并分析复杂度。下面这套框架可以帮你少走很多弯路。
先写一个随机数组生成器：
#include <stdio.h> #include <stdlib.h> #include <time.h> void generateArray(int a[], int n, int maxVal) { for (int i = 0; i < n; i++) { a[i] = rand() % maxVal + 1; } }再写一个统一的排序调用函数。你可以复制同一份数组到多个备份数组，分别调用不同排序函数，避免“第一个排序把数组改乱，第二个排序拿到的是有序数组”的问题。样本数组拷贝用memcpy即可。
计时使用clock()：
clock_t start = clock(); bubbleSort(arr, n); clock_t end = clock(); double time_ms = (double)(end - start) / CLOCKS_PER_SEC * 1000; printf("耗时: %.3lf ms\n", time_ms);一个重要的实验细节：当 n 很小时（比如 1000），算法的耗时可能不到 1ms，计时结果会被噪声淹没。建议每组数据多测几次取平均值，或者把 n 拉到 1 万、10 万、100 万三个量级再观察 O(n²) 和 O(n log n) 的差距。数据规模到 10 万时，冒泡排序会明显卡顿，快排和归并则依然流畅，这种差距本身就是实验报告里最好的结论。
8.2 把输出做成“可眼观”的可视化过程
虽然没有真正的动图，但实验报告里可以做一种简单的可视化：每趟排序后打印当前数组状态。
void printArray(int a[], int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); }在冒泡排序内层循环结束时插入printArray(a, n)，就能看到每一趟的中间结果。在快排 partition 返回后打印，也能看到枢轴如何逐步归位。
我建议在调试排序程序设计时，只用少量数据，比如固定 8 个元素，不要使用随机数组。这样打印出的过程更容易和手工推演对照。
8.3 实验报告必写的分析维度
一份能拿高分的排序实验报告，至少要回答这几个问题：
- 每种排序在最好、最坏、平均情况下的比较次数和移动次数大致趋势。
- 不同数据规模下，运行时间增长速度是否符合理论复杂度。
- 稳定的排序和不稳定的排序，在交换相等元素时的表现差异。
- 空间开销差异。可以提到快排递归栈和归并临时数组的额外内存占用。
我见过很多学生把实验报告写成“代码展示+一张耗时表”，这很可惜。如果你能在报告中加一段对快速排序退化场景的分析，或者堆排序调整过程的分步图，老师会觉得你真的理解了算法，而不仅仅是运行代码。
9. 常见问题与排查技巧实录
9.1 七个典型坑速查表
| 症状 | 可能原因 | 解决办法 |
|---|---|---|
| 快排结果丢了一个元素 | partition 最后没有把 pivot 写回坑 | 检查a[low] = pivot是否执行 |
| 快排递归栈溢出 | 固定选第一个元素且输入有序，退化 O(n) | 改用三数取中或随机枢轴 |
| 堆排序前几个元素乱序 | 建堆起点选错 | 从n/2 - 1开始调整，而不是 n-1 |
| 归并结果有 0 或多个重复 | merge 拷贝回原数组时错用下标 | 用a[left + k] = temp[k] |
| 希尔排序结果不对 | 内层 j 步长没有用 gap | 确认j -= gap，而不是j-- |
| 冒泡越界访问 | 内层循环写成j < n | 写成j < n - 1 - i |
| 直接插入排序后末尾出现乱序 | temp 没有插回正确位置 | 检查a[j + 1] = temp是否在内层循环后执行 |
9.2 调试排序算法的实用心得
调试排序最忌讳一上来就盯着完整代码看。我习惯的做法是：先写一个只有 5 到 8 个元素的手工用例，在关键循环里打印数组状态，然后用纸笔同步推演。如果代码和手推结果在第几步出现分歧，就回看那一步的变量值，问题通常在几个循环边界条件里。
另外，排序算法刷题时有一个很重要的对比工具：写一个“暴力验证函数”：
int isSorted(int a[], int n) { for (int i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) return 0; } return 1; }每次写完排序后立刻调用它。如果返回 0，说明排序没排完或者中间覆盖了数据。这一步能省去大量人工检查时间。
在哈希表和排序数组结合的场景下，我还常用另一个方法：用一个足够大的数组，先用随机数打乱一遍，再排序，最后验证 isSorted。这个流程能一次性排除绝大多数越界和逻辑错误。
我个人在实际操作中还有一个体会：排序算法很多问题出在“边界是一个元素还是两个元素”的判断上。快排的if (low < high)、归并的if (left < right)、堆排序的for (int i = n / 2 - 1; i >= 0; i--)，这些边界条件不需要背，你要在心里画一棵递归树或完全二叉树，对着树想“什么时候该停”。
这七大排序学到后面，你会慢慢发现它们并不是七个孤立的知识点，而是四类策略的具体落地：插入法、交换法、选择法、分治法。真正把它们串起来以后，面对任何排序题，你都不会觉得慌。哪怕题目不是这七个里的任何一个，你也可以从这四种策略出发推理出思路。
如果你正准备期末考或 408，最后再分享一个小技巧：考前不要通读代码，拿起纸笔把每个排序的框架写一遍，写得出来，才算真的记住了。动图看得再多，不如自己动手画一遍。
