企业官网建设流程全解析

【数据结构】八大排序算法详解（C语言实现）——这种标题我见过太多次了。第一次学数据结构的人，多半以为这门课的任务就是把八个代码背下来；可真到了面试或者真实项目里，面试官一句“这八种排序你选哪种、为什么”，就能筛掉一大半只会背代码的人。

这篇文章我按自己的理解，把插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序这八种算法串成一条线：每个算法先讲直觉，再给C语言实现，然后说清楚复杂度、稳定性和容易踩的坑，最后一章聊真实场景下怎么选型。特别适合正在学数据结构的同学、准备校招面试的工程师，以及想把“背代码”升级成“真理解”的朋友。

1. 打开排序的地图：八种算法各自的定位与分类

1.1 先搞清楚一个基本问题：排序到底在排什么

排序的目标很朴素：给定一个无序序列，按关键字从小到大或从大到小重新排列。在C语言里最直接的表示就是一个int数组，但你不能只把这八种算法当八个模板记，而要看清它们背后的几种“操作思路”：相邻交换、扫描选极值、扑克牌式插入、分组跳步、树形锦标赛、分治快分、分治合并，以及最后那个干脆不比较、只统计频次的家伙。

我习惯把它们分成五条线：

• 插入类：直接插入排序、希尔排序。核心动作是“把一个元素插入到前面已经有序的位置”。
• 交换类：冒泡排序、快速排序。核心动作是“通过交换消除逆序对”。
• 选择类：简单选择排序、堆排序。核心动作是“每趟挑出剩下元素里的最值”。
• 归并类：归并排序。核心动作是“把两个有序段合并成一个”。
• 非比较类：计数排序。核心动作是“统计频率，按坐标放回，根本不比较大小”。

为什么要这样分？因为一旦你确定了算法类别，它的时间复杂度和稳定性就有了大致框架：选择类普遍不稳定，插入类容易做到稳定，交换类里冒泡稳定、快排不稳定。这个分类习惯，比你一个个去背结论要可靠得多。

1.2 一张表看清复杂度、空间和稳定性

下面这张表建议直接收藏，面试前扫一眼非常有帮助：

几个经常有人记错的地方，我直接说透：

• 选择排序的最优时间也是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不断缩小，最后一趟gap=1就是标准插入排序。因为前面几趟已经把序列收拾得接近有序，最后一趟虽然用的是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的节点，左孩子是2i+1，右孩子是2i+2，父节点是(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^(h+1)个，把每层的代价加起来，总和会收敛到一个常数乘以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的元素，就把它放到i+1的位置；扫描完毕，把pivot放到i+1的位置，这个位置就是它的最终位置。

这个写法代码短、不容易错，是我在面试时首选的分区写法。缺点是如果数组里大量元素等于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从high+1开始，do while能保证进入循环后一定自增自减，先动再看。
• 返回的是j，不是pivot的最终位置。递归时左半区间是[low, j]，右半是[j+1, high]。如果照抄Lomuto的[low, pi-1]，会漏元素，甚至死循环。
• 极端输入下，i和j可能出现越界风险，所以工程上几乎不会裸用这个版本，一般会先做随机pivot或三数取中。

我的建议是：面试答题用Lomuto，代码最不容易错；做性能优化想试试Hoare，就要耐心处理边界。

5.3 快排为什么平均最快、最坏却很惨

快排的平均时间复杂度是O(n log n)，因为每趟大概率把区间对半分，递归深度约log n，每层总工作量O(n)。最坏情况下，如果每次选的pivot都是最大或最小值，一趟只排好一个元素，递归深度变成n，复杂度掉到O(n²)。

避免最坏情况的三个标准手法：

1. 随机选择pivot：每次在[low, high]里随机挑一个下标，和arr[low]或arr[high]交换后再分区。这让最坏情况的概率变得极低。
2. 三数取中：取arr[low]、arr[mid]、arr[high]的中位数当pivot，对“已经有序”这种经典退化输入极其有效。
3. 小区间切换插入排序：当递归区间长度小于某个阈值（通常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(n+k)。

计数排序有两个前提：元素必须是有限整数范围，且这个范围不能太大。时间O(n+k)里的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语言实现一个个跑通，再想清楚每个“为什么不这样写”，等你真正参加面试或者接手真实项目时，会感谢当初这个较真的过程。