【数据结构】八大排序算法详解C语言实现——这种标题我见过太多次了。第一次学数据结构的人多半以为这门课的任务就是把八个代码背下来可真到了面试或者真实项目里面试官一句“这八种排序你选哪种、为什么”就能筛掉一大半只会背代码的人。这篇文章我按自己的理解把插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序这八种算法串成一条线每个算法先讲直觉再给C语言实现然后说清楚复杂度、稳定性和容易踩的坑最后一章聊真实场景下怎么选型。特别适合正在学数据结构的同学、准备校招面试的工程师以及想把“背代码”升级成“真理解”的朋友。1. 打开排序的地图八种算法各自的定位与分类1.1 先搞清楚一个基本问题排序到底在排什么排序的目标很朴素给定一个无序序列按关键字从小到大或从大到小重新排列。在C语言里最直接的表示就是一个int数组但你不能只把这八种算法当八个模板记而要看清它们背后的几种“操作思路”相邻交换、扫描选极值、扑克牌式插入、分组跳步、树形锦标赛、分治快分、分治合并以及最后那个干脆不比较、只统计频次的家伙。我习惯把它们分成五条线插入类直接插入排序、希尔排序。核心动作是“把一个元素插入到前面已经有序的位置”。交换类冒泡排序、快速排序。核心动作是“通过交换消除逆序对”。选择类简单选择排序、堆排序。核心动作是“每趟挑出剩下元素里的最值”。归并类归并排序。核心动作是“把两个有序段合并成一个”。非比较类计数排序。核心动作是“统计频率按坐标放回根本不比较大小”。为什么要这样分因为一旦你确定了算法类别它的时间复杂度和稳定性就有了大致框架选择类普遍不稳定插入类容易做到稳定交换类里冒泡稳定、快排不稳定。这个分类习惯比你一个个去背结论要可靠得多。1.2 一张表看清复杂度、空间和稳定性下面这张表建议直接收藏面试前扫一眼非常有帮助排序算法平均时间复杂度最坏时间复杂度最优时间复杂度额外空间稳定性插入排序O(n²)O(n²)O(n)O(1)稳定希尔排序O(n^1.3)~O(n^1.5)O(n²)O(n)O(1)不稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定冒泡排序O(n²)O(n²)O(n)O(1)稳定快速排序O(n log n)O(n²)O(n log n)O(log n)~O(n)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定计数排序O(nk)O(nk)O(nk)O(k)稳定几个经常有人记错的地方我直接说透选择排序的最优时间也是O(n²)因为它不管数组是否有序都必须完整扫描剩余区间去找“最小值”。这和插入、冒泡的“最好情况O(n)”有本质区别。希尔排序的时间复杂度没有统一结论取决于增量序列。表里写的是经验范围考试时如果题目没有指定增量策略通常接受“大约在O(n^1.3)到O(n²)之间”的说法。快排的最坏O(n²)不是理论吓唬人一个已经有序的数组你每次都拿第一个或最后一个元素当基准就是实打实O(n²)。递归归并的空间是O(n)因为要开临时数组递归快排的空间主要花在调用栈上平均O(log n)退化时可以到O(n)。1.3 为什么“稳定性”被低估了一个真实的多关键字场景稳定性说的是两个关键字相等的元素排序后相对顺序保持不变那这个算法就是稳定的。初学者常觉得这只是概念题直到碰上多关键字排序才意识到它多重要。举个例子一份成绩表需求是先按总分降序总分相同的再按学号升序。最省事的做法是先按学号排一次再按总分排一次。第二次排序必须是稳定的否则总分相同的学生学号顺序就乱了。数据库里的ORDER BY、Excel多列排序、基数排序每一轮“按位排”背后全是稳定性在兜底。所以后面每个算法我都会单独说一句“稳定还是不稳定、为什么”。这比背“插入稳定、快排不稳定”的口诀有用得多因为你能讲出原因。2. O(n²)三兄弟插入、选择、冒泡的代码与真实差距2.1 冒泡排序相邻交换加一个提前退出标记冒泡最直观每一轮从头到尾比较相邻元素大的往后“浮”。经过n-1轮数组就排好了。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标记。没有它冒泡排序面对一个完全有序的数组依然要走完n-1轮、做大约O(n²)次比较非常浪费。加了这个标记完全有序时第一轮扫完发现没交换直接跳出最好情况变成O(n)。冒泡的另一个易错点是内层循环边界写成了n-1-i。每一轮结束最大值已经固定到末尾下一轮不需要再碰它。很多人写成j n - 1结果没错但白白多做了无效比较。冒泡排序是稳定的因为只有arr[j] arr[j 1]时才交换等于时不动。这个细节看着不起眼但它刚好是“稳定性由比较条件决定”这句话的最佳教材。2.2 选择排序每轮挑一个最小值交换次数最少选择排序的思路更“省事”第i轮在[i, n-1]范围内找出最小值记录下标然后和arr[i]交换一次。循环n-1轮就结束。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[i]; arr[i] arr[min_idx]; arr[min_idx] tmp; } } }对比冒泡就会发现冒泡每轮可能做很多次交换选择每轮最多只做一次交换。如果元素是很大的结构体、交换成本很高选择排序在“减少交换”这件事上的优势就会体现出来。但它也有明显的短板比较次数固定是n(n-1)/2就算数组已经有序它也得老老实实把所有元素扫一遍确认没有更小的了。所以选择排序的最优时间复杂度就是O(n²)这个点经常有人记错。选择排序也不稳定很多人不理解。看个例子原数组[2_a, 2_b, 1]两个2值相等用下标区分前后第一轮找到最小值1在位置2把它和位置0的2_a交换得到[1, 2_b, 2_a]。排序完成后原本在前的2_a跑到了2_b后面相对顺序被破坏。原因就是选择排序会让一个远处的“最小值”跨越中间元素直接来到前面这种跨距离交换天然无法保证稳定。2.3 插入排序扑克牌式整理实际最实用的O(n²)算法插入排序的思路和整理扑克牌一模一样手里已经排好一把牌新摸一张从右往左找它该放的位置插进去。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; } }两个细节必须说清楚第一while循环里不能写成arr[j] key。当前是严格大于才往后挪等于时不挪这样相等元素的相对顺序才不会变。一旦用了大于等于插入排序就从稳定变成不稳定。第二j 0的判断必须写在arr[j] key前面。C语言的从左到右短路求值当j变成-1时会先被判断出来后面不再访问arr[-1]。如果顺序反过来在j为-1时访问arr[-1]直接数组越界这是初学C语言时最隐蔽的段错误来源之一。插入排序最好的情况是数组几乎有序每个元素往前看一眼就能放好整个排序退化成一次线性扫描。这个性质在真实系统里极其重要因为很多数据恰恰是“刚刚被小幅修改过的有序数据”。这也是为什么后面快排在小区间会切到插入排序的原因。2.4 三个O(n²)算法实际该用谁说一个很实用的结论几百个元素以内、数据近似有序、希望代码稳定不出错无脑插入排序。希望讲清楚“相邻交换消除逆序”用冒泡排序做教学演示但工程里单独用它的时候很少。元素是很大的结构体、交换代价高、稳定性无所谓选择排序值得考虑。但更常见的场景里插入排序还是更好因为移动几个数组元素通常比交换两个大结构体便宜。一句话O(n²)本身不丢人丢人的是在数据量大时硬上O(n²)算法。3. 希尔排序让插入排序“健步如飞”的增量思想3.1 插入排序的痛点与“跳步”的直觉插入排序慢是因为它每趟只能把一个元素往左挪动一位。数据混乱的时候一个很小的元素想从数组末尾跑到前面要经历几乎整段数组的搬迁。希尔排序的想法很直接既然一步一挪太慢那就先离远点让元素一次跳好几步先做到“大致有序”最后一趟再来一次标准插入排序。这种“先粗糙整理、再精排”的思路让希尔排序也被叫做“缩小增量排序”。它不追求一趟就把数组排完而是分多趟进行每趟的步长gap不断缩小最后一趟gap1就是标准插入排序。因为前面几趟已经把序列收拾得接近有序最后一趟虽然用的是O(n²)的插入排序实际要挪的数据量却已经很小。3.2 增量序列的选择与C语言实现最简单好记的增量策略是gap从n/2开始每次gap / 2直到变成1。代码实现也不难把插入排序里所有相邻的1替换成gap就行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]; int j i - gap; while (j 0 arr[j] key) { arr[j gap] arr[j]; j - gap; } arr[j gap] key; } } }理解这段代码的关键是看清for (int i gap; i n; i)在做什么。它不是把数组切成几个互不相关的分组去分别插入排序而是“让每个元素都和自己前面第gap个位置的元素做插入排序”。一趟跑完所有间隔gap的子序列都各自有序。增量序列对希尔排序的影响很大。gap n/2折半只是最容易上手的方案理论更好的还有Hibbard增量1, 3, 7, 15…、Sedgewick增量1, 5, 19, 41, 109…等。实践的经验是好的增量序列能把平均复杂度拉到O(n^1.3)附近但考试和工程演示用折半增量已经足够。3.3 希尔排序为什么不稳定希尔排序的不稳定是“跨距离移动”直接导致的。相同的关键字可能被分到不同的gap分组里而不同分组的整理顺序有先后后面趟次又可能跨越多个位置调整元素。一来二去相等元素的相对顺序根本没有办法保持。这一点和插入排序形成了鲜明对比插入排序本身是稳定的但希尔排序把它包装成“跳跃版”之后稳定性就丢了。要是面试被问“为什么希尔不稳定”最简单的回答就是它把插入排序里的“相邻移动”变成了“隔段移动”隔段移动天然无法保证相等元素的先后关系。4. 堆排序把数组看成完全二叉树用树的高度换效率4.1 数组与完全二叉树的对应关系堆排序最需要切换的视角是一个数组本身可以被看作一棵完全二叉树。下标i的节点左孩子是2i1右孩子是2i2父节点是(i-1)/2。只要你接受了这个映射堆排序的大门就打开了。大顶堆的定义是每个节点都不小于它的两个孩子。这个性质给出一个关键结论堆顶arr[0]一定是整个数组的最大值。堆排序的核心就是反复利用这个结论把堆顶最大值和末尾元素交换缩小堆的范围再重新调整堆结构。4.2 heapify的核心实现非递归下沉调整堆的核心函数叫sift_down负责把某个元素向下“沉”到合适位置。我推荐非递归写法性能更稳边界也更可控void swap(int *a, int *b) { int tmp *a; *a *b; *b tmp; } void sift_down(int arr[], int n, int i) { while (1) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest i) break; swap(arr[i], arr[largest]); i largest; } }注意每次比较前都要检查left和right是否小于当前的堆大小n。堆排序过程中堆的有效长度不断变小下标越界是堆排序最常见的错误。建堆的写法是自底向上从最后一个非叶子节点开始逐个下沉void build_max_heap(int arr[], int n) { for (int i n / 2 - 1; i 0; i--) { sift_down(arr, n, i); } }为什么从n/2 - 1开始因为下标从n/2到n-1的节点全是叶子叶子没有孩子不需要下沉。最后一个非叶子节点的下标就是n/2 - 1。这里有个常被追问的复杂度问题建堆明明是n/2个节点各做一次下沉为什么总代价是O(n)而不是O(n log n)因为绝大多数节点都离叶子很近能下沉多层的高节点很少。树高h的节点大约只有n/2^(h1)个把每层的代价加起来总和会收敛到一个常数乘以n。第一次听这个结论觉得反直觉很正常画一棵满二叉树数一数每层有多少节点、每个节点最多下沉几层就一目了然了。4.3 两阶段流程与复杂度分析堆排序完整流程如下void heap_sort(int arr[], int n) { build_max_heap(arr, n); for (int i n - 1; i 0; i--) { swap(arr[0], arr[i]); sift_down(arr, i, 0); } }第一阶段建堆O(n)。第二阶段反复把堆顶最大值交换到数组末尾再把堆顶下沉每次O(log n)总代价O(n log n)。全程额外空间O(1)而且无论输入是什么样的数据堆排序都不会退化。这就是它比快排最核心的优势快排最坏可能O(n²)堆排序最坏也是O(n log n)。缺点是常数大实际执行往往不如平均情况下的快排猛加上堆顶和末尾元素的交换是远距离交换破坏局部性对CPU缓存不友好。4.4 堆排序的真实用途工程里很少用堆排序去排一个完整的大数组它的高光场景其实是“只需要前K个最大/最小元素但不用全排序”。比如从一百万个数里找最大的100个维护一个小顶堆遍历一遍每个数比堆顶大就替换并调整。这样时间和空间都远小于全排序。理解了堆的本质TopK问题其实就顺带会了。5. 快速排序分治思想的执行速度之王5.1 partition是快排的灵魂Lomuto写法快排的核心是partition选一个基准值pivot把数组分成“左边都小于等于pivot、右边都大于pivot”两个部分并返回pivot最终所在位置。最经典的Lomuto写法int partition_lomuto(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; swap(arr[i], arr[j]); } } swap(arr[i 1], arr[high]); return i 1; } void quick_sort(int arr[], int low, int high) { if (low high) { int pi partition_lomuto(arr, low, high); quick_sort(arr, low, pi - 1); quick_sort(arr, pi 1, high); } }Lomuto的设计思路是用i维护“小于pivot区域的右边界”用j扫描整个区间。每发现一个小于pivot的元素就把它放到i1的位置扫描完毕把pivot放到i1的位置这个位置就是它的最终位置。这个写法代码短、不容易错是我在面试时首选的分区写法。缺点是如果数组里大量元素等于pivot它会把相等的元素都放到左边导致左右规模不均衡性能退化。这种情况要配合随机pivot来缓解。5.2 Hoare写法和它的边界陷阱另一个经典写法是Hoare分区从两端向中间逼近。它交换次数平时比Lomuto少很多追求性能的实现都会选它int partition_hoare(int arr[], int low, int high) { int pivot arr[low]; int i low - 1; int j high 1; while (1) { do { i; } while (arr[i] pivot); do { j--; } while (arr[j] pivot); if (i j) return j; swap(arr[i], arr[j]); } }这段代码有很强的迷惑性我当年调试了很久才搞明白它的规则pivot取的是arr[low]但i从low-1、j从high1开始do while能保证进入循环后一定自增自减先动再看。返回的是j不是pivot的最终位置。递归时左半区间是[low, j]右半是[j1, high]。如果照抄Lomuto的[low, pi-1]会漏元素甚至死循环。极端输入下i和j可能出现越界风险所以工程上几乎不会裸用这个版本一般会先做随机pivot或三数取中。我的建议是面试答题用Lomuto代码最不容易错做性能优化想试试Hoare就要耐心处理边界。5.3 快排为什么平均最快、最坏却很惨快排的平均时间复杂度是O(n log n)因为每趟大概率把区间对半分递归深度约log n每层总工作量O(n)。最坏情况下如果每次选的pivot都是最大或最小值一趟只排好一个元素递归深度变成n复杂度掉到O(n²)。避免最坏情况的三个标准手法随机选择pivot每次在[low, high]里随机挑一个下标和arr[low]或arr[high]交换后再分区。这让最坏情况的概率变得极低。三数取中取arr[low]、arr[mid]、arr[high]的中位数当pivot对“已经有序”这种经典退化输入极其有效。小区间切换插入排序当递归区间长度小于某个阈值通常16到32直接调用插入排序。插入排序对接近有序的小数组是O(n)级别组合之后平均性能更好。现在很多成熟排序库的实现其实是“快排堆排插入排序”的混血快排负责正常划分递归深度一旦超过上限就切到堆排兜底小区间交给插入排序收尾。目的只有一个让排序在最坏情况下也不会退化到O(n²)。这是工程和课堂最大的区别。快排不稳定这件事很多人背了答案但说不清原因。看一眼partition过程就明白小于pivot的元素会跨越中间元素被交换到左侧这种跨距离的交换完全可能让两个相等值互换相对位置。所以快排想保持稳定就必须放弃原地分区改用额外空间。那就不叫标准快排了。6. 归并排序稳定的O(n log n)代价是内存换时间6.1 递归分治加上合并两个有序数组归并排序的思路很对称把数组从中间拆成两半分别排好再把两个有序数组合并成一个。递归下去直到区间只剩一个元素。核心代码在merge函数void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; int *L (int *)malloc(n1 * sizeof(int)); int *R (int *)malloc(n2 * sizeof(int)); for (int i 0; i n1; i) L[i] arr[left i]; for (int j 0; j n2; j) R[j] arr[mid 1 j]; int i 0, j 0, k left; while (i n1 j n2) { if (L[i] R[j]) arr[k] L[i]; else arr[k] R[j]; } while (i n1) arr[k] L[i]; while (j n2) arr[k] R[j]; free(L); free(R); } void merge_sort(int arr[], int left, int right) { if (left right) { int mid left (right - left) / 2; merge_sort(arr, left, mid); merge_sort(arr, mid 1, right); merge(arr, left, mid, right); } }两个实现细节值得反复念计算mid用left (right - left) / 2别用(left right) / 2这是防大数溢出的标准安全写法。合并时比较条件写成L[i] R[j]而不是。相等时优先取左边元素这行代码直接决定归并排序稳不稳定。上面为了结构清晰每次递归都临时malloc两块数组。真实工程里请在外层一次性申请一块等长临时数组所有merge复用否则频繁分配内存会拖垮性能。6.2 稳定性为什么是归并的“天赋”归并排序整个过程不破坏稳定性的关键就在merge时相等元素先取左侧。如果某层归并把右侧相等元素先拿过来后续相对顺序就乱了。代码里写死L[i] R[j]就是每一层都执行这个规则。因为每层归并都遵守所以归并排序是天然的稳定排序。对有稳定性需求的场景来说稳定排序是刚需。尤其处理“先按姓名排、再按年龄排”这类多关键字排序归并排序是最稳妥的选择之一。6.3 归并排序的真正舞台链表和外部排序原地数组排序时归并的空间开销O(n)让它显得有些吃亏。但在两类场景里它几乎无可替代外部排序数据量大到内存放不下比如几十个G的日志按时间排序。做法是切文件成多段每段读入内存排好写回磁盘再用多路归并合并。归并排序对磁盘的访问基本是顺序读写这是快排、堆排那种跳跃访问完全无法比拟的。链表排序归并排序只需要顺着链边走天然适合单链表。而且链表归并只用改指针不需要额外的大块内存。快排和堆排都依赖随机访问放到链表上基本没法用。如果面试里被问“哪种排序最适合链表”归并排序是标准答案。7. 计数排序当数据范围很小时干脆不排序7.1 比较排序的下界和“作弊”的思路你可能在课本上见过一个结论基于比较的排序最坏情况下时间复杂度不可能低于O(n log n)。这个结论从决策树来n个元素有n!种可能排列比较排序每做一次比较最多只能排除其中一部分可能性最坏情况下至少要比较约log2(n!)次也就是O(n log n)。但注意这个下界只约束“基于比较”的排序。计数排序根本不比较元素大小它只记录每个值出现了几次再按值从小到大的顺序把次数“摊”回数组。这条路绕开了决策树下界所以能做到O(nk)。计数排序有两个前提元素必须是有限整数范围且这个范围不能太大。时间O(nk)里的k指的就是最大值与最小值的跨度。7.2 C语言完整实现频次统计、前缀和、倒序回填默认元素是非负整数、最大值是k的标准实现void counting_sort(int arr[], int n, int k) { int *count (int *)calloc(k 1, sizeof(int)); int *output (int *)malloc(n * sizeof(int)); 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]; } free(count); free(output); }中间的两个步骤值得展开讲一下第一步统计count[v]表示值v出现了几次。第二步前缀和把count[v]改造成“小于等于v的元素总个数”。改完以后count[v] - 1正好是排序后最后一个等于v的元素应放的下标。比如count[3] 7说明值为3的最大下标是6。第三步倒序回填是为了稳定。从数组末尾往前遍历遇到一个值v就把它放进当前count[v] - 1的位置再把count[v]减一。倒序保证了相同值中后出现的先放到靠后位置先出现的后放但落在更靠前位置最终相对顺序和原数组完全一致。如果不要求稳定正序回填也能得到一个正确的有序数组只是相同值元素的顺序会反过来。所以标准库风格的稳定实现都走倒序。7.3 计数排序的坑负数、偏移和数据范围爆炸写代码最容易踩的坑是元素里有负数直接拿负数当下标必然越界。解决办法是先扫一遍拿到max和min令offset min建长度为max - min 1的计数数组排序时用arr[i] - offset做下标。只是多一层映射思路不变。这也是面试官问“负数怎么办”时的加分回答。更大的坑是k远大于n。比如数据有1万个元素但取值范围是0到10亿count数组要开10亿个int直接内存爆炸。这时计数排序就不适用老老实实回快排或归并。所以我反复强调“数据范围小”这个前提决定计数排序适不适用的是k不是n。范围小、数据量大计数排序是王者范围大、数据量小别碰它。计数排序也是基数排序和桶排序的基础这里不展开先把它当成“按值分类”的鼻祖就好。8. 实战选型面试和工程里到底怎么选8.1 一个排序选型决策思路把前面所有内容压缩成四个问题任何排序选型决策基本都能落地问题一数据量有多大几百个无脑插入排序。几万个插入、希尔都可以。百万级快排、归并、堆排。上亿且内存不够归并的外部排序思路。问题二数据本身有什么特征基本有序插入排序或希尔排序别直接用快排除非做三数取中。关键字范围很小计数排序。大量重复元素普通快排会退化考虑三路快排思想或者走计数、归并路线。问题三稳不稳定重要吗需要稳定归并、插入、冒泡、计数。不需要稳定快排、堆排、选择、希尔。问题四额外空间允许吗内存苛刻、要求最坏情况可控堆排序。内存充足、同时要求稳定归并。完全不能申请额外空间又要平均快快排的原地版本。面试时先反问面试官数据规模、数据特征、稳定性要求、内存限制再决定选哪种。这个思考过程比直接背“用快排”重要得多。很多人上来就说“用快排”但如果场景是“几百个学生按学号排”插入排序可能是更优雅也更简单的答案。8.2 为什么成熟排序库都是“混血”的如果你看过一些成熟排序库的实现会发现它们很少单独用一个算法。常见组合是快排做主体分区递归深度过深切到堆排序规模小于阈值切到插入排序如果数据量特别大或要求稳定又会走归并路线。原因很朴实快排平均最快但怕最坏堆排最坏可控但常数大插入排序在小数据量下常数最小归并稳定但费内存。把它们组合起来正好互相补短板。这种“为最坏情况兜底、为最好情况提速”的设计思路才是排序选型真正的核心。8.3 我用C语言写这些排序时踩过的坑最后分享几个我实际写和讲排序时踩过无数次的坑坑一快排递归深度爆栈。有一次我在批量测试里对100万有序整数跑裸快排程序栈直接就崩了。解决办法就是三数取中或随机pivot或者限制递归深度后切堆排。写代码时总觉得“我不会遇到最坏情况”但测试机器真的会让你遇到。坑二归并排序忘了free。递归里每次malloc两块数组如果某个分支提前返回内存泄漏很难发现。我写教学代码时习惯在merge末尾加free但如果改成复用全局临时数组要特别注意当前归并区间用了哪些位置。坑三计数排序遇到负数直接崩。我见过太多次arr[i]是负数count[arr[i]]直接越界。加一个offset映射只要十几行别嫌麻烦。坑四swap函数的类型陷阱。如果排序的元素不是int而是几十字节的结构体写swap时不能只交换指针。真正通用做法是按元素size用memcpy按字节交换否则交换完等于没换。坑五测稳定性时别只看“结果对不对”。用普通整数数组测稳定性是测不出来的因为相等元素根本看不出谁先谁后。正确做法是构造“关键字段相等、辅助字段递增”的结构体数组排序后检查辅助字段是否仍然递增。我在教这个知识点时经常说一句话排序算法考的不是“会不会背代码”而是“能不能解释为什么”。为什么堆排最坏也能保证O(n log n)为什么快排需要随机化为什么归并愿意花内存换稳定为什么计数排序能突破O(n log n)的界限。这八个算法每一问都是小考题也是你理解数据结构与算法思想的试金石。先把C语言实现一个个跑通再想清楚每个“为什么不这样写”等你真正参加面试或者接手真实项目时会感谢当初这个较真的过程。
