C语言学到数组这部分几乎所有教材都会同步安排排序算法这其实不是巧合而是因为数组的连续存储和下标记址方式天然就是演示排序过程最合适的“舞台”。我见过太多次这样的场景五个算法都能背出名称甚至能默写某个版本的代码但换一组数据、换一个数组长度代码就跑出越界或者结果不对。这篇文章就把冒泡排序、选择排序、插入排序、快速排序、归并排序这五大基础排序绑定在C语言数组的场景下一次讲透。适合刚开始啃C语言的大学生也适合学了一圈回头补基础的人。看完你至少能明白三件事每种算法在数组上是如何移动元素的、边界条件为什么容易错、遇到实际问题时该怎么选方案。1. 数组为什么是所有排序算法的“共同地基”1.1 C语言数组的三大特性恰好对应排序的硬需求要理解排序算法先得理解数组这种存储结构。很多初学者把数组当成“一种能存多个数据的变量”这个理解没错但太表面了。真正支持排序算法跑的是数组三个底层特性。连续内存元素在内存里一个挨一个存放物理上是连续的。排序算法里的“整体有序”本质上就是把这串连续的值重新排列。下标随机访问给定数组名和下标可以在常数时间内访问任意元素。排序过程中最频繁的操作就是“取第i个元素”和“取第j个元素比较”如果不是数组而是链表光定位元素就要消耗大量时间算法复杂度也完全变了。元素类型一致每个元素占用同样大小空间编译器才能通过下标精确计算地址。这保证了循环中下标递增时访问到的元素位置是确定的。这三点合在一起意味着你可以在同一个数组里原地调整元素顺序不需要为每个元素重新分配存储。像选择排序、快速排序这类“原地排序”算法正是建立在数组这种结构上的。1.2 把“排序”拆成两个基本动作比较和移动不管什么排序算法最终都只做两件事比较大小移动元素。你观察所有实现跑不掉这两个动作。所谓“比较”就是判断两个数谁大谁小所谓“移动”包括交换两个元素的位置或者把某个元素向后平移覆盖。设计一个排序算法本质上是回答三个问题每一轮比较哪两个元素比较结果如何决定移动方向移动发生在原数组内还是需要额外的辅助空间这五个基础排序算法就是这三种答案的不同组合。冒泡排序比较相邻元素选择排序比较未处理区段的全部元素插入排序比较有序区与新元素的相对大小快速排序靠分区基准值来安排位置归并排序则干脆把问题拆成两半最后合并。理解了这点你再看每种算法的代码就能顺着“比较—移动”这条线理清逻辑而不是死记循环边界。2. 冒泡排序交换思想的起点也是越界错误的重灾区2.1 完整实现与运行逻辑冒泡排序的思路最直白从左到右反复比较相邻两个元素如果左边比右边大就交换。这样每一轮比较结束后当前范围里最大的元素会“冒泡”到最右边。经过n-1轮整个数组就有序了。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 temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped 1; } } if (!swapped) { break; } } }我在代码里加了一个swapped标志变量这是冒泡排序最实用的优化。如果某一轮从头到尾没有发生交换说明数组已经整体有序继续循环没有任何意义直接退出就行。写冒泡排序最容易出的错误是把内层循环的边界写成j n。这时arr[j 1]会访问到下标n也就是数组最后一个元素之后的位置这是典型的数组越界。C语言不会主动提醒你程序可能照常跑但结果是未定义的。正确写法是j n - 1 - i因为每一轮结束后右边i个位置已经固定不再参与比较。2.2 冒泡排序的性能画像最好情况数组原本有序加优化后一轮扫描就能停下复杂度O(n)。平均和最坏情况都是O(n²)。空间复杂度O(1)也就是只用了几个临时变量。稳定性稳定。两个相同值的元素在排序后仍然保持原有相对顺序因为只有时才交换相等不会触发。我一般把冒泡排序定位成“教学热身题”。它能让你很快明白排序的交换原理但实际项目中几乎没人用它因为同一个数组规模下比较次数太多。唯一值得记住的是那个swapped优化思路它在很多场景里都通用一旦发现整体有序提前结束节省不必要的计算。3. 选择排序每轮只交换一次以“少移动”换性能3.1 完整实现与边界细节选择排序的思路和冒泡刚好相反。冒泡是“边比较边交换”选择排序是“每轮只记录位置最后交换一次”。具体做法是从数组第i个位置开始在后面的所有元素里找到最小值所在下标然后把它和第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 temp arr[i]; arr[i] arr[min_idx]; arr[min_idx] temp; } } }外层循环i确定“当前待填充的位置”内层循环j从i1往后扫描更新最小值的下标。等内层跑完min_idx就是当前未排序区段的最小值位置再交换。这样每轮最多做一次交换。这段代码的边界注意点外层i只需要到n-2最终交换因为最后一个元素不需要再处理。内层j从i1开始初始min_idx设为i这样即使后面没有更小值也不会出现无意义交换。加if (min_idx ! i)只是为了减少多余的赋值操作删掉也不影响排序正确性。3.2 为什么选择排序适合交换代价高的场景选择排序有一个很独特的优点无论数组原始状态如何比较次数永远是固定的n(n-1)/2但交换次数最多只有n-1次。这个特性让它特别适合“移动元素代价很高”的场景。比如数组元素本身是个结构体里面装了一堆大字符串或者是一个大对象这时候交换一次的开销比比较一次高得多。选择排序宁可多比几轮也要把交换控制在最少优势就体现出来了。当然它也有明显的短板不稳定。举个例子数组是[5a, 3, 5b, 2]第一轮找到最小值2把它和第0位的5a交换数组变成[2, 3, 5b, 5a]。原本5a在5b前面排序后5b跑到5a前面了相同值的相对顺序被破坏。如果你有稳定排序的需求选择排序就不能用。4. 插入排序像整理扑克牌一样逐步扩大有序区4.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保存当前要插入的元素值。为什么必须用临时变量存因为前面的元素整体后移会覆盖掉arr[i]如果不提前取出原值就丢了。j从i-1开始向左扫描。只要前面的元素比key大就把它后移一个位置腾出空位。循环结束时j要么停在-1说明key比前面所有元素都小要么停在第一个不大于key的元素位置arr[j1]就是key该去的地方。这个写法用while循环天然避免了“边移动边找位置”容易漏的边界问题。同样场景如果用for循环很容易写成for (j i - 1; arr[j] key; j--)一旦j降到-1表达式访问arr[0]已经悬空最后还得额外判断不如while直观。4.2 对“接近有序”数据的出色表现插入排序在五种基础算法里有一个很特殊的优点它对基本有序的数据效率极高。如果数组接近有序每个元素在有序区里只需要比较一两次就找到位置不需要大段移动最好情况下复杂度降到O(n)。这个特性在实践中很有用。比如一个系统需要维护一个动态排行榜新数据到来时老数据基本已经有序只需要把新元素插到合适位置插入排序的变体就能胜任。它也是很多高级排序算法在数据量小或接近有序时的“补充方案”比如快速排序递归到小区间时有些实现会切换成插入排序来减少函数调用开销。不要被它O(n²)的平均复杂度吓到。对于几百个元素的小数组插入排序的性能表现往往比复杂度理论估计的更好因为它的常数因子特别小内存访问也局部化不涉及跨区域跳转。5. 快速排序递归和分区在数组上的第一次“搭档”5.1 Lomuto分区法与完整实现快速排序是这五个算法里第一个让你感受到“递归拆分”魅力的。它的核心思路不是整体一步一步整理而是先定一个基准把数组分成两半左半全部不超过基准右半全部大于基准然后对左右两半递归执行同样操作。分区完成后整个数组自然有序。实现快速排序有很多种分区方式教学上最常用的是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 temp arr[i]; arr[i] arr[j]; arr[j] temp; } } int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; return i 1; } void quick_sort(int arr[], int low, int high) { if (low high) { int pi partition(arr, low, high); quick_sort(arr, low, pi - 1); quick_sort(arr, pi 1, high); } }理解Lomuto分区关键在于变量i的含义。i始终指向“已经处理过的、小于等于pivot的区段”里最后一个元素的位置。j负责扫描整个区间每发现一个小于等于pivot的元素就先把i前移一位再把这个元素换到i位置。等j扫描完毕所有小于等于pivot的元素都集中在i及以前所有大于pivot的元素都在i以后。最后把pivot从high位置换到i1pivot就到了它最终的位置上。一个容易混淆的地方是递归边界。quick_sort里的参数是下标low和high不是长度也不是个数。很多人写成quick_sort(arr, 0, n)然后递归调用时越界。记住调用入口应该是quick_sort(arr, 0, n - 1)。5.2 最坏情况与实用规避手段快速排序的平均时间复杂度是O(n log n)但它有一个致命的弱点最坏情况退化成O(n²)。什么时候退化当每次选定的pivot都是当前区间最大或最小值时分区极不平衡一边没有元素另一边是n-1个递归深度变成n性能暴跌。典型场景就是数组本身已经有序或接近有序而代码选pivot用的是固定位置比如取arr[high]。这时arr[high]就是最大值每一轮分区都失效算法退化成冒泡级别。很多人一开始没注意这个问题拿快速排序测一组已经排好序的数据结果慢得离谱怀疑自己代码写错了。实用规避方案有两个随机选择pivot把arr[random]和arr[high]交换再执行分区逻辑。三数取中取low、mid、high三个位置的中间值作为pivot。虽然随机选pivot也不能在理论上彻底消除最坏情况但实际数据里基本不会连续出现这种退化场景。我在给学生演示时习惯在partition之前加一句随机交换宁可多一点开销也不让快排掉进最坏陷阱。6. 归并排序用临时数组换稳定性典型的空间换时间6.1 合并有序数组的完整实现归并排序的思路比快速排序更“机械”一些把数组从中间切两半左半边排序右半边排序然后把两个有序序列合并成一个大的有序序列。递归执行下去最终整个数组有序。它的核心在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]; i; } else { arr[k] R[j]; j; } k; } 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) { 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语言时就开始养成。合并的while循环有一个细节要注意比较用的是L[i] R[j]而不是L[i] R[j]。如果写成小于两边相等时会优先取右边数组的元素这会让相同值的相对顺序颠倒破坏归并排序的稳定性。6.2 稳定性为什么有实践价值以及O(n)空间代价归并排序是五个算法里仅有的两个稳定算法之一另一个是冒泡排序。所谓稳定就是相同键值的元素在排序后保持了原先的相对先后顺序。这在处理结构体数组或者有多个排序字段的数据时非常关键。举个常见的例子学生成绩表里有学生姓名和成绩两个字段先按学号排序再按成绩排序。如果第二个排序算法不稳定那么成绩相同的同学里学号顺序就被打乱了。如果使用稳定排序第二轮的相同成绩区间里学号顺序会继续保持第一轮排好的状态。归并排序因为合并时优先取左边数组天然具备这种稳定性所以很多需要稳定性的场景都会首选归并。代价就是O(n)的额外空间因为每次合并都要申请两个临时数组。虽然归并排序时间上所有情况都是O(n log n)但在内存紧张的环境里空间开销可能成为瓶颈。实际工程中归并排序常用于外部排序也就是数据量大到内存装不下、需要借助磁盘的场景因为它的“顺序访问”特性非常适合磁盘IO。7. 五个算法的横向对比以及我踩过的那些坑7.1 把复杂度放在一张表里看清楚五个算法的特性我建议你直接存下面这张表算法最好情况平均情况最坏情况空间复杂度稳定性冒泡排序O(n)O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n)O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定空间复杂度那栏快速排序写的O(log n)指的是递归调用栈的深度不是数组本身占的空间。归并排序的O(n)是临时数组的开销。对比表最值得记住的点是这个如果数据规模大、对稳定性没有要求快速排序通常是最优选择如果必须稳定归并排序优先如果数据基本有序插入排序可能出人意料地快如果元素交换成本极高选择排序的固定交换次数反而是优势。7.2 写排序代码时最常见的四种“翻车现场”我这些年帮人调试过太多排序代码问题高度集中在四个地方。第一循环越界。这是冒泡排序的内层边界、快速排序的递归入口最容易犯的错。C语言数组越界不会立刻报错反而让bug藏得很深。调试方法很简单在循环里加一句printf(%d %d\n, j, arr[j])肉眼检查是否存在访问到arr[n]的情况。第二值被覆盖。写插入排序时忘记用临时变量保存key前面的元素后移后游戏直接崩。同理交换两个元素时不引入temp以为可以用两步完成交换结果两个位置变成相同值。我见过有人在快排的partition里手写交换把三步写成了两步排序结果少了一个数查找难度极高。第三递归边界错乱。快速排序和归并排序的递归函数参数是闭区间下标不是从0到n。不理解这点的人会习惯性地写quick_sort(arr, 0, n)直接访问越界。记住递归终止条件low high已经说明了这是下标区间。第四画图问题不大但思维跳跃大的情况。面对递归排序把代码跑一遍不如手画一遍递归树。拿六个元素的数组跑归并排序画出每一层的调用和合并过程比嘴上说“分治分治”管用十倍。7.3 我建议的练习路径如果把这篇文章当成任务清单我建议你按顺序做三件事。第一件把我给的五个函数原样跑通用printf打印每一步数组变化。至少观察冒泡和插入的移动过程你会直观看到“比较和移动”这两个动作到底是什么。第二件不看代码自己在纸上写五个函数的完整实现再用随机数据测试。写不出来没关系回到文章里找但一定要找出自己哪里卡住了——多半是边界条件没想明白。第三件尝试改参数。比如把冒泡排序改成降序把插入排序改成从右向左扫描把快排的固定pivot换成随机pivot。每一次改动都会逼你去理解原代码的每一行这种“主动制造问题”的练习方式对你的提升很大。我个人在实际带项目时有个体会排序算法学到什么程度算真学会不是能把代码默写出来而是别人问你“为什么这里相等时不交换”“为什么不稳定一定出现在交换之后”时你能解释清楚原因。这几个为什么才是数组和排序这段内容真正留给你的东西。
