从最暴力的两两比较到生产环境里用的快排变种再到数据范围有限的计数排序这些年我在C语言项目里把经典排序算法几乎写了个遍。回头看排序不只是面试题和课本知识点它其实是理解递归、指针、复杂度分析这些C语言核心概念的最佳训练场。这篇专题总结一先把排序这块最基础也最重要的内容讲透接下来的系列文章会继续延伸到查找、字符串处理和图论算法。老规矩先说这篇文章适合谁正在学C语言的数据结构课程、准备机试或笔试、或者工作中需要手写排序逻辑的读者都能从中拿到有价值的东西。我会把每种排序的核心思想、C语言实现、复杂度推导和实际使用建议全部过一遍也会穿插一些我在实际调试中踩过的坑。代码统一用C语言写标准是C99可以直接编译运行。1. 排序问题的基础认知先搞清楚我们从哪里出发1.1 排序在C语言编程中的位置排序算法几乎是所有C语言程序员绕不开的第一道坎。它不像指针那样玄乎但比简单的循环和分支要复杂一个层次是很多人从“会写代码”到“理解算法”的分水岭。在嵌入式设备上需要对传感器数据进行排序在通信协议里需要对报文按序号整理在一些基础库中需要对配置表排序——这些都是C语言排序算法的真实用武之地和刷题场景完全不同。从另一个角度说排序算法也是学习算法设计与分析的绝佳载体。它足够简单让你能直观看到某个操作的执行次数它又足够丰富覆盖了暴力枚举、分治、递归、非比较排序等多种设计思想。学会了排序你就掌握了一套通用的算法分析方法论后面再去啃KMP算法、深度优先搜索这些东西都会轻松不少。1.2 评价排序算法时我们到底在看什么很多初学C语言的朋友对排序的理解就是“把数组排成升序”实际上工程上选型要考虑的东西多得多。我在项目里见过因为选错排序算法导致系统延时抖动的案例所以这里把评价指标讲清楚很重要。第一是时间复杂度的平均情况、最好情况和最坏情况。这三个值必须分开看因为有些算法平均表现优秀但碰到特定输入会退化到难以接受的地步。第二是空间复杂度。在单片机这类内存受限的环境中额外开一个等长的辅助数组可能直接把内存打爆这是很现实的问题。第三是稳定性。稳定排序能保持相等元素的原始相对顺序。当你有多个排序字段时这一点极其关键——比如先按姓名排再按成绩排只有稳定排序才能保证成绩相同的同学仍然按照姓名的顺序排列。第四是常数因子。复杂度分析只关注数量级但真实程序中常数因子往往决定了谁更快。快排的平均复杂度是O(n log n)在数据集较小的时候实际运行速度可能还不如一个实现良好的插入排序。1.3 经典排序算法总览在深入每种排序之前先放一张我整理的速查表方便你建立整体框架。这张表来自我结合《算法导论》CLRS和多年C语言实践整理的版本排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性核心思想冒泡排序O(n²)O(n²)O(1)稳定相邻比较交换选择排序O(n²)O(n²)O(1)不稳定找最值交换插入排序O(n²)O(n²)O(1)稳定扑克牌插牌法希尔排序O(n^1.3)O(n²)O(1)不稳定分组插入归并排序O(n log n)O(n log n)O(n)稳定分治合并快速排序O(n log n)O(n²)O(log n)不稳定分治分区计数排序O(nk)O(nk)O(k)稳定非比较计数基数排序O(d(nk))O(d(nk))O(nk)稳定逐位桶排这张表不是让你背的而是让你知道每种算法在什么场景下有优势。接下来逐个拆解。2. 三个O(n²)级别的奠基算法冒泡、选择、插入排序2.1 冒泡排序理解循环嵌套与交换操作的第一步冒泡排序的核心思想非常直观重复遍历数组每次比较相邻的两个元素如果顺序不对就把它们交换就像气泡从水底浮到水面一样每一轮结束后最大的元素会“冒”到数组末尾。我看很多初学者用C语言写冒泡排序时会陷入一个误区把所有比较逻辑堆在同一个双重循环里代码越写越乱。我建议先写清楚单轮冒泡的逻辑再套上外层循环。单轮遍历的目的是把当前范围内最大的元素送到最右边怎么判断是不是最大一个一个比较过去谁大谁往后挪。这个“谁大谁往后挪”就是内层循环要做的事。外层循环控制还需要多少轮因为每一轮已经确定了一个元素的最终位置所以第 i 轮只需要比较前 n-1-i 对元素。一个标准的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 temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped 1; } } if (swapped 0) { break; } } }这里加了一个swapped标志位是实际工程中最常用的优化。如果某一轮遍历过程中一次交换都没发生说明数组已经是有序的可以直接跳出循环。这个优化让冒泡排序在最好情况下的时间复杂度变成O(n)。我第一次在嵌入式项目里用冒泡排序处理几乎有序的状态列表时这个优化直接让函数耗时下降了近一个数量级。冒泡排序是稳定的吗是的。判断条件是arr[j] arr[j1]才交换等于的情况不交换相等元素的相对位置不会被破坏。那冒泡排序实际用得多吗说句实在话除了教学场景我在正式项目中几乎不用它。它的交换次数实在太多了每一轮都要进行大量的相邻交换。但在数据量很小比如少于50个元素且基本有序时它的代码简洁性和O(n)的最好情况表现还是有一定竞争力的。2.2 选择排序把交换次数压到极致选择排序的思路比冒泡更直接每次都从未排序区间中选出最小的元素放到已排序区间的末尾。翻译成人话就是“每次挑一个最小的放到前面”。选择排序最值得称道的一点是交换次数固定为 n-1 次。注意是交换而不是比较比较次数仍然是O(n²)但交换次数很少。如果你处理的数据元素很庞大比如结构体数组每次交换要搬运大量数据这时选择排序的交换次数少就是巨大优势。反过来如果交换代价低而比较代价高比如比较两个大整数选择排序就不如其它算法。下面是C语言实现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 temp arr[i]; arr[i] arr[min_idx]; arr[min_idx] temp; } } }内层循环的核心是更新min_idx也就是记录最小元素的下标。注意这里有个细节min_idx初始化为 i然后从 i1 开始扫描找到比当前最小值还小的就更新下标。扫描完成后如果min_idx ! i才交换否则跳过交换。这个判断是必要的优化避免自己和自己交换。选择排序的不稳定问题值得单独说。举个例子数组为[5, 8, 5, 2]第一轮找到最小值2和第一个位置的5交换变成[2, 8, 5, 5]——两个5的相对顺序被改变了原来的第二个5现在在第三个位置第一个5在第四个位置因此选择排序不稳定。读过CLRS的朋友应该知道算法导论里用循环不变量来证明选择排序的正确性。这个证明思想其实对每个排序算法都适用每一轮循环开始时区间[0, i)已经是最终有序的且其中每个元素都不大于区间[i, n)中的任何元素。这就是选择排序的不变量。理解它你写代码时就不会在边界条件上翻车。2.3 插入排序处理近似有序数据时被低估的利器插入排序的算法思想是扑克牌理牌你摸到一张新牌会从右往左找合适的位置插进去。在数组上怎么实现把数组分成“已排序前缀”和“未排序后缀”每次从未排序部分取第一个元素在已排序部分从后往前找找到比它小的位置把它插进去。我见过很多初学朋友用临时数组来做插入排序这是完全不必要的。原地插入只需要一个临时变量保存当前要插入的值然后利用赋值操作把大于它的元素整体右移一位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; } }从一开始接触插入排序我就被它的简洁震撼了代码量只有五六行但逻辑却非常严密。j 0防止越界arr[j] key是严格的“大于”保证等于 key 的元素不会被移位也就是说插入排序是稳定的。找位置时从右往左找找到第一个不大于 key 的位置后就停然后把 key 放在它后面这样相等元素能够保持原有顺序。插入排序的性能特点值得深入理解。平均和最坏都是O(n²)但它的最好情况是O(n)——当数组已经有序或几乎有序时内层循环几乎不进每个元素直接落在原位。这个特性在真实项目中极其重要。比如有一个按时间排好序的任务列表偶尔需要插入一个新任务插入排序就是最优选择。我自己写日志模块时需要维护一个按优先级排序的缓冲区因为新日志通常接近有序同一个优先级的常连续到来插入排序比快排和归并都快。希尔排序其实就是插入排序的升级版后面会专门讲。所以插入排序千万别觉得只是教学用的“小玩具”它是很多高级算法的基础组件。3. 从O(n²)到O(n log n)希尔排序与归并排序3.1 希尔排序插入排序的“跳步”进阶希尔排序的核心思想是对插入排序的一种补救。插入排序慢就慢在每次只能把元素移动一位如果一个很小的数在数组尾部要让它冒到头部需要整整n次移位太吃亏了。希尔排序的想法是先让元素能“大步跨越”移动最后再变回普通插入排序时数组已经基本有序了插入排序就能发挥它的O(n)最好情况。具体怎么做选一个增量序列比如初始增量为 n/2然后不断减半。每个增量 h 相当于把原数组分成 h 组每组中的元素是相隔 h 的那些位置对每一组做插入排序。最经典的增量序列是希尔增量h n/2, n/4, ..., 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]; int j i; while (j gap arr[j - gap] key) { arr[j] arr[j - gap]; j - gap; } arr[j] key; } } }这个写法是在每个增量下对从 gap 开始的所有元素依次进行跨 gap 的插入排序。看起来和普通插入排序很相似区别是把步长从1换成了gap。我在实际调试中发现初学者最容易搞混的是内层循环的下标关系普通插入排序是arr[j] key时往左一位希尔排序是arr[j-gap] key时往左跳 gap 位同时注意j gap防止 j-gap 取到负数。希尔排序的时间复杂度分析比前几种排序复杂得多它和增量序列的选择强相关。用希尔增量时最坏情况是O(n²)用 Hibbard 增量1, 3, 7, 15, ...可以达到O(n^1.5)现代研究中还有人提出了更优的增量序列。工程上怎么选我的建议是除非你有特殊需求用n/2减半这个简单版本就够用代码改动小、可读性强。在中等规模数据几千到几万个元素上它比插入排序快一个数量级比归并和快排慢一些但差距不会很大。希尔排序是不稳定的因为分组的插入操作会把相等元素的相对顺序打乱。我在项目里用过它来排序几百个配置项这个体量希尔排序的简单性和中等性能非常有吸引力因为它不需要像归并那样O(n)的额外空间。3.2 归并排序理解分治思想的最佳样本归并排序是教科书里第一个真正意义上达到O(n log n)的稳定排序它完美展示了“分治”策略把大问题拆成小问题解决小问题然后合并结果。具体到归并排序就是把数组对半切开递归地把左半部分排好序递归地把右半部分排好序最后把两个有序子数组合并成一个有序数组。合并过程需要额外空间。这是归并排序的硬伤——空间复杂度O(n)在内存紧张的场景不友好。但反过来归并排序有两个独特优势稳定以及最坏情况时间复杂度稳定在O(n log n)不受输入数据分布的影响。快速排序最怕的逆序数据、大量重复元素归并排序完全不怕。核心代码分成两部分合并函数和递归排序函数。void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; int L[n1], R[n2]; 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]; } } 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); }这里有个我在代码评审时常考别人的细节mid的计算为什么要写成left (right - left) / 2而不是(left right) / 2因为当 left 和 right 都很接近 INT_MAX 时两者相加会溢出整数范围。这在真实项目中不是杞人忧天数组或者区间索引很大时完全可能发生。left (right - left) / 2避免了溢出是更安全的写法刷题和面试时这样写也是加分项。合并过程本身有个细节if (L[i] R[j])这行决定了归并排序的稳定性。使用而不是意味着当左右两个子数组遇到相等元素时优先取左边的相等元素的相对顺序得以保留。如果改成相等时会优先取右边的稳定就没了。很多初学者在这里吃过暗亏。我在实际中会怎么选型归并如果数据量大十万级、内存够、要求稳定归并排序是首选。C标准库的qsort实现大多是基于快排的但很多语言的标准库排序反而使用归并或混合排序原因就是稳定性这个特性在面向对象语言里对对象排序特别重要。4. 快排之所以是快排分区思想与工程级优化4.1 快排的主框架与分区函数快速排序的思想同样是分治但它和归并排序完全不同归并是“先递归后排”快排是“先分区后递归”。每一次对区间[low, high]处理时选一个基准元素 pivot把整个区间重排成“左边都小于等于pivot、右边都大于等于pivot”的状态pivot 落到它的最终位置然后递归处理左右两侧。整个过程里最重要、也最考究功底的是分区函数 partition。经典做法是 Lomuto 分区和 Hoare 分区两种。Lomuto 分区代码简单但常数较大Hoare 分区是快排作者本人的原始设计更高效但边界条件更容易搞错。我给的入门版是 Lomuto因为逻辑清晰、不容易错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; 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(arr, low, high); quick_sort(arr, low, pi - 1); quick_sort(arr, pi 1, high); } }我详细讲一下partition的执行过程因为很多初学者看了好几遍代码还是不懂“为什么这样就分好了”。这里用变量 i 指向“最后一个被确认小于 pivot 的元素”它初始化为 low-1也就是还没找到任何小于 pivot 的元素。变量 j 从 low 开始往 high-1 扫每扫到一个小于 pivot 的元素就把 i 前移一位然后把 arr[i] 和 arr[j] 交换。这相当于把“已知小于 pivot 的元素”在数组前端排好队。循环结束后arr[high] 还站在原地它是 pivot此时 arr[i1] 以及它左边的所有元素都小于 pivot它右边的元素都大于等于 pivot所以最后把 arr[i1] 和 pivot 交换就完成了分区。用 Lomuto 分区实现快排在工程上会导致一个明显的问题如果数组里有很多重复元素比如全是一样的数字每次 partition 会得到一个极度不平衡的切分递归深度变成n时间复杂度退化到O(n²)。这个场景在真实数据里太常见了——状态码、类别编号、枚举值全是重复数据。要应对这种情况就要用三路分区后面细讲。4.2 快排的三大优化三数取中、小数组切换、三路分区真正在工程上落地的快排远不止上面那几行。C标准库的qsort经过了几十年的反复打磨用了数量可观的优化手段。这里我把最核心的三个讲透。第一是三数取中。快排最怕的问题之一定义在“每次选到的 pivot 都是当前区间的最小值或最大值”这种情况会让递归退化成n层。解决办法是选 pivot 时不盲选末尾或开头而是取区间左端、中间、右端三个位置的中位数作为 pivot。中位数能避免一部分极端情况比如已经排序好的数组用三数取中后选到的正好是中间值性能最佳。第二是小数组切换。这在数据量小时特别重要。快排递归到子区间只有十几二十个元素时继续递归的开销已经超过了插入排序的常数开销。此时改用插入排序直接收尾。很多实现在high - low小于某个阈值比如10或20时改用插入排序整体的常数因子明显下降。C标准库的排序实现普遍使用了这个技巧。第三是三路分区。针对大量重复元素的问题三路分区把数组分成 pivot、 pivot、 pivot三部分。递归时只处理小于和大于两部分等于 pivot 的部分直接跳过既不参与递归排序也不会导致分区不平衡。荷兰国旗问题的解法就是这个思想。我来写一个三路分区的快排实现void quick_sort_3way(int arr[], int low, int high) { if (low high) return; int pivot arr[low]; int lt low; int gt high; int i low 1; while (i gt) { if (arr[i] pivot) { swap(arr[lt], arr[i]); } else if (arr[i] pivot) { swap(arr[gt--], arr[i]); } else { i; } } quick_sort_3way(arr, low, lt - 1); quick_sort_3way(arr, gt 1, high); }这三个变量的含义需要仔细体会lt指向等于pivot区的第一个元素gt指向等于pivot区的最后一个元素i是正在扫描的位置。遇到小于pivot的元素把它换到前面去同时lt和i都前进遇到大于pivot的换到后面gt后退但i不动——因为换过来的元素还没检查过遇到等于pivot的直接i前进。这个写法把“等于pivot的元素留在中间”这个目标落实得清晰干净。工程上对存在大量重复键值的数据做排序三路快排在实测中的数据甚至优于普通快排一个数量级。快排的平均时间复杂度O(n log n)、空间复杂度O(log n)递归栈深度。最坏情况是O(n²)但使用了三数取中后最坏情况在实际输入中几乎不可能出现。它是工程上默认的排序选择qsort在大多数平台上的底层就是快排。5. 跳出比较的框架计数排序、桶排序与基数排序5.1 计数排序用空间换时间的典型前面讲的所有排序都是基于比较的排序任何比较排序在最坏情况下时间复杂度不可能低于O(n log n)。这有严格的信息论证明n个元素的排列有n!种每次比较最多排除一半情况要想区分所有排列至少需要 log₂(n!) O(n log n) 次比较。但计数排序不走比较这条路。它的思路是如果我知道每个元素出现的次数就能直接计算出每个元素排序后的位置。适用条件是数据范围有限且数据是非负整数。核心步骤有三步统计每个值的出现次数把次数累加得到“小于等于当前值”的元素数量根据累加结果从后往前填充输出数组。void counting_sort(int arr[], int n, int k) { int count[k 1]; int output[n]; memset(count, 0, sizeof(count)); 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]; } }为什么最后一个循环要从 n-1 往前遍历这是为了保持稳定性。假设数组中有两个值相同的元素从后往前填充时后出现的那个会首先被放到输出数组靠后的位置先出现的随后被放到它前面相对顺序保持不变。如果用memset注意头文件是string.h数组的 k 边界要确定好count的大小必须能覆盖所有可能的值。我在嵌入式设备上处理ADC采集数据时用过计数排序采样值范围0到4095一共十几个样本计数排序轻松搞定甚至不需要额外的比较逻辑。它的时间复杂度是O(nk)k是数据范围。如果k远大于n效果反而比比较排序还差——所以用之前先评估数据范围。5.2 桶排序把数据分到多个“小桶”里各自排序桶排序是计数排序往更通用方向的推广。计数排序的思路是每个值一个桶桶排序允许一个桶里装多个元素桶内可以再用任何排序方法通常用插入排序或快排。适用场景浮点数均匀分布时非常合适。比如要在0到1之间均匀分布的浮点数排序可以分成n个桶每个元素按值放进对应的桶每个桶内的元素量很少排序代价很低。实现的关键点是确定“元素应该进哪个桶”的映射函数。以范围[0, 1)的浮点数为例子桶下标就是arr[i] * n取整。更通用的场景如果知道数据的最大值 max 和最小值 min可以设计公式index (arr[i] - min) / (max - min) * (bucket_count - 1)。#define BUCKET_COUNT 10 void bucket_sort(float arr[], int n) { Node *buckets[BUCKET_COUNT] {0}; for (int i 0; i n; i) { int idx (int)(arr[i] * BUCKET_COUNT); insert_sorted(buckets[idx], arr[i]); } int pos 0; for (int i 0; i BUCKET_COUNT; i) { Node *cur buckets[i]; while (cur) { arr[pos] cur-value; cur cur-next; } } }这个实现里insert_sorted是在链表中做插入排序。理论上桶内排序可以用任意算法链表的好处是插入方便。但要注意动态内存使用嵌入式环境建议预先分配节点池。桶排序平均时间复杂度O(n)最坏情况所有元素落进同一个桶就退化到O(n²)。它的稳定性取决于桶内排序算法是否稳定比如桶内用插入排序就是稳定的。5.3 基数排序逐位入桶的另类思路基数排序的核心思想是把整数按位拆开从最低位到最高位逐位排序。每轮排序使用稳定排序通常用计数排序按当前位的值排一次经过 d 轮后d是数字的位数整体有序。为什么每轮需要稳定排序因为高位的优先级高于低位。如果先按低位排好再按高位排时用稳定排序那么高位相同的元素之间低位的相对顺序会保留——最终结果就是“先高位、再低位”的整体有序。void radix_sort(int arr[], int n) { int max find_max(arr, n); for (int exp 1; max / exp 0; exp * 10) { counting_sort_by_digit(arr, n, exp); } }counting_sort_by_digit就是用计数排序的方式按每一位进行排序。基数排序的时间复杂度O(d(nk))d和k通常很小实际效果可以逼近线性。它实现起来比快排复杂但好处是稳定且最坏情况也是O(n log n)级别的。处理大整数、字符串排序时非常有用——字符串排序的经典实现之一就是基数排序的变种按字符逐位排序。这也是热词里“字符串排序”在工程上和基数排序产生关联的原因。不过要提醒的是负数情况需要额外处理。标准基数排序只支持非负整数有负数时可以把所有数偏移到非负区间或者单独对负数部分加符号位处理。我在实际工程中会先检查数据分布再决定要不要用基数排序因为它的实现复杂度比快排高得多不是常规场景的首选。6. 用C语言手写排序时最容易踩的坑从实战中捞出来的经验6.1 交换函数的两种写法与性能陷阱排序算法的核心操作是交换很多刚写C语言的朋友会在交换函数上踩坑。最容易犯的错误是忘了指针传参写成下面这种void swap_bad(int a, int b) { int temp a; a b; b temp; }调用后外面的值根本没变因为C语言默认值传递a和b是实参的副本。正确写法是传地址void swap(int *a, int *b) { int temp *a; *a *b; *b temp; }还有不少人喜欢用异或实现交换号称省内存void swap_xor(int *a, int *b) { *a *a ^ *b; *b *a ^ *b; *a *a ^ *b; }这个写法在绝大多数情况下能用但有一个致命陷阱如果a和b指向同一个地址第一步执行后*a变成0整个交换就失败了。这在排序中确实可能发生比如选择排序的if (min_idx ! i)就是防止这种自我交换但写通用交换函数时你无法保证调用者永远不传同一个地址。我的建议是永远用临时变量法现代编译器对简单交换的优化已经非常到位了异或交换节省的那点内存微乎其微维护成本却高出一截。6.2 数组作为参数传递时的退化陷阱C语言里数组传给函数时会退化成指针所以函数内部无法用sizeof(arr) / sizeof(arr[0])计算元素个数。很多初学者把“计算数组长度”写在排序函数内部结果得到的是指针大小除以元素大小完全错误。正确的做法是一开始就在 main 函数里用sizeof算出长度然后把长度作为参数传给排序函数。int arr[] {3, 5, 1, 2, 4}; int n sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, n);另一个相关的坑是二维数组排序。如果要对矩阵按某一行或某一列排序直接用 qsort 配合合适的比较函数要比手写快排简单得多但比较函数的写法要注意int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }这段代码有个隐藏问题当两个 int 的差值可能超过 int 范围比如一正一负两个极端值时会溢出。更安全的写法是int cmp(const void *a, const void *b) { int x *(const int *)a; int y *(const int *)b; return (x y) - (x y); }这个写法通过两个比较的差值返回 -1、0 或 1彻底避免溢出问题。我在实际项目中见过因为前者溢出导致排序结果莫名其妙的案例所以这里专门提一句。6.3 边界条件空数组、只有一个元素、指针为空排序函数最容易崩的地方是空数组和指针为空。如果你写的排序函数被其他模块调用就必须处理arr NULL或n 1的情况。最稳妥的方式是在排序函数入口加保护判断if (arr NULL || n 1) { return; }加了这个保护调用方传什么都不会崩。这看起来很小但在项目里是维护性的关键——排序函数一旦被多个模块调用谁也不能保证传进来的数组一定合法。递归排序归并、快排还有一个问题就是递归深度。如果对几十万甚至上百万个元素的数组用普通递归快排栈空间可能不够。解决方案之一是定义递归深度上限超过阈值改用非递归方式或堆排序。C标准库的qsort之所以不是纯递归快排部分原因就在这里。我建议在真实项目中如果数据规模百万级别优先考虑qsort或者把快排改成迭代式它的空间复杂度O(log n)意味着递归栈不会太深但足够大的数据也可能触到栈限制。6.4 用qsort时要格外注意比较函数的返回值qsort的坑还有一点比较函数返回值的定死规范。C标准要求比较函数返回一个负整数、零或正整数表示第一个参数小于、等于或大于第二个参数。千万不要认为只能返回1或-1有些实现会依赖返回值的符号正负来判断而不是严格等于某个值。还有一个容易踩的点qsort 的稳定性不保证。标准库文档明确说明排序结果可能不稳定。如果你的业务依赖稳定性不要用 qsort老老实实写归并排序。我在一个成绩排序需求里就吃过这个亏——学生先按姓名排好序再按成绩用 qsort 排结果相同成绩的学生姓名顺序被打乱了后来改用自己实现的归并才解决。7. 排序算法怎么选一张实践路线图讲了这么多排序的实现细节最后从实践角度给一条清晰的选择路径。这也是我最常被问的问题什么时候用哪个排序如果数据规模小于50我的建议是直接插入排序。代码短、稳定、写起来几乎不可能出错。如果正好碰上近似有序的数据插入排序的表现优于所有高级排序。如果数据规模几千到几万需求又强调稳定归并排序。如果数据量很大没有稳定性要求又能接受最坏情况退化的小概率风险快排加上三数取中优化。如果数据范围特别有限比如取值只有几百个不同的非负整数计数排序能让你体验到线性的快感。这种情况下哪怕数据规模十万、百万计数排序都是碾压级别的存在。如果处理的是长整数或定长字符串基数排序值得一试。比如按学号字符串排序基数排序按字符逐位处理效果稳定且可控。最后再强调一句稳定性。我在真实项目中用稳定排序的次数远多于不稳定排序数据库索引排序、排行榜并列名次处理、先按A字段再按B字段排序——这些需求都要求稳定。所以我在团队里总是说如果拿不准排序选什么归并是个兜底的安全选项它稳定的同时复杂度可达上限只是额外占用一段内存换来这个品质。回到C语言本身排序算法不仅仅是“让数组变有序”的工具它训练的核心能力是“控制程序的执行过程”和“预判该操作的代价”。理解了排序你再看KMP算法的前缀函数再看深度优先搜索的递归回溯就会觉得这些经典算法其实都是同一个思路——把一个明确的大问题拆成步骤清晰、可验证的小操作。这也是我这一系列专题想要传达的东西。下篇我会继续总结哈希查找和二分查找在实际工程里的应用和细节到时可以延续这边的代码风格继续往下聊。