先抛个问题你在写代码的时候有没有想过一个问题——“排序还有必要自己捣鼓吗”我当年也觉得排序嘛qsort一调、sort()一用就完事了。直到有一次要处理几十万条订单数据按金额直接排完后发现另一列的关联凭证全乱了这才意识到排序算法的“稳定性”“空间复杂度”这些破事根本不是理论考试刁难人而是真实业务里的血泪坑。这篇东西我还是按自己习惯的“白话代码踩坑”方式来讲。适合对象学数据结构的学生、准备面经的应届生以及想在C语言里把排序用得明明白白的上班族。内容把常用排序算法分门别类拆一遍每一类都给C语言可跑的代码再附上我实际用过的判据和建议。不会有花里胡哨的封装直接拿数组说话。1. 先把排序算法的“评价体系”搭起来聊算法不谈复杂度等于评车不谈油耗。排序算法的核心指标就三个时间复杂度、空间复杂度、稳定性。1.1 时间复杂度最好、平均、最坏一个都不能少看排序算法我习惯先问三个问题数组已经有序这个算法还要跑多久对应最好情况。数组完全乱序平均下来跑多久对应平均情况。数组故意反着排比如降序数据要求升序排序算法会不会塌陷对应最坏情况。很多人的误区是只看平均时间复杂度比如快速排序平均是O(n log n)看起来很美但遇到近乎有序的数组且基准值选得烂时它可能塌到O(n²)。这不是教科书上的“极端假设”是真实发生过无数次的线上事故。1.2 空间复杂度原地排序与非原地排序的分界线空间复杂度衡量的是算法在排序过程中额外占用的内存。O(1)额外空间原地排序比如冒泡、选择、插入、堆排序。O(n)或O(log n)额外空间非原地排序或需要栈辅助比如归并排序需要临时数组合并快速排序的递归栈在理想情况下是O(log n)。为什么关心这个处理嵌入式场景、处理单机大文件排序时内存就是命。我在单片机上排传感器数据直接排除归并因为临时数组开销太奢侈在服务器上排海量订单反而更偏向归并因为它稳定且没有退化风险。1.3 稳定性乱序前后的“相对位置”保住没有稳定性是个容易懵的概念一句话讲清楚如果两个值相同的元素排序前a在b前面排序后a依旧在b前面这个排序就是稳定的反之就是不稳定的。举例学生成绩单按“总成绩”降序排总成绩相同的人按“学号”升序排。做法是先按学号排序再用稳定排序按成绩排——这样学号顺序就天然保留下来了。如果用了不稳定排序成绩同分的学生学号会错乱。这个点在实际业务里极其重要因为大部分场景的排序都是“次级关键字已有序需要按主关键字稳定分组”。不理解这一点就会出现开头说的“关联信息错乱”事故。1.4 常用排序算法全景对比表先把主流算法的关键指标摆一张表后面再逐个细说。算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3~1.5)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(nk)O(nk)O(k)稳定基数排序O(d(nk))O(d(nk))O(nk)稳定这张表背下来用处不大关键是把“为什么快”“什么场景翻车”搞清楚。2. 入门三兄弟冒泡排序、选择排序、插入排序这三个算法都是比较类排序里的“初级工种”时间复杂度同为O(n²)但实际表现差异很大。别因为它们简单就跳过——很多工程上的骚操作比如小数组用插入排序就是从这儿来的。2.1 冒泡排序被嫌弃但最适合教学的老实人原理从头到尾两两比较相邻元素把较大的值不断往后挪。每轮结束时最大元素就跟气泡一样浮到数组末尾。下一轮可以少比较一个位置因为末尾已经有序。void bubble_sort(int arr[], int n) { for (int i 0; i n - 1; i) { 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; } } } }这段代码有优化空间如果某一轮循环里一次交换都没发生说明数组已经有序可以直接跳出。加一个标志位就能把“最好情况”从O(n²)降成O(n)void bubble_sort_early_exit(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; } }实际感受冒泡排序教学价值大于工程价值但在元素非常少比如10个以内且代码追求极简时可一用。对应的“两两交换”思路是理解所有交换类排序的基础。2.2 选择排序交换次数最少的O(n²)排序原理每轮扫描未排序部分找出最小值下标然后把最小值交换到“已排序区”的末尾。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; } } }这个算法的不稳定性值得说道说道比如数组[5, 8, 5, 2]第一轮找到最小值2直接跟第一个5交换结果是[2, 8, 5, 5]。原本前面的5被交换走了两个5的相对顺序就变了。所以选择排序虽然“交换次数少”但稳定继承不了冒泡的衣钵。实际使用场景键值对结构体数组排序时如果交换对象是一个很大的结构体比如几百字节选择排序每轮只做一次交换反而比冒泡省了大量内存拷贝。这个优点平时没人提但很实用。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; } }为什么说它是隐藏王者因为当数组“基本有序”时内层循环几乎不用移动元素时间复杂度趋近O(n)。我实测过一个40万条的数据每条记录就是一个字符串长度约200字节的结构体如果全局打乱用插入排序硬排会慢到怀疑人生但如果只把尾部几十条数据乱序插入排序可以直接秒杀快速排序。很多标准库的实现都利用了这一点比如Java的Arrays.sort()在小数组或者递归分治到小规模时会切回插入排序。C的std::sort里也内置了这个逻辑只不过默认阈值的细节没公开。生活化类比整理一叠学生试卷如果试卷基本是按学号排好的只有个别乱插进来你肯定不会全部推倒重排而是顺手把个别的试卷抽出来插到合适位置——这就是插入排序的思路。2.4 三个初级算法的取舍建议场景首选原因代码最短、最好讲解冒泡逻辑单纯适合演示交换思想结构体元素巨大、数组几乎乱序选择交换次数最少大部分有序、小规模数据插入逆序度低时极快且稳定3. 分治三巨头快速排序、归并排序、堆排序这三个是实际开发中出现频率最高的O(n log n)级算法。但它们的工程实现远比教材伪代码复杂坑也最多。3.1 快速排序平均最快的分治代表原理每次挑一个基准值pivot把数组分成两部分——小于等于pivot的放左边大于等于pivot的放右边。然后递归处理左右两边。教材版代码长这样void quick_sort(int arr[], int low, int high) { if (low high) return; int pivot arr[low]; // 默认拿第一个做基准 int i low, j high; while (i j) { while (i j arr[j] pivot) j--; // 从右往左找小的 if (i j) arr[i] arr[j]; while (i j arr[i] pivot) i; // 从左往右找大的 if (i j) arr[j--] arr[i]; } arr[i] pivot; // 基准归位 quick_sort(arr, low, i - 1); quick_sort(arr, i 1, high); }这段代码看着没问题但直接用在生产环境就是定时炸弹原因有二基准值选第一个元素时数组如果基本有序升序每次分割都极度不平衡递归深度变成n时间复杂度塌陷成O(n²)。递归栈深度过深时C程序直接栈溢出。我在实际项目里一般不用默认第一个做基准。至少用“三数取中”——取首、中、尾三个位置的值选中间大小的当基准。这几乎不增加额外开销但能大幅降低退化概率int median_of_three(int arr[], int low, int high) { int mid low (high - low) / 2; if (arr[low] arr[mid]) swap(arr[low], arr[mid]); if (arr[low] arr[high]) swap(arr[low], arr[high]); if (arr[mid] arr[high]) swap(arr[mid], arr[high]); return arr[mid]; // 中位数作为基准同时保证 arr[low] arr[mid] arr[high] }快排为什么平均是O(n log n)因为每轮把数组分成两半分log n层每层做线性扫描合起来n log n。这个推导不复杂但很重要快排强就强在“分治”和“缓存友好”它是原地排序对内存带宽的消耗比归并低所以平均情况下比堆排序更快。3.2 归并排序稳定性和最坏O(n log n)双保障原理把数组从中间一分为二递归排序左右两半然后合并两个有序数组。合并过程需要临时数组属于典型的空间换时间。void merge(int arr[], int tmp[], int left, int mid, int right) { int i left; int j mid 1; int k left; while (i mid j right) { if (arr[i] arr[j]) { tmp[k] arr[i]; } else { tmp[k] arr[j]; } } while (i mid) tmp[k] arr[i]; while (j right) tmp[k] arr[j]; for (i left; i right; i) { arr[i] tmp[i]; } } void merge_sort(int arr[], int tmp[], int left, int right) { if (left right) return; int mid left (right - left) / 2; merge_sort(arr, tmp, left, mid); merge_sort(arr, tmp, mid 1, right); merge(arr, tmp, left, mid, right); }稳定性的关键在合并那一行比较if (arr[i] arr[j])。写小于等于时左边相等元素先入临时数组右边相等元素后入相对顺序就保住了。如果把误写成稳定性直接破功。这个细节我在代码评审时至少给人揪出过三次。归并排序的工程变体是外部排序的基石当数据量大到放不进内存时比如10GB文本文件先把文件分块读入、块内排序再按归并思想把各块合并这就是数据库和搜索引擎底层排序的基本思路。所以我一直认为理解归并排序不是学了个算法而是理解了“内存装不下时计算机怎么排序”。3.3 堆排序原地且最坏O(n log n)但偏偏用不太上原理先建堆大顶堆/小顶堆然后反复把堆顶元素交换到数组末尾再调整剩余部分继续维持堆结构。void sift_down(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; sift_down(arr, n, largest); } } void heap_sort(int arr[], int n) { // 构建大顶堆从最后一个非叶子节点倒序下沉 for (int i n / 2 - 1; i 0; i--) { sift_down(arr, n, i); } // 依次取出堆顶到末尾 for (int i n - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; sift_down(arr, i, 0); } }堆排序的不稳定性源于堆顶交换相同值的元素在堆里位置本来就乱交换后相对位置没法保证。所以链式数据需要稳定性时我不会选堆排序。为什么实际工程里堆排序没有快排吃香堆排序虽然时间复杂度稳定但它的内存访问模式是“跳跃式”的对CPU缓存的利用远不如快速排序和归并排序。真实数据量大时堆排序反而更慢。堆排序真正的主场是优先队列任务调度、Top-K问题而不是纯排序。3.4 高级排序怎么选才不踩坑先看稳定性和内存再看数据特征和场景。算法稳定性额外空间最大优势最大软肋快速排序不稳定O(log n)平均最快、原地、缓存友好最坏退化、递归栈深归并排序稳定O(n)稳定且最坏也是O(n log n)额外内存大堆排序不稳定O(1)空间原地、最坏可靠常数偏大、缓存不友好我的默认方案是数据不确定、有稳定需求、内存够用 → 归并排序内存紧张、无稳定需求、数据随机 → 快速排序 三数取中数据有Top-K需求 → 堆。4. 打破比较的下限计数排序、基数排序前面所有算法都是“比较类”排序而比较类排序理论上限就是O(n log n)。想再快只能告别“比较”走“数据本身当下标”的路线。4.1 计数排序用空间换时间O(nk)碾压全场原理如果数据是范围有限的整数比如0~10000就开一个长度为k的计数数组统计每个值出现的次数然后按顺序把计数数组“铺回”原数组。不需要任何比较。void counting_sort(int arr[], int n, int max_val) { int *count (int *)calloc(max_val 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 max_val; 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); }注意细节我特意用了“前缀和 从后往前填”的写法而不是直接用“按值依次展开”。因为前者是稳定的后者会丢掉原先数据的相对顺序。实际场景里对一组整数排序往往还要关联其他信息稳定性仍然是刚需。限制也很明显当max_val远大于n时比如排序5个元素但它们都在0到2亿之间开一个2亿大小的计数数组就不合适了。计数排序只适合“数据范围紧凑”的场景。4.2 基数排序按位拆开从低位到高位逐轮稳定排序原理拿一组三位数举例先按个位排序再按十位排序最后按百位排序。每一轮用稳定的排序做子排序通常用计数排序整体就能得到有序结果。void radix_sort(int arr[], int n, int max_digits) { int bucket[10][1000]; // 简化演示实际应该动态分配 int bucket_count[10] {0}; int exp 1; for (int digit 0; digit max_digits; digit) { memset(bucket_count, 0, sizeof(bucket_count)); for (int i 0; i n; i) { int radix (arr[i] / exp) % 10; bucket[radix][bucket_count[radix]] arr[i]; } int idx 0; for (int i 0; i 10; i) { for (int j 0; j bucket_count[i]; j) { arr[idx] bucket[i][j]; } } exp * 10; } }这段代码是教学演示写法工程上要改用链表或一维数组动态分配否则桶大小写死会导致内存浪费。核心思想是每一轮排序只知道当前位但通过“稳定排序”的约束低位排序结果不会破坏最后高位决定大局。基数排序在手机通讯录、车牌号、整数ID这类定长数据上有出色表现但浮点数、字符串变长数据的处理就没那么直接了。4.3 非比较排序的应用边界算法适用数据时间复杂度典型案例计数排序范围小的整数O(nk)统计期末成绩分布、年龄统计基数排序定长整数/字符串O(d(nk))电话号码排序、身份证号排序桶排序均匀分布的浮点数O(n)海量浮点数粗略排序后微调非比较排序看起来很美但现实中数据往往并不满足“紧凑的整数”或“定长”前提。所以它是辅助武器替代不了比较排序的通用性。5. C语言实现排序算法的实战要点这一段是很多人学完算法却写不出能跑进生产环境代码的关键分水岭。语法都会一上线就崩问题多半出在这几个细节里。5.1 交换操作别用异或炫技老老实实开变量网上有一段经典面试代码用异或交换两个整数void swap(int *a, int *b) { *a ^ *b; *b ^ *a; *a ^ *b; }我劝你不要在正经代码里这么写。原因有二当a和b指向同一个地址时第一条异或就把值清零了。排序代码里完全可能出现swap(arr[i], arr[i])的情况。现代编译器对“临时变量交换”的优化已经非常成熟根本不存在性能问题。static inline void swap_int(int *a, int *b) { int tmp *a; *a *b; *b tmp; }使用static inline关键字还能减少函数调用开销。排序是高频循环每一处不必要的开销都会在万级数据量上被放大。5.2 函数指针让排序支持任何数据类型C语言里很多教材的排序函数都是针对int数组写的但实际项目里要排序的是结构体数组。这就需要函数指针也就是C语言版的“泛型”手段。下面的代码示范如何写一个通用的插入排序接口// cmp 返回 -1/0/1表示 ab / ab / ab void generic_insertion_sort(void *base, size_t nmemb, size_t size, int (*cmp)(const void *, const void *)) { unsigned char *data (unsigned char *)base; unsigned char *key (unsigned char *)malloc(size); for (size_t i 1; i nmemb; i) { memcpy(key, data i * size, size); size_t j i; while (j 0 cmp(data (j - 1) * size, key) 0) { memcpy(data j * size, data (j - 1) * size, size); j--; } memcpy(data j * size, key, size); } free(key); }这条路就是qsort的设计思路。你完全可以直接用标准库的qsort然后把自己写的cmp函数往里扔。但如果想深挖“库函数底层怎么运作”亲手实现一遍上面的泛型化封装对理解内存布局和字节操作帮助极大。我见过很多工作两三年的工程师排序一个结构体数组时还在手工写多重循环比较就是吃透了这个差异。5.3 递归深度与栈溢出快排的真正死穴快速排序递归深度平均是O(log n)但最坏情况下是O(n)。对10万条数据最坏递归10万层栈直接爆掉。常规解法是尾递归优化先递归处理较短的一侧再用循环处理较长的一侧把递归深度压到O(log n)void quick_sort_tail_recursive(int arr[], int low, int high) { while (low high) { int pivot_idx partition(arr, low, high); // 递归处理左侧较短的区间 quick_sort_tail_recursive(arr, low, pivot_idx - 1); // 循环处理右侧较长的区间 low pivot_idx 1; } }工程上的另一条路是自研栈把待排序区间下标压入栈用循环模拟递归彻底摆脱栈溢出烦恼。我写嵌入式离线分析工具时就常这么干因为目标环境的栈往往只有十几KB。5.4 测试排序算法的正确姿势写排序算法不测试等于裸奔。我的测试套路分四步乱序测试随机生成10万条数据验证排序后完全升序。边界测试空数组、单元素数组、两个元素数组、全部相同元素数组。逆序测试从大到小排列的数组专门攻快速排序的退化弱点。稳定性测试构造“值相同但带序号”的结构体数组排序后检查相同值的序号顺序是否保持不变。测试验证函数很简单int is_sorted(int arr[], int n) { for (int i 1; i n; i) { if (arr[i - 1] arr[i]) return 0; } return 1; }6. 常见问题与排查技巧实录把我在实际项目里踩过的坑和最常被问的问题集中列在这一节。这些都是不在教科书里的“现场型经验”。6.1 快速排序越排越慢先查基准值的选取症状数据只有5万条快速排序耗时比插入排序还长。排查第一步打印每一层递归的区间长度如果发现一侧始终只有1个元素、另一侧覆盖剩余全部元素基本可以断定基准值选取导致严重失衡。对策不要用固定位置取基准改用“三数取中”或随机选基准。随机化加“三数取中”是性价比最高的组合代码只多加几行退化概率大大降低。6.2 排序后数据出现了“看起来随机缺失”的现象真实案例我把一组带ID的结构体用堆排序后发现ID的顺序莫名其妙乱套。排查后发现堆排序本身是不稳定性排序而我恰好用它处理了“首要关键字相同需要保留次级关键字顺序”的数据。对策先问自己“数据是否依赖原有的相对顺序”如果是直接选稳定的归并排序或插入排序不要硬上快排和堆排。6.3 小数组排序为什么反而是插入排序最快几万个数据时快速排序看似碾压一切。但一旦数组规模掉到百以内插入排序经常反杀。原因不复杂插入排序实现简单没有递归、没有基准值计算、没有分区操作单次循环的开销极低。小规模数据的循环次数差异不大常数项反而成了决定性因素。现代CPU的缓存预取对小数组的顺序访问非常友好。这个现象衍生出工程上非常经典的“混合排序”思路数据量大用快速排序或归并排序当递归切分到小区间时比如n 16改用插入排序收尾。Cstd::sort和很多数据库内部排序实现都这么做。6.4 大数组排序归并排序的内存占用翻车排序200万条结构体每条64字节数组本身占128MB。归并排序需要同尺寸的临时数组又占128MB。在内存紧张的环境下直接失败。对策优先用原地快速排序。如果必须归并可以尝试把数据分段处理降低临时数组峰值或者换用O(n log n)且原地操作的堆排序兜底。我在服务器上排几百万条订单时一般默认快排只有明确要“稳定且保证最坏情况”才用归并。6.5 排序结果“部分有序”但顺序似乎没有完全稳定举例先按日期升序排又按金额降序排期望“日期相同的人里金额从高到低”。但结果里日期相同的人金额顺序乱了。原因第一轮按日期排序如果用了一个不稳定排序日期相同的元素的相对顺序已经乱了第二轮即使使用稳定的排序也只能保留“第一轮排序后的顺序”而这个顺序本身已经不可靠。对策主次关键字排序最稳的做法是从次要关键字开始一次次向前推进先按金额排再按日期做稳定排序。这样“日期相同的元素里金额顺序”才保留得住。6.6 速查表遇到问题先查这一行症状可能的根因首选解法快排退化变慢基准值选法不当三数取中或随机基准排序后关联信息乱不稳定排序换归并、插入或改用稳定算法大数组内存不足归并临时数组太大快排或堆排原地操作递归栈溢出递归深度太大尾递归优化、自研栈小数组排序反而慢忽略常数项小区间切回插入排序相同值顺序乱排序算法本身不稳定使用稳定排序7. 个人经验收尾排序算法最后拼的是场景判断我印象最深的一次排查是新同事用直接插入排序去排100万条日志记录跑了一个多小时没结束。我当时没批评他用错了算法只是让他把数据规模换成10万随机数据测一遍再做对比实验——结果显示插入排序比快排慢了近十倍。这让他真正理解了“不同规模的算法选择不是数学题是工程题”。排序算法这块入门的时候以为就是背背复杂度做做动画演示后来才发现真正的门槛在于场景判断数据规模多大是否近乎有序元素是整数还是结构体内存吃不吃紧需不需要稳定每一个条件都在影响算法选型。我自己现在的排序工具箱是这样的默认第一选择qsort或者手写快速排序三数取中 尾递归优化。需要稳定且内存充足归并排序。数据量极小几十条插入排序。内存吃紧且无稳定需求堆排序或快排。整数范围紧凑、量级大计数排序或基数排序。如果你正在准备面试建议把原理和代码都默写一遍然后跑一遍应力测试再手写一遍泛化版本——这三步下来基本就不会被各种变异题问倒了。如果你在写业务代码希望这篇能帮你少踩几个“数据明明排对了关联信息却全乱了”的坑。排序算法不算难但值得认真对待。搞清楚了评价体系剩下的就是多写、多测、多对比。