数组和排序这两件事在C语言里有多基础不用我多说。数组是C语言里最常用的连续存储容器而排序算法几乎就是算法学习的“普通话”。很多初学者学完数组、循环、函数之后第一道真正需要“动脑子”的练习题就是给一个乱序数组排个序。我当时学的时候就是在翁恺老师的C语言练习里反复写这些排序写到后来发现这五个基础算法不只是应付考试它们对理解递归、指针、复杂度、稳定性这些概念都有直接帮助。这篇文章围绕数组这一数据结构把五大基础排序算法——冒泡排序、选择排序、插入排序、快速排序、归并排序——全部用C语言手写一遍。每个算法我都会给出完整代码讲清楚为什么这么写边界条件怎么处理哪些地方容易踩坑以及实测下来是什么表现。适合刚学完数组和函数、想系统整理排序算法的初学者也适合面试前快速复习或者工作中需要自己实现排序逻辑的同学参考。1. 数组与排序先厘清几个基础概念1.1 数组的存储结构与排序对象的形态C语言的数组在内存中是连续存储的一维数组的元素按下标0到n-1排列。排序算法的输入本质上就是一个一维数组我们要做的是在数组内部改变元素顺序所以函数参数通常写成void sort(int arr[], int n)的形式。这里有个C语言特有的坑数组名作为参数传递时会“退化”为指针函数里其实拿不到数组长度所以必须显式传入n。如果你写的排序函数内部还想着sizeof(arr)/sizeof(arr[0])那结果一定是错的因为这个arr已经是指针了。数组初始化和声明也是个常见入门问题。比如int a[10] {0};会把所有元素初始化为0而int a[10];里面的值是不确定的。在排序前务必确认数组里存的是有效数据否则你排出来的可能是“垃圾”。另外虽然排序主要针对一维数组但二维数组、指针数组在某些场景下也会涉及排序逻辑比如指针数组存字符串后按字符串长度排序。不过核心思路相同只是比较元素的方式不同。本文先用int一维数组把算法本身讲透。1.2 复杂的度和稳定性先记住一个表在讲具体算法之前我建议先把下面这个速查表记下来然后每讲完一个算法你回过来看它理解会更深。排序算法最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n)O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定插入排序O(n)O(n^2)O(n^2)O(1)稳定快速排序O(n log n)O(n log n)O(n^2)O(log n)递归栈不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定稳定性这个概念对于很多初学者来说容易忽略。它指的是如果数组里有两个值相等的元素排序后它们的相对顺序是否保持不变。能保持就叫稳定不能就叫不稳定。比如按成绩排序后如果还要保留原本的学号顺序稳定排序就比较有用。后面我会在具体算法里解释为什么有的稳定、有的不稳定。空间复杂度这里快排的O(log n)是递归调用栈消耗归并的O(n)是临时数组开销其余三个原地排序没有额外大块内存。2. 冒泡排序最直观的交换排序2.1 算法思想与代码实现冒泡排序的思想最接近人的直觉从第一个元素开始相邻两个元素两两比较如果前一个比后一个大就交换位置。这样一轮走完最大的元素就像气泡一样冒到了数组最后。第二轮再对前面n-1个元素做同样的事第二大元素会到倒数第二位置。重复n-1轮整个数组就排好了。我平时喜欢在代码里加一个swapped标志用于检测某一轮是否发生过交换。如果某一轮从头到尾都没有交换说明数组已经有序提前结束循环。这个优化在最好情况下可以把时间复杂度降到O(n)。#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; } } }这段代码里有几个点值得拆开讲。外层循环i控制的是“已经排好末尾多少个元素”。第一轮结束时末尾1个元素定住第二轮结束时末尾2个元素定住所以最多n-1轮。内层循环的上界是n - 1 - i因为末尾i个元素已经有序不需要再参与比较。如果不减i虽然也可能排好但会做大量重复比较而且当i0时j到n-1arr[j1]访问到arr[n]越界程序可能直接崩溃。2.2 实测心得与常见误区我拿随机生成的10000个整数的数组测过冒泡排序在没有优化的情况下大概要0.15秒到0.2秒加上swapped优化后随机数据的耗时差别不大但对本来有序的数据几乎瞬间完成。它的优点是代码简单、稳定、好理解缺点是平均和最坏都是O(n^2)数据量一大就吃不消。所以冒泡排序实战价值不高主要用在学习阶段。最常见的误区有两个。第一个是交换变量时写成arr[j] arr[j1]; arr[j1] arr[j];结果两个元素变成相同值。交换必须用临时变量tmp或者使用异或技巧但不推荐可读性差。第二个误区是忘了数组下标从0开始把j n - 1 - i写成j n - i导致比较范围扩大不仅慢还可能越界。建议初学者写完代码后先用n1、n2、n3的小数组测试再验证大数据。3. 选择排序简洁但不稳定的排序3.1 算法思想与代码实现选择排序的思路也很简单每一轮在未排序区间里找到最小元素的下标然后把它和未排序区间的第一个元素交换。第一轮找到全局最小值放到arr[0]第二轮在arr[1]到arr[n-1]里找最小值放到arr[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; } } }选择排序的比较次数是固定的n(n-1)/2无论数据是否有序这个数不变。所以它的时间复杂度没有最好最坏之分都是O(n^2)。但交换次数最多只有n-1次这一点比冒泡好很多在某些交换代价很高的场景比如元素是大型结构体反而可能更实用。3.2 边界情况与优化思路选择排序不稳定这点很多人想不明白。我举个例子数组[5, 8, 5, 2]第一轮找到最小值2在下标3和下标0的5交换变成[2, 8, 5, 5]。原来两个5第一个5下标0跑到了第二个5下标2的后面相对顺序变了所以不稳定。写选择排序时最容易忽略的是当min_idx i时不需要交换虽然交换也没什么问题但属于无意义操作加一个判断更严谨。另外有一种优化思路是每一轮同时找出最小值和最大值最小值放前面最大值放后面这样排序轮数可以减少一半但代码里的边界处理复杂度明显增加容易写错。我个人不推荐初学者用这种优化老老实实写标准版就好。4. 插入排序像整理扑克牌一样4.1 算法思想与代码实现插入排序是我个人最喜欢的一个排序算法因为它和生活经验完全对应打扑克牌的时候你抓一张新牌会把它插入到手里已经有序的牌堆里的正确位置。插入排序就是从左到右把每个元素往前插入到前面有序序列的合适位置。它处理数组前i个元素时前i-1个元素已经有序第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; } }这里有两个关键点。第一先用key保存当前待插入的元素因为后面移动元素时会覆盖arr[i]。第二移动过程不是交换而是从后往前把比key大的元素逐个后移一位最后把key放到空出来的位置。整个过程是稳定的因为遇到等于key的元素时while循环条件arr[j] key为假不会越过相等元素相等元素的相对顺序得以保留。4.2 适用场景与性能细节插入排序在对近乎有序的数组排序时表现异常好最好情况下只需要O(n)次比较。比如数组原来是[1, 2, 3, 5, 4, 6]只有5和4是逆序的插入排序几乎两轮就搞定。很多标准库的快排实现会在递归到小区间比如小于16个元素时改用插入排序就是因为小规模数据下插入排序的常数小、开销低。写插入排序最常见的坑是while循环的短路顺序。while (j 0 arr[j] key)里的j 0必须写在前面因为C语言运算符从左往右求值一旦j 0后面的arr[j]就不会执行了。如果写成while (arr[j] key j 0)当j变成-1时程序会先访问arr[-1]这在C语言里是未定义行为可能读到垃圾值也可能直接段错误。我在实际调试中就见过这种写法导致的诡异崩溃排查了很久。5. 快速排序分治思想的代表5.1 递归实现与分区逻辑快速排序利用分治思想从数组里选一个基准值pivot把数组分成两部分左边所有元素不大于基准右边所有元素不小于基准然后递归对左右两部分排序。它的核心难度在于partition分区这一步怎么写得高效且不越界。我这里用经典的“挖坑填数法”代码比较直观。int partition(int arr[], int low, int high) { int pivot arr[low]; int i low; int j high; while (i j) { while (i j arr[j] pivot) { j--; } arr[i] arr[j]; while (i j arr[i] pivot) { i; } arr[j] arr[i]; } arr[i] pivot; return i; } void quick_sort(int arr[], int low, int high) { if (low high) { int pos partition(arr, low, high); quick_sort(arr, low, pos - 1); quick_sort(arr, pos 1, high); } }解释一下partition的流程。一开始把arr[low]作为基准值此时arr[low]相当于一个“坑”。先从右往左找第一个小于基准的元素填到坑里于是arr[j]变成新坑然后从左往右找第一个大于基准的元素填到右边的坑。循环直到i和j相遇最后把基准值放进相遇位置。这样一轮下来基准值左边都小于等于它右边都大于等于它。调用示例是quick_sort(arr, 0, n-1)区间是闭区间。如果你写成quick_sort(arr, 0, n)那partition处理时访问arr[n]就会越界。这是我反复提醒初学者的一条快速排序的所有边界都是“包含端点”的递归子区间分别是[low, pos-1]和[pos1, high]不能把pos再包含进去。5.2 退化风险与优化技巧快速排序的平均时间复杂度是O(n log n)但最坏情况是O(n^2)。当数组已经有序而基准值又总是选第一个元素时每次partition都只能把区间分割成1和n-1两部分递归树退化为一条链性能直接崩掉。为了规避这个问题工程上常用“三数取中”策略从arr[low]、arr[mid]、arr[high]三个位置取中间值作为基准并把它交换到low位置。这样能极大降低有序数据下的退化概率。另一种方法是随机选基准但随机数生成本身有开销。递归深度也是快速排序的隐患。最坏情况下递归深度达到n对超大数组可能耗尽函数调用栈空间。我在一个嵌入式项目中就遇到过快速排序排序几万条记录时程序崩溃查到最后就是递归太深把有限的栈空间用光了。如果你的运行环境栈很小或者数据量不可控要么改用非递归快排用栈模拟递归要么直接换归并排序。但大部分桌面环境下普通几万个数用快排是没问题的。6. 归并排序稳定但需要额外空间6.1 算法思想与代码实现归并排序也是分治。它将数组不断二分直到每个子区间只有一个元素然后把两个有序子区间合并成一个有序区间。这个过程需要额外的临时数组来存储合并结果。归并排序的优点是稳定且时间永远是O(n log n)缺点是需要O(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 (int p left; p right; p) { arr[p] tmp[p]; } } void merge_sort(int arr[], int tmp[], int left, int right) { if (left right) { 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); } }这里mid的计算用了left (right - left) / 2而不是(left right) / 2虽然对普通int数组后者也不会溢出但这是一个好习惯尤其是当left和right很大时两者相加可能溢出int范围。合并时的关键判断是arr[i] arr[j]这个“等于号”决定了归并排序的稳定性。如果写成当arr[i]等于arr[j]时会把右边的元素先放入tmp左边相同值的元素相对顺序就变了排序就变成不稳定。我专门拿[3, 1, 2, 3]这样的用例测试过写成后两个3的顺序确实会颠倒。6.2 内存分配与边界检查归并排序需要一个临时数组tmp。常见错误是在递归函数里频繁分配和释放tmp这样不仅低效还可能因为多次malloc导致内存碎片。正确做法是在对外接口里一次性分配好临时数组再调用递归的merge_sort。#include stdlib.h void merge_sort_wrapper(int arr[], int n) { if (n 0) { return; } int *tmp (int *)malloc(n * sizeof(int)); if (tmp NULL) { return; } merge_sort(arr, tmp, 0, n - 1); free(tmp); }同时要注意n0或n1的情况前者malloc(0)可能返回非NULL也可能返回NULL但都不该去访问内存后者递归里leftright直接返回。如果你在主程序里直接调用merge_sort(arr, tmp, 0, n)那也是错的因为rightn超出了有效下标范围循环会访问arr[n]。归并排序所有区间都是闭区间我建议把对外接口单独封装让调用者只传数组和长度避免搞混起始位置。7. 五大排序横向对比与选型建议7.1 复杂度与稳定性速查表我把前面零散提到的信息整理成一张表方便你随时查阅。排序算法最好平均最坏空间稳定冒泡排序O(n)O(n^2)O(n^2)O(1)是选择排序O(n^2)O(n^2)O(n^2)O(1)否插入排序O(n)O(n^2)O(n^2)O(1)是快速排序O(n log n)O(n log n)O(n^2)O(log n)否归并排序O(n log n)O(n log n)O(n log n)O(n)是这张表里最容易混淆的是“最坏”和“空间”。快速排序最坏O(n^2)可能让人意外但只要你理解了退化原因就明白应该避免在有序数组上直接选首个元素做基准。归并排序时间稳定但因为要拷贝到临时数组再拷回来实际常数因子比快速排序大所以数据量相同时归并排序往往比快排稍慢除非要求稳定性。7.2 根据场景选择算法我的经验是选排序算法不能只看复杂度还要看数据规模、是否要求稳定、内存限制、是否几乎有序。数据量小于50时插入排序往往比快速排序还快因为它的常数小不需要递归。数据量在几千到几百万且不要求稳定性时快速排序是默认选择。数据量大且业务上要求稳定时归并排序更合适。如果数据近乎有序插入排序是最好的选择。如果内存极其有限只能原地排序那就只能在冒泡、选择、插入、快排里选再综合考虑稳定性。另外C标准库自带qsort它内部是经过精心调优的快速排序可能混合插入排序绝大多数情况下我们不需要自己写快排。但自己手写一遍这五个算法意义在于理解它的缺陷和优化点这样用qsort时你能知道为什么它的参数里要传入比较函数为什么它的复杂度不是绝对有保障。8. 数组排序实战中的常见问题与排查8.1 数组越界与下标错位C语言数组越界是不会自动提示的这是新手最容易栽的跟头。比如冒泡排序里内层循环如果写j n - i当i为0时j最大到n-1访问arr[j1]就是arr[n]越界。再比如快速排序递归调用时把high写成npartition里就会访问arr[n]。排查这类问题我建议三个办法先用n1和n2的小数组跑一遍在排序函数入口打印low、high和n的值观察是否合理如果用GCC编译可以加-fsanitizeaddress它能直接报告越界位置比你自己盯代码高效得多。还有一种很隐蔽的错误排序函数的参数是数组和长度但你在循环里把长度写成了sizeof(arr)/sizeof(arr[0])。就像前面说的数组参数退化成指针sizeof(arr)是一个指针的大小通常是8字节除以4以后得到2导致循环只处理前两个元素。这种错误在64位系统上尤其常见因为指针大小和int大小不一样。8.2 递归栈溢出与排序性能陷阱快速排序和归并排序都用递归。快排在极端情况下递归深度等于n如果n是十万而环境栈空间只有几百KB每层递归即使只占用几十字节也可能栈溢出。归并排序的递归深度固定为log2(n)一般不会栈溢出但它需要额外数组分配。我建议在使用递归排序时给数据规模设一个上限或者提前对数组做一次“是否明显有序”的检测避开最坏情况。排查这类问题可以在main函数里设置一个较大的数组比如100000个元素连续多次调用排序函数观察是否崩溃。如果崩溃优先怀疑栈溢出可以临时把数组规模降到10000试一试。对于归并排序还要检查malloc的返回值返回NULL时不要直接往下走否则解引用空指针必挂。我在Windows和Linux下都遇到过系统资源紧张导致malloc失败的情况所以封装函数里一定要判断。8.3 排序函数的工程化封装要点写实际可用的排序模块时我通常会把内部实现和对外接口分开。比如冒泡排序直接暴露bubble_sort(arr, n)没问题但快速排序和归并排序会暴露复杂参数low/high或tmp这时封装一层能有效防止调用者传错。另外数组里的元素类型不总是int如果你要排序结构体数组只要把比较逻辑抽出来单独写一个函数或者写成宏就能复用排序框架。C语言里最灵活的是函数指针但作为入门阶段的五个基础算法先用int把逻辑吃透更重要。我还想提一个容易被忽略的问题排序过程中如果数组里存在大量重复元素快速排序的性能也会退化。因为经典的partition把等于基准的元素分散到两侧导致区间分割不均匀。解决方法是三路快排把数组分成小于、等于、大于基准的三部分等于基准的不用再递归。这个思路可以作为进阶练习但它已经超出了基础五排序的范围。建议你先把基础算法写熟再去研究三路快排、堆排序这些扩展内容。最后再分享一点我的个人经验这几个算法我前前后后写了不下几十遍每次写都还能发现一些细节问题。我现在写排序时会习惯性在测试函数里用一个print_array函数每次排序后打印前几个和后几个元素快速确认没有越界或丢失数据。你去看很多开源代码里面排序函数旁边都会带一个简单的验证数组就是这个原因。另外我强烈建议你把每个算法都亲自敲一遍不要复制粘贴敲的过程中才能注意到变量名、边界条件和交换逻辑。等你手写熟之后再回头用qsort处理实际问题会轻松很多。排序是算法的起点也是理解C语言内存和指针的一扇门希望这篇文章能帮你把这扇门推开。
数组和排序这两件事在C语言里有多基础不用我多说。数组是C语言里最常用的连续存储容器而排序算法几乎就是算法学习的“普通话”。很多初学者学完数组、循环、函数之后第一道真正需要“动脑子”的练习题就是给一个乱序数组排个序。我当时学的时候就是在翁恺老师的C语言练习里反复写这些排序写到后来发现这五个基础算法不只是应付考试它们对理解递归、指针、复杂度、稳定性这些概念都有直接帮助。这篇文章围绕数组这一数据结构把五大基础排序算法——冒泡排序、选择排序、插入排序、快速排序、归并排序——全部用C语言手写一遍。每个算法我都会给出完整代码讲清楚为什么这么写边界条件怎么处理哪些地方容易踩坑以及实测下来是什么表现。适合刚学完数组和函数、想系统整理排序算法的初学者也适合面试前快速复习或者工作中需要自己实现排序逻辑的同学参考。1. 数组与排序先厘清几个基础概念1.1 数组的存储结构与排序对象的形态C语言的数组在内存中是连续存储的一维数组的元素按下标0到n-1排列。排序算法的输入本质上就是一个一维数组我们要做的是在数组内部改变元素顺序所以函数参数通常写成void sort(int arr[], int n)的形式。这里有个C语言特有的坑数组名作为参数传递时会“退化”为指针函数里其实拿不到数组长度所以必须显式传入n。如果你写的排序函数内部还想着sizeof(arr)/sizeof(arr[0])那结果一定是错的因为这个arr已经是指针了。数组初始化和声明也是个常见入门问题。比如int a[10] {0};会把所有元素初始化为0而int a[10];里面的值是不确定的。在排序前务必确认数组里存的是有效数据否则你排出来的可能是“垃圾”。另外虽然排序主要针对一维数组但二维数组、指针数组在某些场景下也会涉及排序逻辑比如指针数组存字符串后按字符串长度排序。不过核心思路相同只是比较元素的方式不同。本文先用int一维数组把算法本身讲透。1.2 复杂的度和稳定性先记住一个表在讲具体算法之前我建议先把下面这个速查表记下来然后每讲完一个算法你回过来看它理解会更深。排序算法最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n)O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定插入排序O(n)O(n^2)O(n^2)O(1)稳定快速排序O(n log n)O(n log n)O(n^2)O(log n)递归栈不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定稳定性这个概念对于很多初学者来说容易忽略。它指的是如果数组里有两个值相等的元素排序后它们的相对顺序是否保持不变。能保持就叫稳定不能就叫不稳定。比如按成绩排序后如果还要保留原本的学号顺序稳定排序就比较有用。后面我会在具体算法里解释为什么有的稳定、有的不稳定。空间复杂度这里快排的O(log n)是递归调用栈消耗归并的O(n)是临时数组开销其余三个原地排序没有额外大块内存。2. 冒泡排序最直观的交换排序2.1 算法思想与代码实现冒泡排序的思想最接近人的直觉从第一个元素开始相邻两个元素两两比较如果前一个比后一个大就交换位置。这样一轮走完最大的元素就像气泡一样冒到了数组最后。第二轮再对前面n-1个元素做同样的事第二大元素会到倒数第二位置。重复n-1轮整个数组就排好了。我平时喜欢在代码里加一个swapped标志用于检测某一轮是否发生过交换。如果某一轮从头到尾都没有交换说明数组已经有序提前结束循环。这个优化在最好情况下可以把时间复杂度降到O(n)。#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; } } }这段代码里有几个点值得拆开讲。外层循环i控制的是“已经排好末尾多少个元素”。第一轮结束时末尾1个元素定住第二轮结束时末尾2个元素定住所以最多n-1轮。内层循环的上界是n - 1 - i因为末尾i个元素已经有序不需要再参与比较。如果不减i虽然也可能排好但会做大量重复比较而且当i0时j到n-1arr[j1]访问到arr[n]越界程序可能直接崩溃。2.2 实测心得与常见误区我拿随机生成的10000个整数的数组测过冒泡排序在没有优化的情况下大概要0.15秒到0.2秒加上swapped优化后随机数据的耗时差别不大但对本来有序的数据几乎瞬间完成。它的优点是代码简单、稳定、好理解缺点是平均和最坏都是O(n^2)数据量一大就吃不消。所以冒泡排序实战价值不高主要用在学习阶段。最常见的误区有两个。第一个是交换变量时写成arr[j] arr[j1]; arr[j1] arr[j];结果两个元素变成相同值。交换必须用临时变量tmp或者使用异或技巧但不推荐可读性差。第二个误区是忘了数组下标从0开始把j n - 1 - i写成j n - i导致比较范围扩大不仅慢还可能越界。建议初学者写完代码后先用n1、n2、n3的小数组测试再验证大数据。3. 选择排序简洁但不稳定的排序3.1 算法思想与代码实现选择排序的思路也很简单每一轮在未排序区间里找到最小元素的下标然后把它和未排序区间的第一个元素交换。第一轮找到全局最小值放到arr[0]第二轮在arr[1]到arr[n-1]里找最小值放到arr[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; } } }选择排序的比较次数是固定的n(n-1)/2无论数据是否有序这个数不变。所以它的时间复杂度没有最好最坏之分都是O(n^2)。但交换次数最多只有n-1次这一点比冒泡好很多在某些交换代价很高的场景比如元素是大型结构体反而可能更实用。3.2 边界情况与优化思路选择排序不稳定这点很多人想不明白。我举个例子数组[5, 8, 5, 2]第一轮找到最小值2在下标3和下标0的5交换变成[2, 8, 5, 5]。原来两个5第一个5下标0跑到了第二个5下标2的后面相对顺序变了所以不稳定。写选择排序时最容易忽略的是当min_idx i时不需要交换虽然交换也没什么问题但属于无意义操作加一个判断更严谨。另外有一种优化思路是每一轮同时找出最小值和最大值最小值放前面最大值放后面这样排序轮数可以减少一半但代码里的边界处理复杂度明显增加容易写错。我个人不推荐初学者用这种优化老老实实写标准版就好。4. 插入排序像整理扑克牌一样4.1 算法思想与代码实现插入排序是我个人最喜欢的一个排序算法因为它和生活经验完全对应打扑克牌的时候你抓一张新牌会把它插入到手里已经有序的牌堆里的正确位置。插入排序就是从左到右把每个元素往前插入到前面有序序列的合适位置。它处理数组前i个元素时前i-1个元素已经有序第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; } }这里有两个关键点。第一先用key保存当前待插入的元素因为后面移动元素时会覆盖arr[i]。第二移动过程不是交换而是从后往前把比key大的元素逐个后移一位最后把key放到空出来的位置。整个过程是稳定的因为遇到等于key的元素时while循环条件arr[j] key为假不会越过相等元素相等元素的相对顺序得以保留。4.2 适用场景与性能细节插入排序在对近乎有序的数组排序时表现异常好最好情况下只需要O(n)次比较。比如数组原来是[1, 2, 3, 5, 4, 6]只有5和4是逆序的插入排序几乎两轮就搞定。很多标准库的快排实现会在递归到小区间比如小于16个元素时改用插入排序就是因为小规模数据下插入排序的常数小、开销低。写插入排序最常见的坑是while循环的短路顺序。while (j 0 arr[j] key)里的j 0必须写在前面因为C语言运算符从左往右求值一旦j 0后面的arr[j]就不会执行了。如果写成while (arr[j] key j 0)当j变成-1时程序会先访问arr[-1]这在C语言里是未定义行为可能读到垃圾值也可能直接段错误。我在实际调试中就见过这种写法导致的诡异崩溃排查了很久。5. 快速排序分治思想的代表5.1 递归实现与分区逻辑快速排序利用分治思想从数组里选一个基准值pivot把数组分成两部分左边所有元素不大于基准右边所有元素不小于基准然后递归对左右两部分排序。它的核心难度在于partition分区这一步怎么写得高效且不越界。我这里用经典的“挖坑填数法”代码比较直观。int partition(int arr[], int low, int high) { int pivot arr[low]; int i low; int j high; while (i j) { while (i j arr[j] pivot) { j--; } arr[i] arr[j]; while (i j arr[i] pivot) { i; } arr[j] arr[i]; } arr[i] pivot; return i; } void quick_sort(int arr[], int low, int high) { if (low high) { int pos partition(arr, low, high); quick_sort(arr, low, pos - 1); quick_sort(arr, pos 1, high); } }解释一下partition的流程。一开始把arr[low]作为基准值此时arr[low]相当于一个“坑”。先从右往左找第一个小于基准的元素填到坑里于是arr[j]变成新坑然后从左往右找第一个大于基准的元素填到右边的坑。循环直到i和j相遇最后把基准值放进相遇位置。这样一轮下来基准值左边都小于等于它右边都大于等于它。调用示例是quick_sort(arr, 0, n-1)区间是闭区间。如果你写成quick_sort(arr, 0, n)那partition处理时访问arr[n]就会越界。这是我反复提醒初学者的一条快速排序的所有边界都是“包含端点”的递归子区间分别是[low, pos-1]和[pos1, high]不能把pos再包含进去。5.2 退化风险与优化技巧快速排序的平均时间复杂度是O(n log n)但最坏情况是O(n^2)。当数组已经有序而基准值又总是选第一个元素时每次partition都只能把区间分割成1和n-1两部分递归树退化为一条链性能直接崩掉。为了规避这个问题工程上常用“三数取中”策略从arr[low]、arr[mid]、arr[high]三个位置取中间值作为基准并把它交换到low位置。这样能极大降低有序数据下的退化概率。另一种方法是随机选基准但随机数生成本身有开销。递归深度也是快速排序的隐患。最坏情况下递归深度达到n对超大数组可能耗尽函数调用栈空间。我在一个嵌入式项目中就遇到过快速排序排序几万条记录时程序崩溃查到最后就是递归太深把有限的栈空间用光了。如果你的运行环境栈很小或者数据量不可控要么改用非递归快排用栈模拟递归要么直接换归并排序。但大部分桌面环境下普通几万个数用快排是没问题的。6. 归并排序稳定但需要额外空间6.1 算法思想与代码实现归并排序也是分治。它将数组不断二分直到每个子区间只有一个元素然后把两个有序子区间合并成一个有序区间。这个过程需要额外的临时数组来存储合并结果。归并排序的优点是稳定且时间永远是O(n log n)缺点是需要O(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 (int p left; p right; p) { arr[p] tmp[p]; } } void merge_sort(int arr[], int tmp[], int left, int right) { if (left right) { 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); } }这里mid的计算用了left (right - left) / 2而不是(left right) / 2虽然对普通int数组后者也不会溢出但这是一个好习惯尤其是当left和right很大时两者相加可能溢出int范围。合并时的关键判断是arr[i] arr[j]这个“等于号”决定了归并排序的稳定性。如果写成当arr[i]等于arr[j]时会把右边的元素先放入tmp左边相同值的元素相对顺序就变了排序就变成不稳定。我专门拿[3, 1, 2, 3]这样的用例测试过写成后两个3的顺序确实会颠倒。6.2 内存分配与边界检查归并排序需要一个临时数组tmp。常见错误是在递归函数里频繁分配和释放tmp这样不仅低效还可能因为多次malloc导致内存碎片。正确做法是在对外接口里一次性分配好临时数组再调用递归的merge_sort。#include stdlib.h void merge_sort_wrapper(int arr[], int n) { if (n 0) { return; } int *tmp (int *)malloc(n * sizeof(int)); if (tmp NULL) { return; } merge_sort(arr, tmp, 0, n - 1); free(tmp); }同时要注意n0或n1的情况前者malloc(0)可能返回非NULL也可能返回NULL但都不该去访问内存后者递归里leftright直接返回。如果你在主程序里直接调用merge_sort(arr, tmp, 0, n)那也是错的因为rightn超出了有效下标范围循环会访问arr[n]。归并排序所有区间都是闭区间我建议把对外接口单独封装让调用者只传数组和长度避免搞混起始位置。7. 五大排序横向对比与选型建议7.1 复杂度与稳定性速查表我把前面零散提到的信息整理成一张表方便你随时查阅。排序算法最好平均最坏空间稳定冒泡排序O(n)O(n^2)O(n^2)O(1)是选择排序O(n^2)O(n^2)O(n^2)O(1)否插入排序O(n)O(n^2)O(n^2)O(1)是快速排序O(n log n)O(n log n)O(n^2)O(log n)否归并排序O(n log n)O(n log n)O(n log n)O(n)是这张表里最容易混淆的是“最坏”和“空间”。快速排序最坏O(n^2)可能让人意外但只要你理解了退化原因就明白应该避免在有序数组上直接选首个元素做基准。归并排序时间稳定但因为要拷贝到临时数组再拷回来实际常数因子比快速排序大所以数据量相同时归并排序往往比快排稍慢除非要求稳定性。7.2 根据场景选择算法我的经验是选排序算法不能只看复杂度还要看数据规模、是否要求稳定、内存限制、是否几乎有序。数据量小于50时插入排序往往比快速排序还快因为它的常数小不需要递归。数据量在几千到几百万且不要求稳定性时快速排序是默认选择。数据量大且业务上要求稳定时归并排序更合适。如果数据近乎有序插入排序是最好的选择。如果内存极其有限只能原地排序那就只能在冒泡、选择、插入、快排里选再综合考虑稳定性。另外C标准库自带qsort它内部是经过精心调优的快速排序可能混合插入排序绝大多数情况下我们不需要自己写快排。但自己手写一遍这五个算法意义在于理解它的缺陷和优化点这样用qsort时你能知道为什么它的参数里要传入比较函数为什么它的复杂度不是绝对有保障。8. 数组排序实战中的常见问题与排查8.1 数组越界与下标错位C语言数组越界是不会自动提示的这是新手最容易栽的跟头。比如冒泡排序里内层循环如果写j n - i当i为0时j最大到n-1访问arr[j1]就是arr[n]越界。再比如快速排序递归调用时把high写成npartition里就会访问arr[n]。排查这类问题我建议三个办法先用n1和n2的小数组跑一遍在排序函数入口打印low、high和n的值观察是否合理如果用GCC编译可以加-fsanitizeaddress它能直接报告越界位置比你自己盯代码高效得多。还有一种很隐蔽的错误排序函数的参数是数组和长度但你在循环里把长度写成了sizeof(arr)/sizeof(arr[0])。就像前面说的数组参数退化成指针sizeof(arr)是一个指针的大小通常是8字节除以4以后得到2导致循环只处理前两个元素。这种错误在64位系统上尤其常见因为指针大小和int大小不一样。8.2 递归栈溢出与排序性能陷阱快速排序和归并排序都用递归。快排在极端情况下递归深度等于n如果n是十万而环境栈空间只有几百KB每层递归即使只占用几十字节也可能栈溢出。归并排序的递归深度固定为log2(n)一般不会栈溢出但它需要额外数组分配。我建议在使用递归排序时给数据规模设一个上限或者提前对数组做一次“是否明显有序”的检测避开最坏情况。排查这类问题可以在main函数里设置一个较大的数组比如100000个元素连续多次调用排序函数观察是否崩溃。如果崩溃优先怀疑栈溢出可以临时把数组规模降到10000试一试。对于归并排序还要检查malloc的返回值返回NULL时不要直接往下走否则解引用空指针必挂。我在Windows和Linux下都遇到过系统资源紧张导致malloc失败的情况所以封装函数里一定要判断。8.3 排序函数的工程化封装要点写实际可用的排序模块时我通常会把内部实现和对外接口分开。比如冒泡排序直接暴露bubble_sort(arr, n)没问题但快速排序和归并排序会暴露复杂参数low/high或tmp这时封装一层能有效防止调用者传错。另外数组里的元素类型不总是int如果你要排序结构体数组只要把比较逻辑抽出来单独写一个函数或者写成宏就能复用排序框架。C语言里最灵活的是函数指针但作为入门阶段的五个基础算法先用int把逻辑吃透更重要。我还想提一个容易被忽略的问题排序过程中如果数组里存在大量重复元素快速排序的性能也会退化。因为经典的partition把等于基准的元素分散到两侧导致区间分割不均匀。解决方法是三路快排把数组分成小于、等于、大于基准的三部分等于基准的不用再递归。这个思路可以作为进阶练习但它已经超出了基础五排序的范围。建议你先把基础算法写熟再去研究三路快排、堆排序这些扩展内容。最后再分享一点我的个人经验这几个算法我前前后后写了不下几十遍每次写都还能发现一些细节问题。我现在写排序时会习惯性在测试函数里用一个print_array函数每次排序后打印前几个和后几个元素快速确认没有越界或丢失数据。你去看很多开源代码里面排序函数旁边都会带一个简单的验证数组就是这个原因。另外我强烈建议你把每个算法都亲自敲一遍不要复制粘贴敲的过程中才能注意到变量名、边界条件和交换逻辑。等你手写熟之后再回头用qsort处理实际问题会轻松很多。排序是算法的起点也是理解C语言内存和指针的一扇门希望这篇文章能帮你把这扇门推开。
