C语言数组上的五大排序算法：原理、边界与工程选型

C语言学到数组这部分，几乎所有教材都会同步安排排序算法，这其实不是巧合，而是因为数组的连续存储和下标记址方式，天然就是演示排序过程最合适的“舞台”。我见过太多次这样的场景：五个算法都能背出名称，甚至能默写某个版本的代码，但换一组数据、换一个数组长度，代码就跑出越界或者结果不对。

这篇文章就把冒泡排序、选择排序、插入排序、快速排序、归并排序这五大基础排序，绑定在C语言数组的场景下一次讲透。适合刚开始啃C语言的大学生，也适合学了一圈回头补基础的人。看完你至少能明白三件事：每种算法在数组上是如何移动元素的、边界条件为什么容易错、遇到实际问题时该怎么选方案。

1. 数组为什么是所有排序算法的“共同地基”

1.1 C语言数组的三大特性，恰好对应排序的硬需求

要理解排序算法，先得理解数组这种存储结构。很多初学者把数组当成“一种能存多个数据的变量”，这个理解没错，但太表面了。真正支持排序算法跑的，是数组三个底层特性。

• 连续内存：元素在内存里一个挨一个存放，物理上是连续的。排序算法里的“整体有序”，本质上就是把这串连续的值重新排列。
• 下标随机访问：给定数组名和下标，可以在常数时间内访问任意元素。排序过程中最频繁的操作就是“取第i个元素”和“取第j个元素比较”，如果不是数组而是链表，光定位元素就要消耗大量时间，算法复杂度也完全变了。
• 元素类型一致：每个元素占用同样大小空间，编译器才能通过下标精确计算地址。这保证了循环中下标递增时，访问到的元素位置是确定的。

这三点合在一起，意味着你可以在同一个数组里原地调整元素顺序，不需要为每个元素重新分配存储。像选择排序、快速排序这类“原地排序”算法，正是建立在数组这种结构上的。

1.2 把“排序”拆成两个基本动作：比较和移动

不管什么排序算法，最终都只做两件事：比较大小，移动元素。你观察所有实现，跑不掉这两个动作。所谓“比较”，就是判断两个数谁大谁小；所谓“移动”，包括交换两个元素的位置，或者把某个元素向后平移覆盖。

设计一个排序算法，本质上是回答三个问题：

1. 每一轮比较哪两个元素？
2. 比较结果如何决定移动方向？
3. 移动发生在原数组内，还是需要额外的辅助空间？

这五个基础排序算法，就是这三种答案的不同组合。冒泡排序比较相邻元素，选择排序比较未处理区段的全部元素，插入排序比较有序区与新元素的相对大小，快速排序靠分区基准值来安排位置，归并排序则干脆把问题拆成两半，最后合并。理解了这点，你再看每种算法的代码，就能顺着“比较—移动”这条线理清逻辑，而不是死记循环边界。

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从i+1往后扫描，更新最小值的下标。等内层跑完，min_idx就是当前未排序区段的最小值位置，再交换。这样每轮最多做一次交换。

这段代码的边界注意点：

• 外层i只需要到n-2最终交换，因为最后一个元素不需要再处理。
• 内层j从i+1开始，初始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[j+1]就是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位置换到i+1，pivot就到了它最终的位置上。

一个容易混淆的地方是递归边界。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(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。每一次改动都会逼你去理解原代码的每一行，这种“主动制造问题”的练习方式对你的提升很大。

我个人在实际带项目时有个体会：排序算法学到什么程度算真学会？不是能把代码默写出来，而是别人问你“为什么这里相等时不交换”“为什么不稳定一定出现在交换之后”时，你能解释清楚原因。这几个为什么，才是数组和排序这段内容真正留给你的东西。