学数据结构的时候排序算法是一个绕不开的坎。哪怕你只是应付期末、考研或者一场笔试也迟早要在纸上手写冒泡、快排和堆排——这是数据结构这门课里最“出活”的部分。我当初啃严蔚敏《数据结构》C语言版的时候排序章节翻来覆去看了好几遍真正搞懂是在把每个算法亲手实现、跑通、再对比之后。所以这篇数据结构排序算法总结我把实际学习中的经验、手写代码的方法和踩过的坑放在一起尽量写得像复习笔记而不是教科书。无论是刚接触数据结构的新手还是马上要面对408数据结构考研、期末复习、实验报告的人这篇文章都能帮你少走弯路。排序算法看着多其实底层思想就那几条交换、选择、插入、分治、堆化、桶分配。把思路理清之后代码只是思想的翻译。下面我从全景到细节把八大排序算法总结一遍每种都给C语言风格的实现思路和关键注意点。1. 排序算法全景先搞清楚在学什么1.1 排序算法的本质解决“乱序”问题的通用套路排序算法要做的事情很简单把一个无序序列变成有序序列。但“简单”的结果背后却对应完全不同的策略有的算法笨但稳有的算法快但娇气有的算法省空间但牺牲稳定性。在数据结构课程里排序被放在查找之前讲是因为很多查找算法都要求数据有序比如二分查找。你连数据都没排好后面谈索引、谈搜索效率都是空谈。所以学习排序算法不要只背结论要理解每种算法是怎么一步步把序列“扳正”的。冒泡靠相邻比较交换选择靠每次挑最小放前面插入靠把新元素塞进已排序区间归并靠“分半-排序-合并”快排靠“选基准-分区-递归”堆排靠“维护堆序性”基数排序靠“按位分配再收集”。这些策略一旦清晰代码自然就能写出来。1.2 三个关键评价维度时间、空间、稳定性评价一个排序算法不能只说“快不快”至少要同时看三个维度。第一个是时间复杂度。多数排序算法的时间复杂度可以分为O(n^2)、O(n log n)和线性级别。O(n^2)适合小规模数据写起来简单O(n log n)是工程主流能处理大批量数据线性级别排序有条件限制不是所有场景都能用。第二个是空间复杂度。除了数据本身占用的空间算法还需要多少额外空间。原地排序如堆排只消耗常数级额外空间而归并排序需要O(n)的辅助空间。在内存紧张的嵌入式环境或大规模排序场景空间可能比时间更关键。第三个是稳定性。稳定性指的是排序前相等元素的相对顺序排序后能不能保持。比如一组学生记录先按学号排好再按成绩排如果排序算法稳定成绩相同的学生仍然保持学号顺序。这种性质在实际业务中非常有用数据库排序多关键字段时稳定性是重要考量。1.3 八大排序算法总览先建整体框架数据结构课程里常说的八大排序算法一般指冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、基数排序。有些教材会把基数换成计数排序本质都是利用“桶”思想的线性排序。先记住这张总览表学习时就有了地图。排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定希尔排序约O(n^1.3)O(n^2)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n^2)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定基数排序O(d*(nk))O(d*(nk))O(nk)稳定这张表里的“稳定性”是高频考点判断题和选择题经常出。我自己的记忆方法是看算法在交换时是否可能“跨越”相等元素。选择排序每次把最小值换到前面时可能把相等的值换到后面去所以不稳定希尔排序分组后元素可能跨组移动所以不稳定快排分区时基准交换也会打乱相等元素顺序所以不稳定。只有冒泡、插入、归并、基数这类相邻或按位处理的排序稳定性才有保障。2. 手写记忆核心从代码看懂每种排序2.1 O(n^2)三件套冒泡、选择、插入冒泡排序是很多人接触的第一个排序算法。它的思路是从头到尾两两比较相邻元素如果顺序错误就交换每一轮结束会让当前未排序部分的最大值“冒”到末尾。C语言的经典写法如下。void bubble_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped 1; } } if (!swapped) break; } }注意我加了一个swapped标记如果某一轮没有任何交换说明数组已经有序可以直接跳出。这个优化平时写代码体会不深但实验报告里如果分析“最好情况时间复杂度为O(n)”就是基于这个优化。选择排序则换了一种思路每一轮从剩余元素中选出最小值放到已排序区间的末尾。它的交换次数远少于冒泡但比较次数依然是O(n^2)。void selection_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int min_idx i; for (int j i 1; j n; j) { if (arr[j] arr[min_idx]) min_idx j; } if (min_idx ! i) { int tmp arr[min_idx]; arr[min_idx] arr[i]; arr[i] tmp; } } }选择排序最大的坑就是它不稳定。举个具体例子数组[2a, 2b, 1]第一轮会把2a和1交换变成[1, 2b, 2a]两个2的相对顺序就变了。笔试如果问“稳定的O(n^2)排序是什么”首选插入排序而不是选择排序。插入排序的思路很像我们整理扑克牌手里已经排好的部分每次从后面拿一张新牌往前找合适位置插进去。代码最直观。void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }插入排序在“基本有序”的数据上表现非常好最好的情况直接退化成O(n)。很多工程排序比如Timsort会把插入排序用作小规模子序列排序就是看中它对局部有序数据的适应能力。考试复习时这三个算法要能手写还要会画每轮结果期末笔试最爱考这种过程题。2.2 进阶三巨头希尔、归并、快速希尔排序是对插入排序的改进核心思想是“先分组再整体插入”。它按一定间隔gap把序列分成若干子序列对每个子序列做插入排序然后逐步缩小gap直到gap为1时整个序列基本有序再做一次插入排序。C语言实现如下。void shell_sort(int arr[], int n) { for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key arr[i], j i; while (j gap arr[j - gap] key) { arr[j] arr[j - gap]; j - gap; } arr[j] key; } } }希尔排序的时间复杂度跟增量序列的选择有关平均约O(n^1.3)左右最坏情况仍可能是O(n^2)。考试一般不会让你严格推导希尔复杂度但要知道它突破了O(n^2)又比快排和归并更好写属于“性价比”很高的排序。归并排序是分治思想的典型代表。面试和专业题里常出现“利用分治思想修改合并排序算法”其实就是在说归并排序的递归分治流程把数组一分为二分别排序再合并两个有序子数组。归并排序的稳定性和O(n log n)的时间复杂度是它最大的优点代价是需要O(n)的辅助空间。void merge(int arr[], int left, int mid, int right) { int len right - left 1; int tmp[len]; int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) tmp[k] arr[i]; else tmp[k] arr[j]; } while (i mid) tmp[k] arr[i]; while (j right) tmp[k] arr[j]; for (int m 0; m len; m) { arr[left m] tmp[m]; } } void merge_sort(int arr[], int left, int right) { if (left right) return; int mid left (right - left) / 2; merge_sort(arr, left, mid); merge_sort(arr, mid 1, right); merge(arr, left, mid, right); }归并排序的递归思路很纯粹先处理左半边再处理右半边最后合并。合并时比较左右两个有序区间的头部把较小的放入临时数组。代码里我用的是变长数组如果在考研手写环境下不允许也可以改成malloc动态分配。要注意递归结束时需要把临时数组拷贝回原数组忘了这一步会得到错误结果。快速排序同样是分治思想但思路和归并相反归并是“先分再合并”快排是“先分区再递归处理左右两侧”。每次选一个基准值把小于它的放左边大于它的放右边然后对左右子区间递归排序。int partition(int arr[], int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } } int tmp arr[i 1]; arr[i 1] arr[high]; arr[high] tmp; return i 1; } void quick_sort(int arr[], int low, int high) { if (low high) return; int p partition(arr, low, high); quick_sort(arr, low, p - 1); quick_sort(arr, p 1, high); }快排是所有排序里最“娇气”也最实用的一个。平均复杂度O(n log n)但最坏情况数据已经有序且每次基准都选在端点会退化成O(n^2)。为了规避这个问题工程实现通常会做三件事随机选基准、三数取中、在递归区间很小时改用插入排序。考研笔试里经常考“快排第几趟后的结果”这类题目要按分区过程一步步推不能只背结论。2.3 堆排序与线性排序桶思想的两种玩法堆排序基于完全二叉树利用堆这种数据结构维护“最大堆”或“最小堆”的堆序性。最大堆的意思是父节点值大于等于子节点值堆顶就是最大值。排序时先把数组建成最大堆然后反复把堆顶和末尾元素交换缩小堆范围再调整堆。void heapify(int arr[], int n, int i) { int largest i; int l 2 * i 1; int r 2 * i 2; if (l n arr[l] arr[largest]) largest l; if (r n arr[r] arr[largest]) largest r; if (largest ! i) { int tmp arr[i]; arr[i] arr[largest]; arr[largest] tmp; heapify(arr, n, largest); } } void heap_sort(int arr[], int n) { for (int i n / 2 - 1; i 0; i--) heapify(arr, n, i); for (int i n - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; heapify(arr, i, 0); } }堆排序的优点是无论数据分布如何时间复杂度都稳定在O(n log n)而且空间复杂度只有O(1)是真正的原地排序。缺点是实际常数较大缓存很不友好所以工程上很少用堆排序做主排序算法更多用于“找前k大元素”或“优先队列”这类场景。线性排序里最常被提起的是计数排序和基数排序。计数排序要求数据是非负整数且范围不大思路是统计每个值出现的次数再根据次数把元素放回原数组。void counting_sort(int arr[], int n, int k) { int count[k 1] {0}; int output[n]; for (int i 0; i n; i) count[arr[i]]; for (int i 1; i k; i) count[i] count[i - 1]; for (int i n - 1; i 0; i--) { output[count[arr[i]] - 1] arr[i]; count[arr[i]]--; } for (int i 0; i n; i) arr[i] output[i]; }这里从后往前遍历是为了保证稳定性相同的元素在原数组中靠后的在排序后的数组中也尽量靠后这样同等关键字的次序不会乱。基数排序则是把数据按个位、十位、百位逐轮排序每轮借用稳定排序比如计数排序来保证整体有序。这类算法理解思想即可笔试手写频率不如前几种高。3. 排序算法比较与工程选型3.1 一张表看懂复杂度、稳定性与适用场景学完每个算法之后最需要做的一件事是横向对比。数据结构期末复习和408考研都喜欢考“以下哪个算法不稳定”“哪个排序空间复杂度为O(1)”这类题目。我把常见场景整理成了下面这张表可以直接背诵。排序算法什么时候优先用什么时候别用冒泡排序教学演示、数据量很小数据量一大就慢选择排序交换代价高、数据量小不稳定的场景慎用插入排序基本有序的数据、少量元素数据完全乱序且量大希尔排序中等规模、对稳定性无要求需要稳定结果的场景归并排序要求稳定、数据量大内存紧张时不合适快速排序通用排序、数据量大数据基本有序且枢轴选取不当堆排序需要稳定O(n log n)、空间受限对缓存友好度要求高的场景基数排序整数或等长字符串、范围可控浮点数、键值范围极大这八种排序不需要全背重点掌握“快排最快、归并最稳、堆排最省空间”这种口诀式结论再配合具体的复杂度分析笔试基本不会丢分。3.2 工程实战为什么默认排序算法都不是“教科书版本”如果去读实际工程源码会发现标准库的排序实现很少直接套用教科书版本。比如C语言的qsort、C的std::sort通常采用“快排插入排序”的混合策略Python的Timsort则融合了归并排序和插入排序专门处理真实数据中大量“部分有序”的情况。原因很简单真实数据不是理论模型。最坏情况O(n^2)的快排在绝大多数真实分布下都接近O(n log n)而且它的局部性很好。归并排序虽然稳定但需要额外内存堆排序虽然空间友好但跳跃访问导致缓存命中率低。所以工程排序往往牺牲理论纯净性用“组合拳”来取得平均最优效果。这部分如果写在实验报告或面试回答里会明显比单纯背复杂度显得有深度。3.3 考研408和期末复习怎么记才不亏如果你在准备408数据结构考研排序这一章的考法通常集中在复杂度的比较、稳定性的判断、一趟排序过程的手推。我的复习建议是先手写一轮全部代码再合上书写过程最后做横向比较。记忆稳定性时我自己用的是排除法只有“冒泡、插入、归并、基数”四个是稳定排序。为什么冒泡和插入稳定因为它们只在相邻元素间交换相等时不会越过彼此。归并稳定是因为合并时遇到相等元素取左区间的值。基数稳定是因为每轮都使用稳定排序。而选择、希尔、快排、堆排都不稳定。判断“四个稳定四个不稳定”比逐个硬背要容易。复杂度的记忆也有技巧元素比较型排序里基于比较的排序理论下界是O(n log n)所以归并、快排、堆排能达到平均O(n log n)就很正常纯暴力三个O(n^2)就是冒泡、选择、插入。空间复杂度特殊记忆归并O(n)的辅助空间最大快排递归栈平均O(log n)最坏O(n)其余三个原地排序都是O(1)。408真题还爱考“排序过程中元素移动次数”。插入排序移动次数多选择排序交换次数少但比较次数不变这些细节要靠手推题目来巩固只看不写很难形成直觉。4. 常见错误与实验避坑实录4.1 边界条件越界、空数组、重复元素排序代码最容易翻车的地方是边界条件。新手写冒泡时内层循环写成j n而不是j n - 1 - i就会在比较arr[j 1]时越界。写归并时递归出口忘记判断left right会导致无限递归。写快排时如果没有在low high时返回也会栈溢出。另一个容易被忽略的场景是空数组和单元素数组。很多排序函数对n 0或n 1的情况要能直接返回不能拿一个未初始化的临时数组去操作。重复元素也很考验稳定性如果排序算法在有大量重复值时仍然能保持相等元素原顺序就能算稳定的好算法。我在调试时发现计数排序最容易错在“累计频率之后赋回原数组”这一步。一定要记得从后往前遍历原数组并且每放入一个元素就对应count减一。如果从前往后遍历稳定性就丢了。排序正确性验证也建议多测几组特殊数据全正序、全逆序、全相等、包含负数如果算法只支持非负整数会出问题。4.2 稳定性的判断雷区和笔试常见坑稳定性是高频考点但也是很多人的丢分点。我见过很多同学把“快速排序不稳定”记成“稳定”原因是被快排的平均O(n log n)迷惑了。其实稳定性跟时间复杂度没有必然关系。判断时就看算法在交换元素时有没有可能跨越中间区域直接交换。选择排序的典型反例前面已经说过再补一个希尔排序的例子[3a, 2, 3b, 1]第一轮gap2时3a和1交换3b留在原位置两个3的相对顺序被破坏。这说明分组处理天然容易破坏稳定性。插入排序和冒泡排序之所以稳定是因为它们只交换相邻元素。而快排的partition中比较小的元素会越过pivot及其后面的元素被换到前面可能把相等的元素顺序打乱。所以“相邻交换可能稳定跳跃交换基本不稳定”这个判断技巧非常实用。4.3 排序实验报告怎么写不是交代码就完事很多同学写“数据结构排序算法实验报告”时只是贴一段代码再加几句复杂度分析这样分数往往不高。实验报告的核心是“过程对比”。我建议按这个结构组织实验目的、算法原理、代码实现、测试数据、结果分析、心得体会。结果分析部分要给出同一组随机数据下各排序算法的比较次数或运行时间。可以用时间函数在排序前后打点注意数据量要足够大比如10万级否则时间差异不明显。更细致的报告还可以画一张折线图展示不同数据规模下各算法耗时的增长趋势。这样写出来才像真正的实验而不是交作业。我还踩过一个坑在测试O(n^2)算法时数据量太小导致快排和冒泡的时间几乎一样数据量太大时又可能因为递归太深导致栈溢出。建议从1万、5万、10万、50万这几个规模开始测既能看出曲线差异又不会让程序直接崩溃。4.4 调试排序代码的几个小技巧排序算法有些错误很难直接看逻辑找出来我常用的排查手段是“小规模暴力验证法”。先生成一组很小的数据比如n6包含重复值然后把标准库排序结果和自己实现的结果逐项比对。一旦不一致就把数组打印出来手动推每一步。还有一个技巧是给排序函数加“断言”在排序完成后检查arr[i] arr[i 1]是否成立。这样能自动发现很多边界错误。写递归排序时我习惯在函数入口打印当前的left和right观察递归划分是否出现区间重叠。如果手写代码时遇到数组长度需要动态变化一定要谨慎处理变长数组和malloc。变长数组在某些编译环境不支持最好用动态分配同时记得free不然程序运行时间长了内存会持续增长。实验报告里有关时间复杂度对比时内存泄漏会让结果显得异常。排序算法的学习归根结底是“把抽象策略变成肌肉记忆”的过程。我最后想分享一个对我帮助很大的做法每天早上抽二十分钟不看任何参考资料在纸上手写一个排序算法然后对照标准实现找差距。连续两周后八大排序基本就不会再混淆了。考试时最怕的不是“不懂原理”而是“会做但手写超时”。把代码写得熟练、简短、减少多余变量笔试优势非常大。没写出来的边界条件一定要拿小数据跑一遍才能真的变成你自己的经验。