尧图网页设计 
如果你现在正捧着教材在“排序”这一章来回翻页多半是在期末复习、考研 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]151交换数组变[1, 5, 4, 2, 8]。第 2 帧比较 a[1]5 和 a[2]454交换数组变[1, 4, 5, 2, 8]。第 3 帧比较 a[2]5 和 a[3]252交换数组变[1, 4, 2, 5, 8]。第 4 帧比较 a[3]5 和 a[4]858不交换。第一趟结束时最大值 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[j1] 时交换相等元素不会交换相对位置。不过冒泡排序在实际开发里几乎不会被大规模使用因为 O(n²) 的复杂度太吃亏。它最大的价值是教学适合用来建立“比较-交换-有序”的直觉。如果面试官让你写一个排序你写了冒泡等于在告诉他“我追求的是稳妥而不是性能”但通常他们更期待看到快排或归并。3. 交换排序动图拆解快速排序3.1 快速排序的“挖坑填数”每一帧怎么走快速排序是交换排序里的重头戏也是考研和面试必考内容。它也是高阶排序大家都用分治法。我用的版本是“挖坑填数法”最容易手写。假设数组是[ 4, 7, 3, 8, 2, 1, 6 ]取第一个元素 4 作为枢轴 key。第一趟 partition 的过程第 1 帧key4把它“挖”走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]把 key4 填回去。一趟结束后数组变成[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 比较72把 7 后移一位把 2 插入到最前面得到[2, 7, 5, 1, 8]。第二轮处理 575向后移25停止把 5 插入索引 1 处得到[2, 5, 7, 1, 8]。第三轮处理 17、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 再做直到 gap1 时做最后一次普通的插入排序。我拿数组[ 9, 8, 7, 6, 5, 4, 3, 2, 1 ]初始 gap4 来演示第一轮分组下标 0、4、8 一组1、5 一组2、6 一组3、7 一组。组内插入排序后数组变为[1, 4, 3, 2, 5, 8, 7, 6, 9]。可以看到小元素一次往前跳了 4 个位置而不是只挪一格。然后再取 gap2再取 gap1。最终 gap1 时数组已经接近有序插入排序会非常快。代码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*i1右孩子是2*i2最后一个非叶子节点是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×(nr))稳定性取决于实现。七大排序里通常不包含基数但不排除试卷扩充考察顺手了解一下没坏处。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最后再分享一个小技巧考前不要通读代码拿起纸笔把每个排序的框架写一遍写得出来才算真的记住了。动图看得再多不如自己动手画一遍。 七大排序算法动图级拆解：从冒泡快排到复杂度对照
如果你现在正捧着教材在“排序”这一章来回翻页多半是在期末复习、考研 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]151交换数组变[1, 5, 4, 2, 8]。第 2 帧比较 a[1]5 和 a[2]454交换数组变[1, 4, 5, 2, 8]。第 3 帧比较 a[2]5 和 a[3]252交换数组变[1, 4, 2, 5, 8]。第 4 帧比较 a[3]5 和 a[4]858不交换。第一趟结束时最大值 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[j1] 时交换相等元素不会交换相对位置。不过冒泡排序在实际开发里几乎不会被大规模使用因为 O(n²) 的复杂度太吃亏。它最大的价值是教学适合用来建立“比较-交换-有序”的直觉。如果面试官让你写一个排序你写了冒泡等于在告诉他“我追求的是稳妥而不是性能”但通常他们更期待看到快排或归并。3. 交换排序动图拆解快速排序3.1 快速排序的“挖坑填数”每一帧怎么走快速排序是交换排序里的重头戏也是考研和面试必考内容。它也是高阶排序大家都用分治法。我用的版本是“挖坑填数法”最容易手写。假设数组是[ 4, 7, 3, 8, 2, 1, 6 ]取第一个元素 4 作为枢轴 key。第一趟 partition 的过程第 1 帧key4把它“挖”走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]把 key4 填回去。一趟结束后数组变成[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 比较72把 7 后移一位把 2 插入到最前面得到[2, 7, 5, 1, 8]。第二轮处理 575向后移25停止把 5 插入索引 1 处得到[2, 5, 7, 1, 8]。第三轮处理 17、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 再做直到 gap1 时做最后一次普通的插入排序。我拿数组[ 9, 8, 7, 6, 5, 4, 3, 2, 1 ]初始 gap4 来演示第一轮分组下标 0、4、8 一组1、5 一组2、6 一组3、7 一组。组内插入排序后数组变为[1, 4, 3, 2, 5, 8, 7, 6, 9]。可以看到小元素一次往前跳了 4 个位置而不是只挪一格。然后再取 gap2再取 gap1。最终 gap1 时数组已经接近有序插入排序会非常快。代码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*i1右孩子是2*i2最后一个非叶子节点是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×(nr))稳定性取决于实现。七大排序里通常不包含基数但不排除试卷扩充考察顺手了解一下没坏处。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最后再分享一个小技巧考前不要通读代码拿起纸笔把每个排序的框架写一遍写得出来才算真的记住了。动图看得再多不如自己动手画一遍。