如果你在学校里学过C语言十有八九在某个实验课上写过冒泡排序如果你去面试十有八九又被问过快排和归并。排序就是这么一门“又基础又高级”的算法分支——它不会直接帮你做业务但几乎所有复杂系统的性能瓶颈、数据组织、推荐排序、索引构建里都有排序算法在底层默默打工。这个专题我打算分几篇来讲开篇就拿排序下手用纯C语言把冒泡、选择、插入、快排、归并、堆排这些主流算法逐个抠一遍顺便把工程里真正会碰到的qsort、结构体排序、字符串排序一起收进来。这篇内容适合谁刚学完C语言基础、准备啃算法和数据结构的人或者正在刷OJ题目、准备面试算法题的人都可以直接对照着看。我尽量把每个排序的“为什么这么写”“哪里容易错”“什么场景才用它”说透。毕竟光背代码没有意义能根据数据规模、稳定性要求、内存限制选出合适的排序算法才是真正值钱的能力。1. 排序到底在排什么1.1 排序问题的本质与两个衡量维度排序问题的定义很简单给定一个包含n个元素的序列按照某个确定的比较规则把这个序列重新排列成有序状态。输入可以是一个整型数组、一个字符串数组、一个结构体数组甚至是一堆对象的指针输出必须满足两个条件一是元素之间的相对大小关系和比较规则一致二是所有元素都要出现在结果中数量不多不少。但真正到写代码的时候要衡量的维度就多了。最重要的两个是时间复杂度和空间复杂度在这两个之外还有一个在考试里容易被忽略、在工程里却极其关键的属性——稳定性。稳定性指的是如果两个元素在比较规则下“相等”排序后它们原来的相对顺序能否保持。能保持的叫稳定排序不能保持的叫不稳定排序。冒泡、插入、归并是稳定的选择、快排、堆排在经典实现里通常不稳定计数、基数这些分布类排序天然稳定。为什么稳定性这么重要举个最直观的场景一个销售报表先按销售额排序再按地区排序如果排序算法不稳定第二次排序会把第一次的排序结果彻底打乱地区相同的数据销售额顺序可能乱掉。这就是我在之前的工程里踩过的坑——数据先按时间排序再按用户分组排序结果用了不稳定的排序分组内时间顺序全乱了。所以别小看稳定性它决定了一个排序算法能不能用于多级排序场景。1.2 算法家族全景与选型思路排序算法按实现思路大致可以分成几类交换排序冒泡、快速、插入排序直接插入、希尔、选择排序简单选择、堆、归并排序、分布类排序计数、基数、桶。其中冒泡、选择、插入是O(n²)级别的基础算法适合理解过程和应对小规模数据快排、归并、堆排是O(n log n)级别的高级算法是工程和面试的常客计数、基数这类非比较排序只在特定数据范围内才有优势。选型没有绝对标准我用下来有几个经验。数据量很小时比如几十个元素插入排序反而是最快的因为它常驻常数极小数据量中等且随机分布时快排通常胜出数据是链表、或者要求稳定就优先归并内存空间非常紧张时可以考虑堆排序或者原地快排数据值域较窄且是整数时计数排序可以做到O(n)级别这也是我在刷题时常用的“降维打击”手段。提示不要崇拜某个算法本身要看它运行在什么数据上。很多人学完排序只记得快排最快却不知道快排在近乎有序的数据上可能退化到O(n²)。选型之前先想清楚数据的规模、有序性、稳定性和内存这四个问题。2. 基础排序冒泡、选择、插入2.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标记这是冒泡排序最常见的优化某一轮扫描完全没有发生交换就说明序列已经有序可以直接退出。这个优化对“近乎有序”的数据非常管用最好情况下能降到O(n)复杂度。很多人写冒泡会忽略这个优化我建议无论如何都要写上因为这是面试官很爱问的“如何优化冒泡排序”的答案。冒泡排序实测下来效率确实一般我不推荐在真实场景中用但它有两个无法替代的价值一是逻辑最简单适合初学者理解循环嵌套和交换操作二是稳定且实现短。如果你给别人讲算法、做课程设计演示用一个冒泡排序是最容易讲明白的。另外务必注意内层循环j的范围是n - 1 - i因为每一轮末尾已经排好一个元素不需要再碰它。我曾经在考试现场把范围写成n - 1结果每轮都把排好的末尾元素重新比较多写了不少循环。2.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[i]; arr[i] arr[min_idx]; arr[min_idx] tmp; } } }这里我想多说一点循环不变量的事情。我在看CLRS的时候对选择排序的循环不变量印象很深表述大概是在第i轮循环开始前区间[0, i-1]已经是最小的i个元素且有序区间[i, n-1]是剩余元素。每一轮迭代从剩余区间中选出最小元素放到位置i并恢复这个不变量。循环不变量听起来玄乎其实就是“这个循环凭什么能保证算法正确”的逻辑依据。写算法题的时候能想到这一步你就不是背代码而是真正在构造一个可靠的过程。选择排序的特点是交换次数非常少每轮最多一次交换总共最多n-1次这在交换代价极高比如元素是很大的结构体或写回磁盘时有优势。但它不稳定因为跳跃交换可能把相同值的相对顺序打乱。它也不具备自适应性无论原数据是否有序都必须完整执行n(n-1)/2次比较。所以选择排序适合的是“数据量小、元素很大、不要求稳定”的场景其他情况基本用不上。2.3 插入排序手牌整理法与小规模数据利器插入排序的思路和玩扑克牌时整理手牌一模一样从第二张牌开始依次把每张牌插到前面已经排好序的牌堆里正确的位置。实现上取出当前元素arr[i]向前扫描已排序区间把比它大的元素依次后移直到找到它的位置。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; } }为什么说它是“手牌整理法”因为对现实中理扑克牌的人而言这种局部插入操作是最自然的动作。数据量小的时候人脑比不上机器但这个算法本身的常数因子极小循环体非常精简几乎没有额外的空间开销。实测在小数组比如n小于15上插入排序往往比快排还快。这也是为什么很多高效的排序库会在递归到小区间时改用插入排序收尾而不是一直递归到单个元素。插入排序是稳定的而且对“近乎有序”的数据有极佳的自适应性——扫描一遍就能确定大部分元素已经在合适位置移动很少。我在做OJ题目时经常遇到“长序列已基本有序只有几个元素乱序”的场景这种数据用插入排序会非常快。要注意的是内层循环条件j 0必须写在arr[j] key前面否则j变成-1再访问arr[-1]就会发生数组越界。这个顺序错误是新手最容易犯的。3. 进阶排序快排、归并、堆排3.1 快速排序的工程化实现与退化治理快排是分治思想的代表从数组中选一个基准值pivot把数组划分成小于pivot和大于等于pivot的两部分然后递归地对两部分排序。关键是划分函数partition。我常用的是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; 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) { int pi partition(arr, low, high); quick_sort(arr, low, pi - 1); quick_sort(arr, pi 1, high); } }Lomuto的实现逻辑是把比pivot小的元素不断“挪”到前面最后把pivot放到正确位置返回它的下标。这种写法代码短便于记忆但常数因子偏大。Hoare划分用两个指针从两端向中间扫描交换左右逆序对实现的比较次数少实际效率更高但边界判断要仔细。我个人刷题时更常用Hoare但入门阶段用Lomuto比较不容易写错。快排最怕的是什么基准值选得不好。如果每次选的pivot恰好是最大或最小值划分就极其不均衡递归深度会退化成n时间复杂度崩到O(n²)。治理方案有三种一是随机选pivot让退化变成概率性事件二是三数取中法取左、中、右三个位置的中位数作为pivot对近似有序的数据很有效三是在递归进入小区间时切换插入排序避免递归层数过深。我在工程里偷懒时直接用随机pivot就够用了。注意快速排序是不稳定的。Lomuto划分过程中pivot会和一个元素交换这个跳跃操作会破坏相等元素的相对顺序。如果题目明确要求稳定排序直接用归并。3.2 归并排序稳定的分治叙事归并排序也是分治思路但它稳就稳在合并过程。它把数组从中间分成两半分别排好序再把两个有序数组合并成一个有序数组。合并时逐位比较两个子数组的头部元素依次取出较小的放进临时数组。这个过程中只要在“两数相等时先取左半部分的元素”就能保证稳定性。void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1, 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) { int mid left (right - left) / 2; merge_sort(arr, left, mid); merge_sort(arr, mid 1, right); merge(arr, left, mid, right); } }我重点说一下合并过程中的一个细节L[i] R[j]这里用小于等于而不是小于这是稳定性的关键。如果L[i]等于R[j]先取左侧的L[i]左侧元素在原始数组中的位置本来就更靠前取出来后它们的相对顺序就保住了。有些教材写成L[i] R[j]等值的时候把右侧的R[j]取出相等元素的顺序就被翻转了。这个差别在面试现场手写归并时特别容易被遗漏。归并排序的时间复杂度稳稳的是O(n log n)但它需要额外的O(n)辅助空间来存储临时数组。我在用递归版本时这样写有一个明显的性能问题每次递归调用都在函数内部定义临时的L和R数组频繁分配和释放内存。工程里更稳妥的做法是“申请一个全局临时数组再把归并过程写成从全局临时数组拷贝回来”这样能把常数优化不少。另外归并排序还是外部排序的基础——当数据大到内存装不下时需要先分块排好再多路归并这本质上还是归并的思路。3.3 堆排序先建堆再滚动取出最大值堆排序利用堆这种数据结构先把数组调整成一个大顶堆父节点大于等于子节点此时堆顶是整个数组的最大值然后把堆顶元素和末尾元素交换将新堆顶下沉调整再取出新的最大值。反复执行n-1次数组就从小到大排好了。核心操作是“下沉”调整也就是max-heapifyvoid heapify(int arr[], int n, int i) { 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) { 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); } }第一个循环从最后一个非叶子节点开始往前建堆原因是堆调整依赖子树已经满足堆的性质从下往上调整才能保证整体正确。第二个循环每轮把堆顶最大值“交换到末尾”再对缩小的堆做下沉调整i既是待排序堆的大小也是末尾下标。很多人会在这里搞混注意看交换完成后数组末尾是已经确定的较大值下一次调整的范围就要去掉它所以heapify的第二个参数传的是i而不是n。堆排序的优点是空间复杂度为O(1)完全在数组内部操作适合内存极度受限的环境时间复杂度稳定在O(n log n)不存在快排那样依赖pivot选择的问题。但实测下来它的常数因子比快排、归并都大因为每次下沉调整都是跳跃式访问数组元素对CPU缓存不友好所以在通用排序库里很少用它。它真正的用武之地是“优先队列”“Top K问题”——需要不断取最大值但又不必完全排序的场景这时候堆几乎是唯一解。4. 工程实战C库函数、结构体与字符串排序4.1 qsort回调函数与万能排序C语言标准库自带的qsort函数底层实现通常是快速排序它最大的特点是“万能”——传入数组基地址、元素个数、元素大小和比较函数指针就能排任意类型的数据。这个设计其实是在教你一个很重要的工程思想算法与比较规则分离核心排序逻辑只依赖一个可替换的比较函数。int cmp_int(const void *a, const void *b) { int ia *(const int *)a; int ib *(const int *)b; return (ia ib) - (ia ib); } // 调用示例 int arr[] {5, 2, 9, 1, 7, 3}; qsort(arr, 6, sizeof(int), cmp_int);写比较函数时注意几点第一参数必须是const void *使用前强制转成具体类型再解引用第二返回值要求是负数、零、正数分别表示a小于、等于、大于b。我习惯写成(ia ib) - (ia ib)而不是ia - ib是因为后者在极端数值下可能溢出比如ia是INT_MAX、ib是INT_MIN时差值会超出int范围产生未定义行为。提示如果你想得到降序把比较函数里的a、b顺序反过来即可不需要改写排序主体。这也是qsort设计得最巧妙的地方——排序规则完全由比较函数决定。为什么我会在实际工程里优先用qsort而不是自己手写快排因为标准库的实现经过充分压测和优化往往包含三数取中、小区间插入排序等策略边界处理也比大多数人手写的版本可靠。自己实现的排序即使测试了一百个随机用例也可能在某些边界数据上翻车。但qsort也有一个问题它不是稳定排序。如果你要稳定排序要么让比较函数附带原始下标把下标作为第二关键字比较要么改用归并实现。4.2 结构体排序与稳定性陷阱工程里最常遇到的是对结构体排序比如学生成绩表、订单记录、排行榜条目。场景往往是“先按主字段排序再按次字段排序”。比如一个排行榜需要按积分降序排列积分相同的人再按注册时间升序排列。这时比较函数的写法就成了关键。typedef struct { char name[32]; int score; int register_time; } Player; int cmp_player(const void *a, const void *b) { const Player *pa (const Player *)a; const Player *pb (const Player *)b; if (pa-score ! pb-score) { return pb-score - pa-score; // 积分降序 } return pa-register_time - pb-register_time; // 时间升序 }我在实际写这类代码时会对上面样例提一个优化建议把pb-score - pa-score改成返回三态比较避免溢出风险。结构体字段可能就是int两个极端值相减确实可能溢出。更好的写法是return (pa-score pb-score) ? 1 : (pa-score pb-score) ? -1 : 0;。虽然啰嗦一点但在数据边界上绝对安全。结构体排序还有一个常见的稳定性大坑很多人在做“点击表头排序”的功能时连续点击两次表头期望第一次按A字段排序的结果能在第二次按B字段排序时保留下来。如果底层用的是不稳定的排序第二次排序后A字段相同的数据顺序会被打乱。解决方案我知道的有两种一是将前一次排序的字段作为比较函数的第二关键字二是用一个额外的序号字段作为最终兜底键。第二种方案实现最简单也是我实际采用最多的方案。字符串数组排序也是高频需求。C语言里字符串是字符数组比较需要strcmp。用它作为比较函数就能让qsort“天然”支持字符串排序因为strcmp的返回值和qsort要求的“负数、零、正数”完全一致。int cmp_string(const void *a, const void *b) { char *const *sa a; char *const *sb b; return strcmp(*sa, *sb); }这里我踩过一个坑qsort的每个元素是char *比较函数拿到的指针是指向char *的指针也就是char **。第一次写的时候我只做了一次解引用传的是字符串首地址而不是指针的指针结果qsort在比较时访问了错误的内存程序直接段错误。所以写字符串比较函数时一定要做两次解引用先取出字符串指针再把指针交给strcmp。如果有逆序需求把strcmp的参数对调一下即可。另外字符串排序的边界问题也很多比如空字符串、大小写混排、中文字节序等处理时要提前定义清楚比较规则。5. 调试经验与自测清单5.1 边界条件与指针操作的典型翻车现场我在讲排序代码时经常强调数组越界和空指针是C语言排序最常见的崩溃原因。空数组和单元素数组虽然逻辑上根本不进入循环但很多人在递归或迭代时忘了对n等于0的情况做专门判断。快排、归并这类递归函数如果high小于low还不返回就会一直递归到栈溢出。所以我写排序函数有一个习惯在入口处先处理n 2的直接返回这比在递归里反复判断要稳妥得多。指针交换也是一个经典问题。写swap时我见过不少同学这么写void swap(int *a, int *b) { int *tmp a; a b; b tmp; }这个写法是完全错误的。它只是交换了形参指针本身的值实参指向的数据一点没动。正确的交换必须解引用交换目标地址里的值int tmp *a; *a *b; *b tmp;。这个看似不起眼的错误在排序代码里出现频率极高因为大家在主函数里传的是arr[i]和arr[j]看起来好像没问题实际却什么效果都没有数组纹丝不动。另外任何比较操作都要关注类型和越界。比如我在上文的样例里写arr[j] arr[j1]如果arr是unsigned int类型而你要比较的是两个无符号数负数的概念就消失了排序结果可能会出乎意料。对字符串数组而言更要小心字符串指针本身为NULL的情况这类问题在线上处理用户数据时偶有发生测试用例很难覆盖到。5.2 用数据构造和gdb验证排序正确性写排序算法最忌讳只测一个正向用例就跑。我个人的自测流程分四步构造边界数据空、单元素、两个元素、构造随机数据、构造特殊数据完全升序、完全降序、全部相等、几乎有序、构造大数据做压力测试。每轮测完必须验证结果严格有序并且元素集合和原数组完全一致。最快的验证方法是在排序前复制一份原数组排序后用memcmp验证有序性再用元素计数验证没有丢失和新增。调试时gdb是很好的帮手。我常用break在排序入口和关键交换处下断点用print arr[i]查看当前元素用watch监控某个变量是否发生了意外变化用backtrace查看递归调用的栈帧。有一次我写归并排序出现段错误就是利用gdb的backtrace定位到merge函数里下标越界的位置。有人说用printf打印全过程也一样但我在处理几万条数据时printf刷屏会把现场淹没gdb可以精准停在你关心的那一次迭代上效率高得多。注意写测试用例时别忘了一个容易被忽视的数据类型——“全部相等”。所有比较都返回0时排序应当什么都不做数组原样返回。如果这时候出现死循环或越界说明算法的边界处理有问题。这个用例成本极低却非常能暴露问题。反复用同一组随机数据测试意义不大我建议构造一个有序数组把随机一个元素改大或改小再排序这样的“近似有序”数据最能考验排序算法是否有优化的空间也能看出你写的排序是不是稳定。5.3 练习建议从教材题目到OJ实战学排序不能停留在“看懂代码”必须动手写而且要多场景练。我个人推荐三个练习方向。第一是教材和课程配套练习翁恺老师的C语言练习题、CLRS书后的思考题都很适合特别是CLRS里对插入排序、归并排序、快速排序的循环不变量证明题目能帮你把算法从“背代码”提升到“理解逻辑”的层面。第二是OJ题目PAT乙级里不少题会直接用排序或者间接依赖排序比如按成绩排名、按时间戳排序等刷这些题能让你在限时环境里写出更稳的代码。第三是自己给自己出题比如写一个对结构体数组的稳定排序或者从大量整数中找出最小的K个数用堆排序和快速选择各写一遍对比性能。练习的时候我会要求自己做到三件事不看书能默写所有排序的完整代码能说清楚每个排序在什么数据上表现好、什么数据上表现差能实现至少两种以上排序并用qsort验证正确性。只有达到这个程度才算真正掌握。很多人说排序很简单但我面试过不少人能一次性把快排partition写对、把归并合并逻辑里的稳定性写对的其实不超过一半。这就是差距所在。实践出真知。我当年在实验室里手动把100个随机数用插入排序一步步排出来排到一半就明白为什么“后移”操作比“交换”操作效率更高了。这个专题让我印象最深的一课是不要觉得排序“写完了就完了”。写完那六种排序后我花了一整天给它们分别喂“升序、降序、重复、随机、近似有序”五组数据发现每种排序都有一两个在特定数据下表现异常。好算法不是单看复杂度的而是看它在真实数据分布下的综合表现。下一期我打算接着整理查找算法和字符串相关的专题排序这个基础打牢了后面很多内容都会顺很多。