简介这是一份面向数据结构与算法初学者、以及需要备考或复习排序知识的C语言学习者的完整示例代码包。资源在VS2010下实现并整理了十类常见排序算法包括冒泡、快速、直接插入、Shell、直接选择、堆排序、归并排序递归与非递归、桶式排序、基数排序顺序与静态队列两种方式以及基于简单插入排序的索引排序基本覆盖了经典排序体系。压缩包共11个文件大小约618KB核心为2个C源文件与1个头文件同时附带VS工程配置.sln、.vcxproj、.filters、.user、编译缓存.sdf、.ipch、.suo以及README说明便于直接打开工程查看和运行。已有717人浏览学习适合正在学习排序算法原理、希望对照完整可运行代码加深理解的读者。通过阅读源码结构和运行示例可以快速掌握各排序算法的C语言写法、边界处理与复杂度表现也可作为课程设计或面试复习的参考。1. 常见排序算法-C语言先想清楚要排什么再选算法“排序算法”和“C语言”这两个词在中文技术圈里经常一起出现但大多数讨论停留在“背出冒泡、快排、归并的时间复杂度”这一步。实际写 C 语言时处境不太一样嵌入式设备上内存只有几十 KB不能用归并排序的临时数组一个保存用户成绩的结构体数组可能达到几十万条qsort 直接排序结构体会产生大量内存拷贝面试时手写快速排序又可能因为边界条件多写一个 off-by-one 被考官追问。在这篇文章里我会按“选型判断、代码实现、工程落地”的顺序把常见排序算法的 C 语言实现讲透包含可以直接编译运行的代码、复杂度对比表以及编译器和 sanitizer 能帮你抓到的边界错误。适合准备 C 语言笔试面试、正在做嵌入式或服务端底层模块的开发者阅读。读完你至少能回答为什么 qsort 不稳定、为什么快排要用三数取中、以及稳定排序到底该自己写还是调库。2. 排序算法 C 语言实现之前稳定性、比较器和内存账2.1 稳定性不是面试名词多字段排序里的实际工程需求稳定排序的定义是两个键值相等的元素在排序前后相对位置不变。C 语言里这个特性经常被忽略因为 qsort 很强大但 C 标准从未承诺它稳定。看一个实际场景有一个 Student 数组每条记录包含班级和姓名你想得到“按班级分组班级内部按姓名排序”的结果。正确做法是先按姓名做一次稳定排序再按班级做一次稳定排序第二次排序不会打乱同班级内部的姓名顺序。如果第二次用的是不稳定排序班级相同的学生顺序会被重新打乱结果就错了。反过来如果数据本身带了自增 id而且你最终只按一个键输出稳定性其实无关紧要。提示在不稳定的排序算法里可以通过“比较器最后一键比较 id 序号”手工让排序结果变成稳定代价是每个元素额外存一个序号和一次额外的整数比较。C 语言里没有语言级的稳定排序函数glibc 的 qsort 在不同版本和条件下可能用归并也可能用快排所以“依赖 qsort 稳定性”的代码属于未定义行为。需要严格稳定时我会自己写一个归并排序或者把序号字段作为比较器兜底。这个决策应该在写排序代码之前完成而不是排序完成后再看结果。2.2 函数指针比较器让一套 C 排序代码同时处理整数、字符串和结构体C 语言没有模板也没有泛型语法排序函数要通用只能靠“元素大小 函数指针”这两个参数。标准库 qsort 的比较器类型是 int (*)(const void *, const void *)自己写的排序函数也应该沿用这个约定。比较器返回值约定为第一个参数排在前面返回负数相等返回 0排在后面返回正数。下面是一个对整数数组、字符串数组和结构体数组都适用的比较器集合。#include string.h typedef int (*cmp_fn)(const void *, const void *); int cmp_int(const void *a, const void *b) { int ia *(const int *)a; int ib *(const int *)b; return (ia ib) - (ia ib); /* 返回 -1 / 0 / 1 */ } int cmp_str(const void *a, const void *b) { /* qsort 传入的是数组元素地址char* 数组的“元素地址”就是 char** */ char * const *sa a; char * const *sb b; return strcmp(*sa, *sb); } typedef struct { int score; char name[32]; } Student; int cmp_student(const void *a, const void *b) { const Student *pa a; const Student *pb b; if (pa-score ! pb-score) return (pa-score pb-score) - (pa-score pb-score); return strcmp(pa-name, pb-name); }cmp_int 里故意不用“return ia - ib”是因为当 ia 是 INT_MAX、ib 是 INT_MIN 时减法会溢出未定义行为在开启优化后可能产生完全错误的结果甚至让比较器不具备反对称性。cmp_str 里最容易被新手绕晕的是指针层级数组元素本身是 char*qsort 回调收到的参数是“指向元素的指针”所以要先把 void* 转成 char** 再解引用得到真正的 char*。2.3 内存账原地排序、额外数组和递归栈的取舍在写一个排序算法前先把内存预算列出来。下面这张表给出了五种常见排序算法在平均情况下的时间和空间代价最后一列“稳定性”表示该实现能否保证相同键值顺序不变。算法平均时间复杂度最坏时间复杂度额外空间稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定嵌入式场景里O(n) 额外空间不是“多一个数组”那么简单。比如用归并对一个 20 KB 的传感器数据排序就要再找一块同样大小且能满足对齐要求的 RAM这在只有 64 KB 内存的 MCU 上可能直接导致分配失败。快速排序的 O(log n) 来自递归栈帧如果枢纽元选得不好退化成 O(n) 深度栈会先于堆爆掉。因此内存受限时优先选择堆排序或原地快排数据规模小、要求稳定时选插入排序或归并数据规模大且卡在内存上只能堆排序。3. 冒泡排序到快速排序C 语言手写过程中的优化与越界排查3.1 冒泡排序 C 语言实现与两个早停优化冒泡排序是最容易验证思路的排序两层循环内层把相邻逆序对交换跑完一轮后最大的元素“冒”到末尾下一轮就不用再看末尾。基础版本不复杂但工程上几乎不会直接用 O(n²) 的冒泡排序它真正的价值是用来检查你对“数据是否有序”的判断是否足够敏感。下面这个版本在每一轮记录是否发生过交换没有交换就直接结束。void bubble_sort(int a[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int t a[j]; a[j] a[j 1]; a[j 1] t; swapped 1; } } if (!swapped) break; } }第一个优化是“无交换早停”已经有序的数组只需要一轮扫描就退出复杂度退化为 O(n)。第二个优化是记录最后一次交换发生的位置因为最后一次交换之后的所有元素都已经有序下一轮扫描不再需要走到 n-1-i而是走到 last_swap。把内层循环上限改成动态位置后在大段已有序的数组上能减少大量比较。void bubble_sort_opt(int a[], int n) { int upper n - 1; while (upper 0) { int last_swap -1; for (int j 0; j upper; j) { if (a[j] a[j 1]) { int t a[j]; a[j] a[j 1]; a[j 1] t; last_swap j; } } if (last_swap -1) break; upper last_swap; } }第二版把外层 for 改成了 while因为 upper 的更新不再遵守“每轮减一”的固定规律。注意 last_swap 初始化为 -1不能初始化为 0否则已经有序时 upper 被设为 0虽然循环也会退出但多了一次边界判断语义上也不够直接。这个函数的时间复杂度仍然是 O(n²)但比较次数在接近有序的数据上会明显下降。3.2 快速排序 C 语言实现三数取中与重复元素分区快速排序是 C 语言面试和工程中见面率最高的排序核心是分区选一个枢纽元 pivot把数组分成“小于 pivot”和“大于 pivot”两段然后递归处理两段。很多人手写快排时直接选 a[hi] 或 a[lo] 当 pivot在完全有序的数组上会退化到 O(n²)。常见做法是选首、中、尾三个位置的中位数作为 pivot尽可能避免退化。static int median_pivot(int a[], int lo, int hi) { int mid lo (hi - lo) / 2; if (a[mid] a[lo]) { int t a[lo]; a[lo] a[mid]; a[mid] t; } if (a[hi] a[lo]) { int t a[lo]; a[lo] a[hi]; a[hi] t; } if (a[hi] a[mid]) { int t a[mid]; a[mid] a[hi]; a[hi] t; } return a[mid]; } static int partition(int a[], int lo, int hi) { int pivot median_pivot(a, lo, hi); int i lo - 1; int j hi 1; for (;;) { do { i; } while (a[i] pivot); do { j--; } while (a[j] pivot); if (i j) return j; int t a[i]; a[i] a[j]; a[j] t; } } void quick_sort(int a[], int lo, int hi) { while (lo hi) { int p partition(a, lo, hi); if (p - lo hi - p) { quick_sort(a, lo, p); lo p 1; } else { quick_sort(a, p 1, hi); hi p; } } }分区用的是 Hoare 算法两个指针从两端向中间扫描遇到等于 pivot 的元素时都停下并交换。这样做是刻意的如果遇到相等元素直接跳过会导致所有相等元素堆到某一侧布局变得极度不均匀。递归调用处做了“只递归短的那一半长的一半用循环处理”的尾递归优化递归深度被压到 O(log n)这是应付大数组和栈受限环境的实用写法。这段代码里最容易写错的是递归边界。Hoare 分区返回的 j 是“小于等于 pivot 区域”的最后一个位置所以递归区间是 [lo, p] 和 [p1, hi]不是 [lo, p-1] 和 [p1, hi]。如果按后面这种写法等于 pivot 的元素会被左侧递归漏掉排序结果不对。pivot 不是像 Lomuto 分区那样固定在最终位置理解这一点后边界就不会记混。3.3 排序算法 C 语言实现时最常见的越界和死循环错误排序算法出错大多不是逻辑理解不了而是边界条件写错。下面这三种情况在 C 语言里出现频率最高。错误写法后果正确写法快排递归 quick_sort(a, lo, p-1) 配 Hoare 返回 j左侧漏掉等于 pivot 的元素排序结果错误返回 j 时递归 [lo, j]冒泡内层循环 for (j 0; j n - i; j)j1 达到 n越界读 a[n]for (j 0; j n - 1 - i; j)归并临时数组用 tmp[i] 写回原数组索引错位把数据写到错误位置用 tmp[k] 写回 a[lok]调试时我一般会在 partition 后加一条 assert检查返回值是否落在合法区间内。C 语言的标准库 assert 在 NDEBUG 宏定义下会被整体删除所以调试版本不要加 -DNDEBUG等确认无误后再开优化编译。用 AddressSanitizer 编译排序代码能在元素越界写入的第一时间定位到具体函数和行号比事后看排序结果高效得多。这一点对排序这类“越界后不一定立刻崩溃”的代码尤其重要因为越界访问可能只污染相邻变量最后表现为一个莫名其妙的逻辑错误。4. 归并排序与 C 标准库 qsort稳定、内存和交付速度的取舍4.1 归并排序 C 语言实现临时数组、稳定性与内存复用归并排序是自底向上的分治先把数组拆成两半分别排好再合并两个有序段。合并时需要一个临时数组这是它额外内存 O(n) 的来源也是嵌入式 C 开发者最介意的地方。下面的实现先把数组拆到底再在 merge 阶段使用 malloc 分配临时空间。#include stdlib.h static void merge(int a[], int lo, int mid, int hi) { int len hi - lo 1; int *tmp (int *)malloc(len * sizeof(int)); if (tmp NULL) return; /* 实际工程里要决定如何处理分配失败 */ int i lo, j mid 1, k 0; while (i mid j hi) { if (a[i] a[j]) tmp[k] a[i]; else tmp[k] a[j]; } while (i mid) tmp[k] a[i]; while (j hi) tmp[k] a[j]; for (int t 0; t len; t) a[lo t] tmp[t]; free(tmp); } void merge_sort(int a[], int lo, int hi) { if (lo hi) return; int mid lo (hi - lo) / 2; merge_sort(a, lo, mid); merge_sort(a, mid 1, hi); merge(a, lo, mid, hi); }merge 里比较条件用的是a[i] a[j]而不是。这个细节决定了归并排序是否稳定当左右两个元素相等时先把左半边的元素放进临时数组右半边相同值的元素自然跟在后面相对顺序保持不变。如果把条件写成相等时先取右半边稳定性就丢了。需要注意C 语言里 malloc 的代价不小递归每个层级都调用 merge 意味着每层都在重复分配和释放。数据量一上来内存碎片和分配耗时都会成为问题。工程里常见的改进是先在外面分配一次大小为 n 的临时数组递归过程中复用这一块缓冲区。merge 函数接收 tmp 作为参数不再自己 malloc。这样既保留了稳定排序特性又把空间申请的次数从 O(n) 降到 O(1)。如果数据量特别大还可以把 merge_sort 改成非递归的自底向上版本彻底消除函数递归带来的栈压力。4.2 qsort 的正确打开方式结构体排序与性能陷阱C 标准库的 qsort 是绝大多数场景下的第一选择不用自己写递归不用担心边界条件通用性最好。需要记住的是qsort 不保证稳定而且它的性能高度依赖比较器和元素大小。下面的代码展示了一个按成绩降序、再按姓名升序排序的完整调用。#include stdlib.h #include string.h typedef struct { int score; char name[32]; } Student; int cmp_student_desc(const void *a, const void *b) { const Student *pa a; const Student *pb b; if (pa-score ! pb-score) return (pa-score pb-score) - (pa-score pb-score); /* 成绩降序 */ return strcmp(pa-name, pb-name); /* 姓名升序 */ } void sort_students(Student arr[], size_t n) { qsort(arr, n, sizeof(arr[0]), cmp_student_desc); }qsort 的几个参数按顺序分别是数组首地址、元素个数、单个元素字节数、比较器函数指针。最容易写错的是第三个参数有人会写成 sizeof(Student*) 或者写死某个数字导致数组元素整体错位排序结果完全不可信。用 sizeof(arr[0]) 是最稳妥的写法即使以后结构体加了字段这个值也会自动变化。注意qsort 移动元素时是按第三个参数指定的字节数整块拷贝。如果结构体特别大比如几百字节一条记录排序过程中每次交换都要拷贝几百字节百万级数据量会产生数十 GB 级别的内存拷贝流量。遇到这种情况我一般会把数组改成“指向结构体的指针数组”排序时只交换指针。排序完成后遍历指针数组就能按顺序访问原结构体。这样交换开销固定为 8 字节比较器里多一层指针解引用但整体性能提升非常明显。代价是多一块 n * sizeof(void*) 的额外内存以及比较器指针层级变深新手容易在返回值上出错。4.3 什么场景应该绕开 qsort 自己写排序先说结论能用 qsort 的地方优先用 qsort。自己写排序的理由无非是下面几种需要稳定排序qsort 无法保证排序的是超大结构体数组且没有足够内存维护指针数组目标平台没有标准库比如某些 MCU 的裸机环境对性能极端敏感需要把比较器内联进排序循环避免函数指针间接调用。最后一种场景里C 语言的宏或模板化写法更合适。#define SORT_TYPE int #define CMP(a, b) ((a) (b)) void insertion_sort_macro(SORT_TYPE a[], int n) { for (int i 1; i n; i) { SORT_TYPE key a[i]; int j i - 1; while (j 0 CMP(a[j], key)) { a[j 1] a[j]; j--; } a[j 1] key; } }上面这个宏定义的 CMP 是“小于”判断对应升序插入排序。改成(a) (b)就能得到降序。宏的方式放弃了类型安全和函数指针的通用性换来的是编译器可以完全内联比较逻辑排序循环里少一层间接跳转。这种写法适合嵌入式驱动里固定类型、固定排序方向的场景不适合通用库。5. 把排序算法用到工程里top-K、内存受限与正确性验证5.1 用堆在固定内存里求 top-K全排序在很多场景里是不必要的。比如传感器每秒钟上报 1000 个数据点只需要保留最近一小时里信号强度最大的 100 个点。完整排序要维护 360 万个元素而一个容量为 100 的最小堆就能解决问题额外内存固定。最小堆的堆顶是当前 100 个最大元素里最小的那个新数据只要比堆顶大就替换堆顶并重新调整堆。void sift_down(int heap[], int k, int idx) { int key heap[idx]; while (idx k / 2) { /* 有左子节点时继续 */ int child 2 * idx 1; if (child 1 k heap[child 1] heap[child]) child; if (key heap[child]) break; heap[idx] heap[child]; idx child; } heap[idx] key; } void insert_topk(int heap[], int k, int *n, int value) { if (*n k) { heap[(*n)] value; int i *n - 1; while (i 0 heap[(i - 1) / 2] heap[i]) { int t heap[i]; heap[i] heap[(i - 1) / 2]; heap[(i - 1) / 2] t; i (i - 1) / 2; } } else if (value heap[0]) { heap[0] value; sift_down(heap, k, 0); } }这里维护的是最小堆堆顶永远是当前 top-K 里最小的值。等数组填满后新元素比堆顶大才替换因此堆里保留的就是全局最大的 K 个元素。每次插入或替换后调整堆的代价是 O(log k)整个数据流处理完的总复杂度是 O(n log k)。如果要求 top-K 按从大到小排序输出等数据处理完后再把堆里元素依次取出来即可。这个思路比“先全排序再取前 K 个”在内存和耗时上都更稳。5.2 用 sanitizer 与随机测试验证排序算法实现手写排序算法后第一步不是看性能而是验证正确性。最靠谱的验证方式是生成多组边界数据和系统自带的 qsort 结果做逐元素对比。测试用例至少要覆盖空数组、单元素数组、完全升序、完全降序、所有元素相等、大量重复元素、随机大数组。前后两组代码交替运行任何下标或交换逻辑错误都会在对比中暴露。gcc -stdc11 -O1 -g -Wall -Wextra -fsanitizeaddress,undefined sort_test.c -o sort_test ./sort_test-fsanitizeaddress负责捕获越界读写和释放后使用-fsanitizeundefined负责捕获有符号整数溢出、数组下标越界等未定义行为。排序代码一旦出现 off-by-one这两个参数会在错误发生的第一时间打印出文件、行号和函数调用栈。注意不要在开启-O2加 sanitizer 的组合下调试图标板上的问题因为优化器可能重排代码排查难度会上升先用-O0或-O1定位问题确认无误后再做性能测试。验证正确性之后再回到性能。不要用冒泡排序测试十万级随机数组也不要一上来就对比 qsort 和手写快排。正确顺序是先在小数组上确认结果一致再逐步放大规模最后才看时钟耗时。性能观察时要防止编译器优化掉看似无用的排序结果可以把排序后的数组元素累加成一个 volatile 变量输出。嵌入式环境里还要额外注意递归深度和临时数组大小用二分法逐步增大数据量观察栈空间峰值避免在测试机上跑得好好的代码一到目标板上就触发 HardFault。本文还有配套的精品资源点击获取