排序是数据结构里绕不开的一道坎也是面试手撕代码的高频考点。插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序这八种经典算法我最近用C语言完整过了一遍过程中踩了不少坑也把很多“当时背过后来忘了”的细节重新补了回来。这篇博客不打算讲段子就实实在在拆解这八种算法的思路、C语言实现要点、复杂度推导和实测选型经验给正在复习数据结构、准备面试笔试的同学一份能直接参考的整理。文章会先把八种排序按思路分组再逐个说原理和实现最后一节专门聊我实际调试时遇到过的典型问题。C语言版本我会给出关键代码片段方便对照复现。1. 先建立全局观八大排序到底在解决什么问题排序问题的本质是把一组无序数据按照关键字变成有序序列。看似简单但“怎么排得更快”“怎么省内存”“怎么保证相同元素的相对顺序不变”这三个问题衍生出了风格完全不同的算法家族。从策略上可以把这八种排序分成三类插入类直接插入排序、希尔排序。核心思想是“把新元素插入到已经有序的序列中”。交换类冒泡排序、快速排序。核心思想是“通过交换逆序元素逐步逼近有序”。选择类简单选择排序、堆排序。核心思想是“每次从剩余元素中选出最小/最大放到正确位置”。分治归并类归并排序。核心思想是“先拆到最小再有序合并”。非比较类计数排序。核心思想是“用值本身当数组下标直接统计频次”。学习时我习惯先看一张总表建立全局认知再逐个理解细节。排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入排序O(n^2)O(n^2)O(1)稳定希尔排序约O(n^1.3)O(n^2)O(1)不稳定简单选择排序O(n^2)O(n^2)O(1)不稳定堆排序O(n log n)O(n log n)O(1)不稳定冒泡排序O(n^2)O(n^2)O(1)稳定快速排序O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定计数排序O(n k)O(n k)O(k)稳定可稳定实现这张表建议记死尤其是稳定性和空间复杂度。很多场景题不考代码本身考的是“哪种排序适合哪种场景”后面我会详细展开。2. O(n^2)三兄弟插入、选择、冒泡这三个是排序算法的基础盘虽然时间复杂度不占优但实现简单、思维价值高。很多高级排序的优化思路都是从它们的弱点出发的。2.1 直接插入排序像整理扑克牌一样直接插入排序的思路我每次都用打扑克牌来类比。你抓牌的时候每拿到一张新牌会把它插到手里已经排好序的牌中合适的位置。代码里做的事就是从左到右扫描把当前元素和它前面的有序序列依次比较找到合适位置插入。核心代码片段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大的元素往后挪一位最后在空出来的位置上放key。这样每次插入只需要一次赋值动作比“交换到最终位置”少了约一半操作。时间复杂度方面最好情况是序列已经有序内层循环一次都不执行外层循环只做n-1次比较所以是O(n)。最坏情况是逆序第i次插入需要移动i次元素总移动次数为12...n-1也就是O(n^2)。我实际测试发现当数据量在1万左右且基本有序时直接插入排序的表现甚至比快排还好。原因在于它天然利用了“局部有序”的信息而快排这种分治算法在小规模数据上的递归开销比较明显。所以后面讲快排优化时会提到小区间用插入排序收尾就是这个道理。2.2 简单选择排序每次都挑最小的选择排序的思路非常直白第一轮遍历整个数组找出最小元素放到下标0第二轮从下标1开始找剩余最小元素放到下标1以此类推。它和冒泡排序最大的区别是交换次数明显更少。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; } } }注意一个容易被忽略的细节每次找到最小值后如果min_idx还是i本身就不需要交换。虽然交换一次是O(1)操作但能省就省。选择排序的时间复杂度无论数据状态如何都是O(n^2)。因为它必须完整扫描剩余部分才能确定最小值无法提前终止。它的比较次数是固定的n(n-1)/2但交换次数最多只有n-1次这是它和冒泡排序在常数性能上的差异。关于稳定性选择排序是不稳定的。比如数组[5, 5, 3]第一轮会选出3并和第一个5交换结果是[3, 5, 5]两个5的相对顺序发生了变化。虽然此时值一样看不出问题但如果排序对象是结构体、按某个字段排序这个特性就会影响结果。很多教材里对稳定性的定义讲得不够透彻我以为只有当“值相同且需要保持原有相对顺序”时才能体现差异。2.3 冒泡排序相邻对比大的沉底冒泡排序的思路是重复遍历数组比较相邻两个元素如果顺序错误就交换。每一轮遍历后最大的元素就像气泡一样“浮”到数组末尾。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)算法里最差的。3. 打破O(n^2)希尔排序与堆排序从O(n^2)到O(n log n)不是一步到位的。希尔排序是第一个突破O(n^2)的排序算法堆排序则是把选择排序的思维用数据结构加速到了极致。3.1 希尔排序插入排序的“跳步”升级版希尔排序的核心洞察是直接插入排序在数据基本有序时效率很高因为元素只需要少量移动就能到位。那能不能先把数据“粗排序”成基本有序再做一次精排于是就有了分组插入的思想。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; } } }这里的gap就是“步长”也叫增量。我用的增量序列是每次除以2这是最常见的实现方式。希尔排序的精髓在于随着gap不断缩小每次插入排序的数据量在增大但数据的有序程度也在提高两者一抵消整体效率远超O(n^2)。希尔排序的时间复杂度分析比较麻烦它取决于gap序列的选取。常用的gap序列有希尔原始序列n/2, n/4, ..., 1最坏O(n^2)但实际表现通常接近O(n^1.3)。Hibbard序列1, 3, 7, 15, 31, ..., 2^k-1最坏约O(n^1.5)。Sedgewick序列1, 5, 19, 41, 109, ...最坏约O(n^4/3)。实际工程里n/2这种简单折半的序列已经够用因为性能差异只有在数据量极大时才会显现。注意希尔排序是不稳定的因为相同元素可能被分到不同的组里分别插入跨越gap移动时会改变相对顺序。我有个体会希尔排序的代码逻辑和直接插入排序几乎一模一样唯一区别是相邻距离从1变成了gap。如果能把直接插入排序写熟希尔排序就是加一层gap循环的事。面试时如果要求手写这层递进关系是最容易说清楚的。3.2 堆排序用完全二叉树加速选择堆排序的思路依然是“每次选最大”但不同的是它不再通过线性扫描来找最大元素而是维护一个二叉堆结构让“找最大”变成O(1)“调整堆”变成O(log n)。整体复杂度就是O(n log n)。堆排序分成两个阶段建堆和反复输出堆顶。void sift_down(int arr[], int n, int i) { while (1) { 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) { break; } int tmp arr[i]; arr[i] arr[largest]; arr[largest] tmp; i largest; } } void heap_sort(int arr[], int n) { for (int i n / 2 - 1; i 0; i--) { sift_down(arr, n, i); } for (int end n - 1; end 0; end--) { int tmp arr[0]; arr[0] arr[end]; arr[end] tmp; sift_down(arr, end, 0); } }建堆时从最后一个非叶子节点开始下沉最后一个非叶子节点的下标是n/2 - 1。为什么是它因为数组下标从0开始二叉堆的最后一个节点下标是n-1它的父节点就是(n-1-1)/2也就是n/2-1。从它开始往前逐个下沉确保每个子树都满足大顶堆性质。这里有一个初学者很容易搞混的点建堆应该用“下沉”sift_down还是“上浮”sift_up答案是下沉。因为上浮操作是用于插入新节点时的向上调整而建堆时数组已经把所有数据都填满了只有根到叶方向不满足堆序只能从下往上逐个下沉调整。虽然理论上两种方式都能建出堆但下沉建堆的时间复杂度可以做到O(n)上浮建堆是O(n log n)。区别在哪里我后面问题排查部分会展开讲。每次输出堆顶后把最后一个元素放到堆顶再下沉这实际上是在用“取出最大元素”和“维护剩余堆结构”两个操作交替进行。最终数组从后往前逐步变成有序巧妙实现了原地排序空间复杂度O(1)。堆排序的稳定性也是不行的。比如[5, 8, 5]建堆后父子交换就可能让两个5的顺序发生变化。实际工作中如果要求稳定排序直接放弃堆排序选归并即可。4. 王者之争快排与归并要说八大排序里最常被拿来对比的一定是快速排序和归并排序。一个是不稳定的原地排序一个是稳定的非原地排序。两个都是O(n log n)级别但工程上的适用场景差异很大。4.1 快速排序选好基准分而治之快排的核心是“分区”。选定一个基准pivot把数组分成两部分左边都小于等于pivot右边都大于等于pivot然后递归处理左右两侧。我写了两种常见的分区实现实际效果对比如下Lomuto分区代码简洁pivot通常取最后一个元素用两个指针i和j扫描。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 p partition(arr, low, high); quick_sort(arr, low, p - 1); quick_sort(arr, p 1, high); } }Lomuto分区的逻辑很好理解i指向“最后一个小于等于pivot的位置”j负责遍历遇到比pivot小的元素就把它和i1位置交换最后把pivot放到i1的位置。这样写出来很直观也容易记住。但这里有个大坑如果数组已经有序pivot取最后一个元素会导致分区极度不平衡每次只分出n-1和1两个部分。递归深度变成n快速排序直接退化成O(n^2)而且递归次数过多还容易爆栈。所以工程实现通常不会傻傻取最后一个元素做pivot。常见的改进方案有三个我建议至少实现前两个三数取中取数组头部、中间、尾部三个元素的中位数作为pivot能有效避免大部分有序输入导致的退化。代码实现时先把中位数交换到最后一个位置再走普通Lomuto分区即可。随机pivot随机选一个下标作为pivot。对恶意构造的数据有防御效果但随机数生成本身有开销数据规模小时反而变慢。小区间用插入排序当递归区间长度小于某个阈值通常是10到20时直接调用插入排序。因为小规模数据上递归和分区开销占比太高插入排序的常数优势更明显。这是很多生产级快排的实现策略。快排虽然平均复杂度是O(n log n)但常数因子比其他O(n log n)算法小配合原地交换内存访问模式对CPU缓存也比较友好所以实际工程中它是通用排序最强的竞争者。稳定性方面快排在分区过程中会发生跨越式的交换相同的元素可能被交换到相对顺序改变所以不稳定。4.2 归并排序先拆到底再稳稳合并归并排序的思路是另一个极端先把数组从中间一分为二递归排序左右两部分然后把两个有序子数组合并成一个有序数组。它的合并过程保证稳定因为合并时遇到相等的元素优先取左半部分的元素相对顺序不会变。void merge(int arr[], int left, int mid, int right, int temp[]) { int i left; int j mid 1; int k left; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int m left; m right; m) { arr[m] temp[m]; } } void merge_sort(int arr[], int left, int right, int temp[]) { if (left right) { return; } int mid left (right - left) / 2; merge_sort(arr, left, mid, temp); merge_sort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); }我在函数声明里多传了一个temp数组这是实现上的一个重要细节。如果每次递归都临时malloc一个临时数组频繁分配内存的开销非常可观。正确做法是在入口函数里一次性malloc好和原数组等长的temp递归过程只负责使用。归并排序的时间复杂度是稳定的O(n log n)无论数据怎么分布都一样。它没有快排那种退化风险空间复杂度O(n)是它的主要劣势。当数据规模很大、内存紧张时归并排序的竞争力会下降。归并排序在工程里有个典型应用场景——外部排序。当数据量大到无法全部加载进内存时只能对磁盘里的分块数据分别排序再用多路归并合并。这时候归并排序的稳定性、顺序读取模式都是很大的优势。我还想提一个小点归并排序的写法里求中点用left (right - left) / 2而不是(left right) / 2是因为后者在left right很大的时候可能溢出。这种细节在C语言里必须注意。5. 不比较也能排计数排序计数排序和前面七种排序有本质区别它完全不需要比较元素之间的大小。前提条件是数据必须是非负整数且取值范围有限不会太分散。思路是这样的先找到数组中的最大值max然后开一个长度为max1的计数数组count。遍历原数组统计每个值出现的次数使count[v]表示值v出现的次数。最后按顺序遍历count把每个值输出count[v]次就能得到一个有序序列。void counting_sort(int arr[], int n) { if (n 1) { return; } int max arr[0]; for (int i 1; i n; i) { if (arr[i] max) { max arr[i]; } } int *count (int *)calloc(max 1, sizeof(int)); for (int i 0; i n; i) { count[arr[i]]; } int idx 0; for (int v 0; v max; v) { while (count[v]-- 0) { arr[idx] v; } } free(count); }这是计数排序最朴素的版本时间复杂度是O(n k)k是值的范围。如果max是几百万而n只有几百空间浪费会非常离谱这种场景不适合用计数排序。上面这个版本直接用下标对应值虽然简单但它有个缺点不稳定的。因为在从count数组回填时相同的元素之间没有先后之分。实际很多题目要求计数排序保持稳定性这时要用前缀和版本void stable_counting_sort(int arr[], int n, int max) { int *count (int *)calloc(max 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; 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); }前缀和版本为什么能保证稳定因为count经过前缀和累加后count[v]表示“小于等于v的元素个数”。从右往左遍历原数组某个元素arr[i]在输出数组中的位置就是count[arr[i]] - 1然后count[arr[i]]减一。这样做的本质是相同值的元素在输出时会按照原数组中从右到左的顺序依次放置逆序回填后原顺序被完整保留。计数排序的实际应用场景其实不少。比如成绩排名中分数范围是0到100分无论考生有多少人k都只有101这时候计数排序效率碾压所有比较排序。再比如对象按照年龄排序年龄范围0到150也适合用计数排序。但要注意计数排序对负数不友好因为数组下标不能是负数。处理办法是加一个偏移量最小值是min就开max-min1的数组下标从0对应min这样通用性会强很多。6. 八种排序的实测选型参考光会背代码还不够面试里更常问的是“什么时候应该选哪种排序”。我把实际调试中观察到的经验整理成几条选型建议。6.1 数据规模与形态是首要考量数据规模对排序算法选择的影响非常直接数据量小于1万直接插入排序和冒泡排序完全够用代码简单不容易出错。尤其是数据基本有序时插入排序表现出乎意料地好。数据量1万到10万希尔排序是个不错的折中。它实现简单、无需额外空间性能虽然不如快排但差距没有想象中那么大。数据量10万以上快排、归并排序、堆排序才是主流选择。快排最快但可能退化归并稳定但占用内存堆排序没有额外空间但常数较大。数据取值范围小且密集计数排序是首选O(n)级别的复杂度直接秒杀所有比较排序。我做过一个简单的对比实验10万个随机整数快排约20毫秒归并约30毫秒堆排序约50毫秒希尔排序约200毫秒插入排序约3000毫秒不同机器差异较大但相对关系稳定。这个数据能直观反映出常数的差距。6.2 稳定性要求怎么取舍稳定性在排序算法里是个经常被忽略但实际中很关键的性质。典型场景是学生先按班级排序再按成绩排序要求成绩相同的学生保持班级顺序不变。如果第二次排序是稳定的就能达到这个效果。SQL中multiply-order-by的底层实现也依赖稳定排序。需要稳定排序时选项其实只有两个归并排序和直接插入排序。快排、堆排、希尔、选择都是不稳定的直接用会导致第二次排序丢掉第一次排序的信息。如果要求稳定、又要求O(n log n)那基本只能选归并排序。很多语言内置的稳定排序底层就是归并排序或Timsort这种改进变体。6.3 额外空间不能忽视空间复杂度排序时原地排序空间O(1)在嵌入式、单片机这些内存受限的场景中几乎是硬性要求。堆排序和快排是原地排序的代表归并排序虽然性能好但n个元素的额外空间在32K内存的单片机上可能直接撑爆。计数排序的额外空间取决于数据范围而不是数据量这一条也要单独评估。如果数据是链表归并排序反而是天然合适的因为链表不需要额外空间即可完成合并这是它的又一个优势场景。7. 实操中的问题排查实录写这八种排序的C语言实现时我至少debug了四五个小时踩过的坑很有代表性问题。我把它们按出现频率排序写下来给大家避坑。7.1 快速排序递归过深导致栈溢出我最开始写的快排直接用最右元素当pivot然后拿一个已经有序的数组测试。结果还没排完程序就直接段错误。原因很简单有序数组每轮分区后pivot都在最右边递归区间只减少1递归深度达到n栈空间根本扛不住。解决方案就是三数取中或者随机选pivot。我实测三数取中对“几乎有序”的数据效果显著递归深度从n降到了log n级别。还有一个容易忽略的问题是递归函数里在归并排序时如果不小心传错了区间边界也可能造成无限递归或栈溢出。7.2 堆排序的建堆到底该用下沉还是上浮这个问题我专门分析过。建堆时如果从堆顶开始把每个元素上浮也就是每插入一个元素就调整一个小堆整体复杂度是O(n log n)。但更优的做法是从最后一个非叶子节点开始对所有非叶子节点执行下沉整体复杂度可以证明是O(n)。为什么下沉建堆是O(n)因为高度越低的节点数量越多而下沉操作消耗的时间正比于节点的高度。求和后是一个调和级数的量级收敛到O(n)。上浮操作则相反每个节点的上浮代价是消耗在对数深度上所有节点一累加就是O(n log n)。实际代码里我犯过的错误是从0开始到n/2-1逐个上浮写出来的代码虽然也能排序但大数据量下明显偏慢。这个细节就是堆排序性能的分水岭。7.3 归并排序的临时数组重复分配问题我最开始写归并排序时在递归函数里每次malloc临时数组。10万随机数据测试竟然比快排慢了近10倍。原因就是频繁调用malloc和free在堆上分配内存的开销远远大于实际排序计算。解决方法是在主函数里malloc一次把指针传进递归函数所有递归层共享同一个临时数组。这个优化让我实测性能提升了一个数量级属于归并排序实现里最重要的细节之一。7.4 C语言里交换函数要传指针这个坑对新手来说几乎是必踩的。C语言函数参数是值传递如果写一个swap函数只传int变量进去交换只发生在函数内部外部数组完全没变。所以要么在排序代码里直接写交换要么用指针void swap(int *a, int *b) { int tmp *a; *a *b; *b tmp; }调用时写swap(arr[i], arr[j])。如果忘了取地址排序结果会静默出错而且不报编译错误排查起来特别折磨人。我建议在工程中把交换封装成宏或内联函数减少手写出错概率。7.5 用随机数据验证排序结果写完所有排序后我建议不要只跑一组有序或逆序数据最好跑一组随机数据验证正确性再跑几组边界数据。我的验证脚本大概是这样的空数组和单元素数组所有排序都能直接返回不崩溃。逆序数组检验排序算法的边界处理能力。大量重复元素数组检验稳定性相关逻辑是否正确值相同时不会死循环。随机生成100组数据对比排序前后的规模和有序性断言确保没有偶发越界。C语言不像高级语言那样有现成的bounds checking数组越界往往不立即崩溃而是悄悄破坏内存最后在某次看似无关的操作中爆发。所以测试时推荐用AddressSanitizer这类工具能直接定位越界语句。8. 最后分享一个实用的调试小技巧写排序算法时我强烈建议在每次循环或递归的关键节点打印出数组状态把中间结果可视化。比如写堆排序时先打印建堆后的完整数组写快排时打印每次分区后的结果。排序算法的逻辑比普通业务代码更抽象单靠脑内模拟很难定位问题。另外一个很有效的方法是“规模递减调试法”先用3个元素的数组手动推导每一步再用5个、10个元素逐步扩大。小规模数据下你能信手画出每一步的中间状态一旦和大规模输出对不上就能快速锁定是哪一步出了问题。关于八大排序我已前前后后写了很多遍每写一遍都会有新的理解。这次完整整理一份C语言实现版既是给自己做个索引也是给正在啃数据结构的同学一份能跑起来、能对照的参考。排序算法的价值不止在于“能排出来”更在于它们背后浓缩了分治、堆、稳定性、复杂度分析这些贯穿整个数据结构的核心思维。把这八种吃透后面再学高级数据结构和算法会顺手很多。
