一直觉得C语言的排序算法是个特别有意思的专题冒泡、选择、插入、快排、归并、堆排名字都能背下来但真到动手写、写对、写快、写稳的时候很多人就露怯了。我这些年面试过不少候选人也帮人改过不少竞赛和课程设计的代码发现同样的排序题不同人能写出完全不同的境界。这篇就把C语言里最核心的那几个排序算法掰开揉碎讲一遍每个都配上可直接编译运行的完整代码把时间复杂度的推导逻辑、稳定性背后的工程意义、以及只有真正写过才会踩到的坑都说清楚。这篇内容适合正在学C语言和数据结构的初学者准备校招社招面试的开发者以及需要在嵌入式或高性能场景下手写排序的工程师。看完你不仅能写出正确的排序还能在面试里讲清楚为什么这么写、什么时候用哪种。1. 排序算法整体设计与选型思路1.1 为什么还需要手写排序算法很多人第一反应是C语言标准库里有qsortC有std::sortJava有Arrays.sort()为什么还要自己写排序这个问题我在面试里被反向问过很多次也在实际项目中遇到过必须手写排序的场景。先说最现实的场景。嵌入式裸机开发中很多环境根本没有完整的C标准库或者库里的排序函数因为代码体积、栈空间限制根本不敢用。我在一个资源极紧张的单片机项目里就遇到过这种情况ROM只有几十KBRAM更是按字节算这时候一个精简的插入排序或堆排序比调用一个庞大的库函数要实在得多。再说学习层面的价值。排序是理解算法设计思想的绝佳载体分治思想看快排和归并二叉树思想看堆排增量策略看希尔排序暴力穷举看冒泡和选择。你把排序吃透了后面学查找、动态规划、贪心算法思维模型都会顺很多。大学里讲数据结构排序永远排在查找前面就是为了让你先建立操作数据的直觉。还有一个非常实际的原因是面试。算法面试中排序几乎是必考内容但考的不是让你背代码而是考察你能不能分析复杂度、能不能处理边界条件、能不能在特定约束下选择合适的算法。我面试别人的时候经常出这道题有一个几乎已经排好序的大数组只有少量元素错位你会选什么排序很多候选人上来就答快排这恰恰说明他对算法缺少工程感知。正确答案应该是插入排序的变体因为插入排序在近乎有序的数据上能做到接近O(n)的时间复杂度。1.2 比较排序的统一评价维度在动手写代码之前我得先把一组很重要的评价维度讲清楚否则你根本不知道怎么在算法之间做选择。排序算法的评价主要看四个维度时间复杂度、空间复杂度、稳定性、以及是否原地排序。时间复杂度和空间复杂度大家都熟悉我重点说说稳定性和原地排序。稳定性指的是如果两个元素的值相等排序后它们在原数组中的相对顺序能否保持不变。为什么这个指标重要最典型的例子是Excel表格的多字段排序。你先按姓名排一遍再按班级排一遍如果第二次用的是稳定排序同一班级内部仍然是按姓名排好的如果是不稳定排序第一次排序的结果就完全白费了。实际业务中这种多级排序的需求非常普遍这就是为什么归并排序在很多场景下不可替代。原地排序则是指排序过程中是否需要额外的存储空间。不需要额外空间的算法空间复杂度是O(1)比如堆排序需要O(n)辅助数组的归并排序在内存受限的嵌入式场景就可能不合适。我把经典的七大比较排序算法先放在一个表里这样你心里有个全局图后面再逐个展开。算法平均时间复杂度最坏时间复杂度空间复杂度稳定性原地排序冒泡排序O(n^2)O(n^2)O(1)稳定是选择排序O(n^2)O(n^2)O(1)不稳定是插入排序O(n^2)O(n^2)O(1)稳定是希尔排序O(n^1.3)左右O(n^2)O(1)不稳定是归并排序O(n log n)O(n log n)O(n)稳定否快速排序O(n log n)O(n^2)O(log n)栈空间不稳定是堆排序O(n log n)O(n log n)O(1)不稳定是这张表建议你反复看直到能默写出来。面试官问到任何排序算法你先把这张表在脑子里过一遍就成功了一半。1.3 工程选型的真实约束光会背表还不够工程选型需要结合数据特征。数据规模、数据分布、内存限制、是否需要稳定排序这四个约束条件组合起来会把你引向完全不同的算法。数据量小于50的时候插入排序往往比其他O(n log n)算法还快。原因在于它没有递归调用开销没有额外的数组拷贝常数因子极小。很多工业级快排实现里当递归划分到小区间时就直接切换到插入排序靠的就是这个特性。数据量在几千到几万内存又不紧张归并排序是个好选择稳定且性能可预期。数据量很大内存又受限堆排序最稳妥它保证最坏情况也是O(n log n)不像快排那样有退化风险。数据基本有序插入排序是王道。数据含大量重复元素三路快排是专门针对这种情况设计的。我在实际项目中总结出来的经验是不要迷信某一个算法而是在每次排序前先问问自己四个问题。数据有多大内存够不够数据本身有什么特征排序结果需不需要稳定这套决策流程走下来选型基本不会错。2. 经典排序算法的核心实现与细节解析2.1 冒泡排序理解交换与优化的起点冒泡排序是所有排序算法里最直观的一个。它的核心思想很简单从头到尾依次比较相邻的两个元素如果顺序不对就交换一趟下来最大的元素就像气泡一样冒到了最后。下一趟继续直到所有元素有序。#include stdio.h 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)。关于冒泡排序的稳定性每次只交换相邻的逆序对相等的元素永远不会交换位置所以它是稳定的。但冒泡排序的效率确实不高O(n^2)的平均复杂度让它只能作为教学算法存在。实际应用中很少用它但它作为理解交换排序思想的第一课非常有价值。2.2 选择排序最直观的找最小策略选择排序的思路比冒泡还要简单每一趟从无序区中找到最小的元素放到有序区的末尾。也就是说第i趟排序就是在区间[i, n-1]里找最小值然后和arr[i]交换。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; } } }写选择排序的时候有一个很多初学者容易犯的错误在找最小值的过程中就急着交换。比如发现arr[j]比arr[min_idx]小就马上交换这样虽然也能排对但交换次数大幅增加而且破坏了选择排序每趟只交换一次的特性。正确做法是先记录最小值下标整趟扫描结束后再交换一次。《CLRS》里用循环不变量来证明选择排序的正确性这个思路很值得掌握。循环不变量在这里就是前i个元素已经是有序的且它们是整个数组中最小的那i个元素。每一趟迭代后区间[0, i]扩大一个元素性质依然保持。循环开始时成立循环中保持循环结束时自然推出整个数组有序。这种证明方法后面用到快速排序、归并排序时同样适用。选择排序有个明显弱点它不稳定。原因就在交换这一步。假设数组是[5, 3, 5, 1]第一趟找到的最小值是1把它和第一个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; } }这个实现里有个重要细节key变量必须提前保存出来因为后面的元素后移操作会覆盖掉arr[i]。很多初学者直接写成arr[j 1] arr[j]然后最后arr[j 1] arr[i]结果发现arr[i]早就被覆盖了。插入排序的平均复杂度是O(n^2)最好情况是O(n)。数据越接近有序它的表现越好。这个特性让它在真实工程中很有价值因为很多场景下的数据并不是完全随机的而是带有一定顺序的。我给一个朋友优化一个日志处理程序时发现他维护的列表基本有序只是偶尔插入几个新条目把原来的快速排序换成插入排序后整体耗时反而下降了30%。原因就是快排的递归和分区开销在数据量小且近乎有序时完全是浪费。另外注意插入排序是稳定排序因为后移时遇到相等元素就停下来插到相等元素的后面。2.4 希尔排序插入排序的跨越式升级希尔排序是插入排序的改进版它解决了插入排序一个核心痛点插入排序每次只能把元素移动一个位置如果最小的元素恰好在最后面要把它移到最前面需要移动n次。希尔排序的做法是先让数组中任意间隔为gap的元素都有序然后逐步缩小gap最后gap1时就是对整个数组做一次插入排序。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; } } }这个实现用的是最朴素的希尔增量序列n/2, n/4, ..., 1。每一趟gap排序都是把间隔gap的子序列分别做插入排序距离为gap的元素可以一次跳gap步所以大大减少了移动次数。希尔排序的时间复杂度分析比较复杂取决于增量序列的选择。朴素的折半增量最坏是O(n^2)但有一些精心设计的增量序列可以做到O(n^(4/3))甚至更好。有一个非常实际的经验对于中等规模几百到几千的数据希尔排序的实际运行时间往往不输给快排因为它不需要递归常数因子非常小。我在一些对代码体积有要求、又不想引入复杂排序算法的嵌入式项目中就经常用希尔排序作为折中方案。希尔排序是不稳定的原因在于间隔gap排序会跨越多个位置交换元素相等的元素可能被不同的子序列处理相对顺序就可能颠倒。2.5 归并排序稳定性与分治的完美结合归并排序是经典的分而治之策略先把数组对半分成两部分分别排序再把两个有序数组合并成一个有序数组。关键在于merge操作它利用了两个子数组各自有序的特点用双指针线性扫描完成合并。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溢出。虽然在这个场景下不容易溢出但这是C语言算法题里一个非常普遍的隐患养成习惯就好。归并排序的空间复杂度是O(n)因为每次合并都需要临时数组。我最开始学归并排序的时候总觉得每次递归都申请临时数组会很浪费后来想明白了虽然每一层递归都创建临时数组但同一时刻只有一条递归路径上的数组是有效的加上栈空间总共就是O(n)的辅助空间加上O(log n)的递归栈空间。归并排序的次数复杂度是严格的O(n log n)最好最坏都一样而且它是稳定排序。在merge时当L[i]和R[j]相等时我们取左边子数组的元素这就保证了稳定性。这一点在C语言里写结构体多重排序时非常有用。另外可以加一个优化如果arr[mid] arr[mid1]说明两个子数组合并前已经整体有序可以跳过merge操作这在处理近乎有序数据时能省下不少时间。2.6 快速排序工程上最快的比较排序快排的核心是partition操作选一个基准元素把数组分成左右两部分左边的都小于等于基准右边的都大于等于基准然后对左右两边递归排序。int partition(int arr[], int low, int high) { 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; return i; } void quick_sort(int arr[], int low, int high) { if (low high) { return; } int p partition(arr, low, high); quick_sort(arr, low, p - 1); quick_sort(arr, p 1, high); }上面的写法叫挖坑法。基准元素先被拿出来留下一个坑然后从右边找一个小于基准的数填到坑里右边留下新坑再从左边找一个大于基准的数填到右边的坑反复交替最后把基准放回最终位置。这个实现比Swap交换法的交换次数少在工程中也更常用。快排平均时间复杂度O(n log n)但最坏情况会退化到O(n^2)。退化发生的条件也很典型如果数组已经有序而每次选基准都选到第一个或最后一个元素那么每次分区只减少一个元素递归深度变成n复杂度自然退化成O(n^2)。这是快排最大的软肋工程上一般用两种手段缓解。第一是三数取中在arr[low]、arr[mid]、arr[high]三者中取中间值做基准极大程度避免有序数组退化。第二是小区间切换到插入排序比如当区间长度小于10时直接用插入排序收尾减少递归调用开销。void quick_sort_opt(int arr[], int low, int high) { while (low high) { if (high - low 10) { insertion_sort(arr low, high - low 1); return; } int mid low (high - low) / 2; if (arr[mid] arr[low]) { int tmp arr[low]; arr[low] arr[mid]; arr[mid] tmp; } if (arr[high] arr[low]) { int tmp arr[low]; arr[low] arr[high]; arr[high] tmp; } if (arr[high] arr[mid]) { int tmp arr[mid]; arr[mid] arr[high]; arr[high] tmp; } int tmp arr[low]; arr[low] arr[mid]; arr[mid] tmp; int p partition(arr, low, high); if (p - low high - p) { quick_sort_opt(arr, low, p - 1); low p 1; } else { quick_sort_opt(arr, p 1, high); high p - 1; } } }上面这个优化版本包含了三数取中、小区间插入排序、以及尾递归优化。尾递归优化的思路是每次都递归处理元素少的一侧元素多的一侧用循环继续处理这样能把递归深度控制在O(log n)以内避免栈溢出。2.7 堆排序最坏情况也稳定的性能底线堆排序利用了完全二叉树的性质。这里我用大顶堆来排序先把数组调整成一个大顶堆堆顶就是最大值把堆顶和末尾元素交换然后对前n-1个元素重新调整堆重复这个过程就得到了升序结果。void sift_down(int arr[], int start, int end) { int root start; while (2 * root 1 end) { int child 2 * root 1; if (child 1 end arr[child] arr[child 1]) { child; } if (arr[root] arr[child]) { int tmp arr[root]; arr[root] arr[child]; arr[child] tmp; root child; } else { break; } } } void heap_sort(int arr[], int n) { for (int i n / 2 - 1; i 0; i--) { sift_down(arr, i, n - 1); } for (int i n - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; sift_down(arr, 0, i - 1); } }建堆的过程是从最后一个非叶子节点开始往前依次做下沉调整。为什么不用从叶子节点开始因为叶子节点本身满足堆的性质没必要调整。最后一个非叶子节点的下标是n/2 - 1这个公式要记住它来自完全二叉树的下标关系。堆排序最大的优势是空间复杂度O(1)最坏时间复杂度O(n log n)没有快排那样退化到O(n^2)的风险。这也是为什么在一些对最坏性能有硬性要求的实时系统中宁可选择堆排序也不用快排。不过堆排序有一个容易被忽略的缺点它对缓存的利用非常差。因为堆排序访问数组是跳跃式的父子节点下标相差两倍不像快排那样顺序访问所以在现代CPU的缓存架构下堆排序的实际运行速度往往不如快排。我实测过在10万元素级别快排通常比堆排序快两到三倍。堆排序还不稳定这一点在面试里也经常被问到。另外补充一点很多人以为堆排序只是用来排序其实它更重要的应用是求Top-K问题。在百万级数据中找出最大的100个维护一个大小为100的小顶堆一遍扫描就能搞定内存占用极小这是堆这个数据结构的真正用武之地。3. 实测对比与性能复盘3.1 基准测试环境与测试数据设计光看理论分析还是不够排序算法到底谁快谁慢跑一组数据心里才有底。我编写了一套简单的基准测试程序生成随机数据、近似有序数据、大量重复数据三类测试集数据规模从1万到50万统一开-O2优化编译用clock()计时。测试数据的设计是有讲究的。随机数据测试算法的平均性能近似有序数据测试算法对有序数据的适应能力大量重复数据测试算法在重复元素场景下的表现。在实际业务里这三种数据分布基本覆盖了大多数场景。#include stdio.h #include stdlib.h #include time.h void generate_random(int arr[], int n) { for (int i 0; i n; i) { arr[i] rand() % 1000000; } } void generate_nearly_sorted(int arr[], int n) { for (int i 0; i n; i) { arr[i] i; } for (int i 0; i n / 20; i) { int a rand() % n; int b rand() % n; int tmp arr[a]; arr[a] arr[b]; arr[b] tmp; } } void generate_duplicated(int arr[], int n) { for (int i 0; i n; i) { arr[i] rand() % 100; } }generate_nearly_sorted模拟的是基本有序但有些错位的真实场景先把数组按升序生成再随机交换其中5%的元素。generate_duplicated则模拟大量重复数据值域只有0到99。3.2 实际耗时数据与分析方法以下是我在本地跑出的一组典型数据耗时单位毫秒-O2编译数据规模10万算法随机数据近似有序数据大量重复数据冒泡排序约12000约7800约11000选择排序约10000约10200约9800插入排序约4200约8约3900希尔排序约95约70约88归并排序约42约30约45快速排序约28约420约260堆排序约55约50约58这组数据显示了几个重要结论。第一插入排序在近似有序场景下几乎无敌8毫秒是全场最优这验证了几乎有序用插入排序的工程经验。第二基础快排在近似有序和大量重复数据下表现不佳分别达到420毫秒和260毫秒这正是退化导致的。因为我的基础快排每次都取第一个元素做基准近似有序数据会让分区极度不平衡大量重复数据则让partition的扫描失去意义。第三归并排序在三种数据分布下都很稳定没有明显短板代价是O(n)的额外空间。这个实验也解释了为什么工业级排序库极少使用裸快排。无论是C的std::sort还是很多数据库的排序实现在快排的基础上都做了三数取中、小区间插入排序、以及针对重复元素的三路划分优化。纯粹的快排只是一个教学原型离工程可用还有距离。3.3 标准库qsort与手写实现的取舍C标准库提供了qsort函数它在很多平台上内部是优化的快速排序变体。用法很简单#include stdlib.h int compare_int(const void *a, const void *b) { int x *(const int *)a; int y *(const int *)b; return (x y) - (x y); } qsort(arr, n, sizeof(int), compare_int);注意比较函数的写法。这里用(x y) - (x y)而不是直接return x - y这是为了避免整数溢出。如果x很大y很小x - y可能溢出为负数导致比较结果错误。这个细节在面试和实际编码中都很容易踩坑。qsort的性能通常不错但有两个问题。一是它通过函数指针调用比较函数每次比较都有一次间接调用的开销在数据量大时这个开销不可忽略。二是qsort的实现细节取决于标准库无法保证是稳定排序。在商业项目中如果只是做一次普通的数组排序我建议直接用qsort省时省力。但如果是对性能敏感的热路径或者需要稳定排序、需要对特定数据分布做优化、或者运行环境缺少标准库那就值得自己写一个专用的排序函数。比如自己写一个针对int数组的快排去掉函数指针调用直接用比较实测在10万元素级别能比qsort快20%左右。4. 常见问题与排查实录4.1 边界条件与区间表示排序算法里最容易出bug的就是边界。我帮人review代码时见过最多的问题是for循环的终止条件多了个等号导致越界访问或者区间表示混乱一会儿左闭右闭、一会儿左闭右开自己把自己绕晕。我的建议是每个排序函数在实现前先明确区间表示。比如归并排序和快排我习惯用左闭右闭区间[left, right]这样递归调用的边界非常清晰。left right时表示区间为空或只有一个元素直接返回。习惯了这种写法后各种边界判断都变得有规律可循。另外一定要单独测试几个边界用例空数组、单元素数组、两个元素数组、全部相等的数组。这些用例在单元测试中都必须通过。我见过不少人排序代码在正常数据上完全没问题一跑空数组就崩原因就是没有在函数开头检查n 1。4.2 稳定性问题与字符串排序的实际联系稳定性这个词在理论课上可能只是一个定义但在真实业务里它直接决定结果对不对。举一个我做过的例子一个字符串排序需求需要先按长度升序排长度相同的按字典序排。最简单可靠的做法是先用字典序排一遍再用稳定排序按长度排一遍。第二次排序只要是稳定的长度相同的字符串就自然保持了第一次字典序的结果。如果第二次用的是不稳定排序比如选择排序那么长度相同的字符串顺序会乱掉整个结果就错了。这个例子里归并排序是最合适的选择。插入排序也可以只要数据量不大。但绝对不能选择排序或堆排序。这里的判断依据就是稳定性。你在选算法之前先回答一个问题数据里有没有多个字段需要依次排序有的话最后一轮排序或倒数第二轮必须用稳定排序。4.3 递归深度的隐患与栈溢出归并排序的递归深度固定是O(log n)这个很安全。快排就危险了最坏情况下递归深度能达到O(n)。我在一个实际项目中就遇到过对10万个逆序数据排序裸快排直接栈溢出崩溃。排查过程很曲折一开始以为是数据问题后来定位到递归深度超过了默认栈空间限制。解决方案有几种。最简单的是在partition之前随机打乱数据让退化概率降到极低。更妥当的做法是采用尾递归优化像我在2.6节展示的那样只递归处理较小的一半较大的一半用循环处理。最彻底的方案是换成堆排序或归并排序它们没有这种退化风险。在实际工程里如果数据来源不可控、无法保证分布特征我倾向于用堆排序兜底或者直接用迭代实现的非递归快排。4.4 交换操作中的隐蔽陷阱交换两个变量初学者最喜欢写经典的三行代码tmp a; a b; b tmp;这当然是正确的。但有些教材为了追求炫技教人用异或交换a ^ b; b ^ a; a ^ b;这个写法在大多数情况下也能工作但有一个致命陷阱如果a和b指向同一个内存地址异或三次会把值清零。这个坑在排序里真的会踩到。比如快排的partition中如果两个指针最终指向同一位置并触发交换用异或交换就会把那个位置的元素变0。我见过一个真实的案例一段用异或交换的快排代码在特定数据下总是莫名出现0排查了几天才找到原因。从此我在所有代码里都坚持用中间变量交换不追求这种没有实际收益的优化。你说它炫吗是挺炫的但它省不了多少性能却可能带来灾难性的后果。5. 实战项目中积累的几条核心建议写了这么多年代码排序算法用了一轮又一轮有几条建议想单独拎出来说。第一条背代码没有意义要背决策逻辑。面试官一问排序你不要直接开始背快排而是先说清楚你的选择依据。数据规模多大、数据特征如何、是否需要稳定、内存有没有限制把这四个问题回答完再写代码面试官对你的评价会完全不同。第二条一定要自己写一遍基准测试。不要以为理解了复杂度分析就够了实际跑一遍数据你才会真正明白常数因子对性能的影响有多大。我在没有亲自跑测试之前也以为堆排序挺快直到看到它被快排稳稳压了一头才真正理解了复杂度相同不等于性能相同这句话。第三条如果是在真实项目中优先用标准库不要自己造轮子。qsort能解决大部分问题。但你要保证自己造轮子的能力——面试会考嵌入式场景会用到而且理解排序原理本身就是一个工程师的基本素养。排序这类基础算法真的是写一次有一次的新体会。我每次回头重写这些代码都会发现自己能写出一点不同的优化。这可能就是基础算法的魅力它就在那里但你和它之间可以有无数种对话方式。