C语言四大排序算法详解：边界控制、稳定性与调试实战

C语言排序算法是练手的好题材也是面试和课设里的常客。冒泡排序、选择排序、插入排序、快速排序这四种算法恰好覆盖了交换类、选择类、插入类、分治类四条不同的思路。我发现很多初学者不是不会写而是说不清每一层循环边界为什么是 n-1、n-1-i一换数组大小就出问题。这篇文章我就把自己常用的 C 语言实例整理出来从测试台架、算法实现到调试方法一起过一遍。代码可以直接拿去跑后面还会聊到我踩过的坑和选型建议。1. 先弄明白这四种排序到底在“比”什么1.1 排序的本质逆序对是怎么被消灭的排序要做的事情用一句话概括就是把数组里的“逆序对”逐渐消灭掉直到任意两个相邻元素都满足前小后大。比如数组[3, 1, 2]存在3 1、3 2两个逆序对。排序的过程就是通过比较和移动让这些逆序对变成顺序对。四种算法处理逆序对的思路完全不同冒泡排序只交换相邻元素每次发现arr[j] arr[j1]就交换相当于把一个相邻逆序对直接抹掉选择排序不急着交换而是每一轮扫描找出当前范围内的最小值把它放到“已排好区”的末尾插入排序更像整理扑克牌把新拿到的一张牌插进手里已经有序的牌堆里快速排序则先选一个基准值让左边的元素都小于等于它、右边的元素都大于等于它于是基准值被放到了最终位置剩下的排序变成两个更短的子数组分别排序。理解这四种“消逆序对”的方式很重要。因为后面看代码时你会发现自己能预判每一轮循环在干什么冒泡每一轮结束都会有一个最大值沉底选择每一轮结束都会有一个最小值归位插入每一轮结束都会让前缀更长一点的有序区快速排序每一轮结束都会让一个基准值永久落位。1.2 复杂度和稳定性选型前先看一眼表先把最常用的结论摆在前面排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性冒泡排序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)选择排序无论数据怎么乱每轮都必须完整扫描剩余部分来找最小值所以最好也是最坏都是 O(n²)。快速排序平均表现最好是因为每次分区都能把数组大致切成两半递归深度是 log n 级别但它怕“每次选中的基准都是最大值或最小值”一旦发生这种情况分区只会切出一个空数组和一个 n-1 长度的数组递归退化成 O(n²)。稳定性这个概念也容易忽略。稳定排序的意思是如果两个元素相等排序之后它们的相对顺序和原来保持一致。对纯整数数组来说无所谓但如果你排的是包含多个字段的结构体先按主键再按副键稳定性就会直接影响结果是否正确。冒泡和插入是稳定排序选择和快排不稳定原因后面说。1.3 为什么要一次把这四种凑齐这四种算法不是简单的“难度递进”而是四种典型思路的入门样板。冒泡排序让你理解两层循环的边界控制选择排序让你体会“先定位、再交换”的取舍插入排序让你看到“移动”和“交换”的区别也让你明白为什么几乎有序的数据可以跑得飞快快速排序则逼你理解递归、分治和基准值的选择。掌握了这四种再看堆排序、归并排序、希尔排序很多概念都能找到对应关系。而且它们正好覆盖了一个很现实的场景考试或笔试里如果只让手写一种排序快速排序是最常考的因为代码量适中、思想又重要但如果只是需要一个不犯错的小数组排序插入排序往往更稳。所以别抱着“反正就背代码”的心态花点时间搞清楚它们各自的适用边界收益比背十遍代码大得多。2. 搭建排序实验台架让代码先跑起来再谈优化2.1 一个可复用的数组打印、校验与拷贝工具写算法最怕的就是“感觉对了实际输出不对”。所以我习惯在建任何排序算法之前先铺一个小的测试台架能打印数组、能判断数组是否真正有序、能拷贝数组。只有把验证动作自动化了后面改代码时才不会靠肉眼硬盯。#include stdio.h #include stdlib.h #include time.h #define N 8 void print_array(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int is_sorted(int arr[], int n) { for (int i 1; i n; i) { if (arr[i - 1] arr[i]) { return 0; } } return 1; }print_array用来输出结果is_sorted用来做自动化校验。别看这两个函数简单它们能省下大量人工核对时间。尤其是数组长度一长人眼很难一眼发现“中间漏了一个小数”的问题程序校验则不会放过任何一次错误。2.2 用函数指针统一驱动四个算法四种排序函数签名会有一点点差异前三个都是void sort(int arr[], int n)而快速排序通常写成void quick_sort(int arr[], int low, int high)。为了能用同一套代码调用我习惯给快速排序包一层接口然后用函数指针把四个算法统一起来。typedef void (*sort_func)(int *, int); void run_sort(const char *name, sort_func fn, int src[], int n) { int copy[N]; for (int i 0; i n; i) { copy[i] src[i]; } fn(copy, n); printf(%s: , name); print_array(copy, n); printf(校验: %s\n, is_sorted(copy, n) ? 通过 : 失败); }这里一定要先拷贝一份原数组。因为排序是原地修改数组如果不拷贝第一个算法排完序后后面几个算法处理的就都是已经排好的数组测试就没有意义了。函数指针的好处是主函数里可以很整齐地按顺序注册算法以后想加一个归并排序或者希尔排序不需要改动调用逻辑。配合快速排序的包装static void quick_sort_wrapper(int arr[], int n) { quick_sort(arr, 0, n - 1); }主函数里就可以写成int main(void) { srand((unsigned)time(NULL)); int arr[N]; for (int i 0; i N; i) { arr[i] rand() % 100; } printf(原始数组: ); print_array(arr, N); run_sort(冒泡排序, bubble_sort, arr, N); run_sort(选择排序, selection_sort, arr, N); run_sort(插入排序, insertion_sort, arr, N); run_sort(快速排序, quick_sort_wrapper, arr, N); return 0; }这一步把后续所有排序实现都隔离在一个统一的测试框架里后面每写完一个算法跑一次run_sort就能立刻知道对错。2.3 测试用例设计别只用随机数有序、逆序、重复都要测随机数组能覆盖很多常见情况但远远不够。固定基准的快速排序最怕的就是逆序数据插入排序最喜欢的就是几乎有序的数据大量重复元素则容易把分区函数里、写错的问题逼出来。我建议至少准备四类测试数据场景数据特征主要目的随机乱序随机生成验证平均情况下的正确性升序已经排好验证最好情况检查是否误交换降序完全逆序暴露固定选基准的快排退化问题大量重复相同值重复出现验证稳定性相关的相对顺序和分区边界平时跑随机数组通过了不算数把这几类数据都跑一遍才算真正能把代码交出去。我在调试时会把N临时调成很小的值比如 5 或 8这样中间结果一眼能看完确认逻辑正确后再把N调大验证性能。3. 冒泡排序和选择排序最直观的两种“最值搬运”方式3.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 tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped 1; } } if (!swapped) { break; } } }外层循环i表示已经排好的元素个数内层循环只需要比较到n - 1 - i。因为每一轮结束后数组末尾会多出一个确定好的最大值这个值不需要再参与比较。举个例子数组[5, 1, 4, 2]第一轮比较 5 和 1、5 和 4、4 和 2 后会变成[1, 4, 2, 5]最大值 5 已经沉到底第二轮就只需要比较前三个元素也就是处理[1, 4, 2]这个子区间。这里有个容易踩的坑如果内层条件写成j n - i当i 0时j会取到n-1访问arr[j1]就等于访问arr[n]已经越界。数组越界在 C 语言里往往不是立刻报错而是到程序末尾才突然崩溃或者悄悄改坏了相邻内存排查起来非常痛苦。3.2 冒泡排序的提前退出优化上面代码里我加了一个swapped标志。如果某一轮扫描下来没有任何一次交换说明数组已经有序可以立刻结束。这个优化在“本来就有序”的数据上效果很明显最好时间复杂度从 O(n²) 降到 O(n)。我试过给一个已经有序的 10000 元素数组跑冒泡排序不提前退出的话要比较约 5000 万次提前退出则只需要 9999 次比较。虽然实际项目中很少用冒泡排序处理大规模数组但这个优化思路值得记住判断“是否还需要继续”永远比闷头做完所有循环更聪明。冒泡排序是稳定的因为代码里只有arr[j] arr[j1]才交换相等时不会交换。如果你把条件改成两个相等的元素就会发生交换稳定性就被破坏了。很多人背下“冒泡是稳定排序”却忽略了前提条件这是一个非常典型的细节。3.3 选择排序每轮找到最小值只交换一次选择排序的思路和冒泡正好相反不是每比较一次就交换而是先扫描整个区间找到最小值的位置最后再交换一次。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; } } }每轮i位置都会被放入从i到n-1之间的最小值。比较次数还是 n(n-1)/2 次但交换次数最多只有 n-1 次。所以如果你的数据“比较代价低交换代价高”选择排序反而比冒泡更合适。比如你要排的是一个个头很大的结构体数组每次交换都要复制一大批数据那选择排序每轮只做一次大交换的优势就很明显。这里有个小细节如果min_idx i就说明当前元素已经是最小值不需要自己和自己交换。虽然自己交换通常也不会出错但加一个判断更干净也能减少不必要的复制。3.4 稳定性差异为什么选择排序不稳定选择排序的不稳定很多人一开始不理解。用一个小例子就能看清楚假设数组是[3a, 3b, 1]两个 3 用 a、b 区分3a 在 3b 前面。第一轮选择排序找到最小值 1然后把它和arr[0]也就是 3a 交换。交换后数组变成[1, 3b, 3a]两个 3 的相对顺序从“a 在前”变成了“b 在前”稳定性被破坏。冒泡排序不会出现这个问题因为它只交换相邻的逆序元素相等的元素从不跨过彼此。所以如果你需要稳定排序冒泡比选择更靠谱。这也解释了为什么复杂度表里同样都是 O(n²)一个稳定一个不稳定。4. 插入排序和快速排序从“理扑克牌”到“分而治之”4.1 插入排序的核心操作把新元素放进已排序区插入排序是最好用生活经验理解的算法打扑克牌时你抓着一张新牌会把它插到手里已经理好的牌堆中。代码里前面一段永远是有序的每次把当前元素key拿出来然后从后往前找它该待的位置。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; } }注意看while循环的条件顺序先判断j 0再访问arr[j]。如果写成while (arr[j] key j 0)当j变成 -1 时会先访问arr[-1]这是未定义行为程序可能不会立刻崩但结果已经不可信了。插入排序的交换成本比冒泡低因为它是“整体移动”不是“两两交换”。对大规模乱序数据来说它依然慢但它的另一个特点非常实用接近有序的数据会跑得非常快因为while循环里的移动几乎不会执行。4.2 插入排序最好的情况几乎有序时的 O(n)如果数组已经升序排好比如[1, 2, 3, 4, 5]插入排序每次取出的key都比前面所有元素大while循环一次都不执行只需要做 n-1 次外层循环和 n-1 次赋值时间复杂度是 O(n)。这个特性让插入排序成为很多高级排序的“底层补充算法”。很多工业级排序实现里当递归区间缩小到一定程度时会放弃快排或归并改用插入排序收尾。原因就是小规模数据本身接近有序的概率高插入排序代码简单、没有递归调用、常数很小实际表现往往比“大材小用”的递归排序更好。4.3 快速排序的挖坑法实现快速排序的写法很多我更喜欢“挖坑法”写分区函数因为它比前后指针法更容易理解也不容易一上来就在边界条件上翻车。int partition(int arr[], int low, int high) { int pivot arr[low]; while (low high) { while (low high arr[high] pivot) { high--; } arr[low] arr[high]; while (low high arr[low] pivot) { low; } arr[high] arr[low]; } arr[low] pivot; return low; }一开始pivot取最左边的元素那么arr[low]这个位置就相当于被挖出来了。先从右往左找小于pivot的元素找到后把它填到左边的坑里这时右边又留下一个新坑再从左往右找大于pivot的元素填右边的坑。最后low和high相遇把pivot放回去。一次分区完成后pivot已经处于它最终应该在的位置左边元素都小于等于它右边元素都大于等于它。快速排序的递归部分非常简单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); } }这里要注意递归边界左边区间是low到pi - 1右边是pi 1到high。如果你不小心把左边写成pi那么已经放好位置的基准值还会被再次处理轻则多做一些无用功重则造成递归无法结束。4.4 固定选基准的坑逆序数据退化成 O(n²)固定取arr[low]作为基准存在一个很明显的短板。当输入是[5, 4, 3, 2, 1]这种完全逆序的数据时第一次分区后小于等于 5 的元素全在左边右边一个都没有基准 5 被放到最后。下一次递归只处理左边长度为 n-1 的区间又选到 4再次退化。整个过程相当于每一轮只排好一个元素递归深度达到 n时间复杂度退化成 O(n²)。解决思路有两个一是随机选基准二是三数取中。三数取中更稳定做法是取low、mid、high三个位置把三个数中大小居中的那个换到low作为基准。这样即使数组接近有序也不会每次都被迫选到最值。完整写法可以加在partition开头int mid low (high - low) / 2; if (arr[low] arr[mid]) { int tmp arr[low]; arr[low] arr[mid]; arr[mid] tmp; } if (arr[low] arr[high]) { int tmp arr[low]; arr[low] arr[high]; arr[high] tmp; } if (arr[mid] arr[high]) { int tmp arr[mid]; arr[mid] arr[high]; arr[high] tmp; } int tmp arr[low]; arr[low] arr[mid]; arr[mid] tmp;这段代码做的事情是先让arr[low]、arr[mid]、arr[high]三个数保证low mid high然后把中间值换到low再继续原来的挖坑分区。改造以后逆序数据退化到 O(n²) 的可能性大幅下降。4.5 快速排序也是不稳定的相等元素的相对顺序可能变化快速排序不稳定理解起来不像选择排序那么直观。假设数组是[3a, 3b, 1]取第一个 3a 作为基准。挖坑过程中1 会被填到 3a 的位置最后 3a 被放回中间位置结果可能变成[1, 3b, 3a]。两个相等的 3 相对顺序变了。所以如果你需要“先按主字段排序再保持副字段的先后顺序”直接上快速排序就要小心。C 语言标准库里提供的通用排序函数虽然也是基于快速排序思想的实现但标准并不保证稳定性。理解了这一点你才会知道为什么面试里经常追问“快排稳定吗”。5. 一次完整运行的输入输出和调试经验5.1 我在台架上的实际输出用前面那套台架跑出来的结果大概长这样原始数组: 42 17 88 3 90 56 12 7 冒泡排序: 3 7 12 17 42 56 88 90 校验: 通过 选择排序: 3 7 12 17 42 56 88 90 校验: 通过 插入排序: 3 7 12 17 42 56 88 90 校验: 通过 快速排序: 3 7 12 17 42 56 88 90 校验: 通过乍看四个算法的输出完全一样这很正常。排序算法本身不会改变数组的最终内容只是内部路径不同。因此只看输出结果无法判断一个算法写得好不好。想要真正看到差异需要增加中间状态打印。5.2 用中间状态打印观察每一轮我给冒泡排序写过一个调试版每轮结束就把数组打出来void bubble_sort_debug(int arr[], int n) { for (int i 0; i n - 1; i) { 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; } } printf(第%d轮: , i 1); print_array(arr, n); } }用[5, 1, 4, 2]测试输出会是第1轮: 1 4 2 5 第2轮: 1 2 4 5 第3轮: 1 2 4 5看到这个过程你会立刻明白“最大值逐渐沉底”是什么意思。快速排序也可以打印每次分区的low、high和pivot位置。中间状态打印是调试算法的最好工具之一它能把“代码为什么这样写”变成肉眼可见的过程。5.3 五个特别隐蔽的错误我几乎都踩过第一个是sizeof失效。数组作为函数参数传入时已经退化成指针在函数里写sizeof(arr) / sizeof(arr[0])得到的是指针大小除以元素大小结果完全不对。解决办法就是像我的台架一样把数组长度作为参数显式传进去。第二个是冒泡内层循环越界。j n - i会让j最大取到n-1再访问arr[j1]就越界。正确写法是j n - 1 - i。第三个是快速排序分区里的while条件写漏。如果只在while (arr[high] pivot)里判断元素没有同时判断low high右边扫描会一路越过low继续往左跑最后读写到数组之外。正确写法必须把low high放在前面。第四个是插入排序里j 0写错顺序。一旦j变成 -1访问arr[-1]行为未定义。虽然某些编译器碰巧没崩但这种代码绝不能上线。第五个是递归边界传错。快速排序右边递归写成quick_sort(arr, pi, high)会让基准值反复进入区间导致无限递归或结果错误。每次写递归排序都要在纸上标清楚基准值的位置到底在哪个区间。5.4 随机化多轮验证把数据规模变大后单次运行看对了也不够。我一般会做 200 轮随机数组测试每轮重新生成数据调用算法后立刻用is_sorted校验。只要有一轮出错就打印这轮的数据和排序结果方便定位问题。int failed 0; for (int t 0; t 200; t) { for (int i 0; i N; i) { arr[i] rand() % 1000; } // 拷贝后用某个排序函数处理 if (!is_sorted(copy, N)) { failed 1; printf(第 %d 轮失败\n, t 1); break; } } if (!failed) { printf(200轮随机测试全部通过\n); }随机多轮测试能把很多“碰巧过了”的问题暴露出来。尤其是快速排序的分区边界只有频繁换数据才能让你遇到那些隐藏的越界和死循环问题。6. 数据规模、稳定性、工程习惯排序代码不是背完就算6.1 小规模数据排序插入排序和冒泡排序并不丢人很多初学者觉得冒泡和插入是“低级算法”实际工程里当数据量小到几十个元素时O(n²) 和 O(n log n) 之间的差距几乎可以忽略。插入排序没有递归调用代码路径短在近乎有序的数据上甚至比快排还快。所以如果你遇到一个数组长度只有 5、10、20 的场景别纠结写插入排序完全没问题。冒泡排序在极端环境里也有价值代码极短不容易出错对内存几乎没有额外要求。我曾经在一个资源很紧张的嵌入场景里用它处理小数组比引入复杂排序划算得多。排序算法的好坏永远要结合数据规模看。6.2 大规模乱序数据快速排序是常见默认选择但注意退化数据量一大比如几千、几万甚至几十万O(n²) 和 O(n log n) 的区别就很明显。这时候快速排序是默认选择平均性能好原地排序不需要额外开一个大数组。但前提是一定要处理最坏情况退化问题至少用三数取中或者随机选基准。如果数据是链表而不是数组快速排序的优势会打折扣因为链表不方便随机访问分区时需要额外维护多个链表。这时候归并排序往往更合适。不过这是另一个话题本文还是围绕数组排序展开。6.3 稳定性需求前怎么选冒泡和插入稳定快排不一定如果你要排序的对象是一个结构体数组并且希望相同主键的元素保持原有顺序那就必须选择稳定排序。四种算法里冒泡排序和插入排序是稳定的选择排序和快速排序不稳定。插入排序在小规模数据里是最合适的稳定排序冒泡排序则适合你更看重“代码短”的场景。如果数据量大且必须稳定我会考虑归并排序但归并需要额外的 O(n) 空间这也是要接受的代价。排序没有银弹稳定性、时间复杂度、空间复杂度、实现难度四个维度需要一起权衡。6.4 工程习惯排序之前先想清楚排序之后先校验我在实际调这些排序的时候最大的体会是写代码之前先问自己三个问题——数据规模有多大是否需要稳定最坏情况能不能接受很多线上问题其实在选型阶段就可以避免。比如你明知道数据接近有序却用了固定基准的快速排序那就是给自己挖坑反过来如果数据量大且很随机却选冒泡那就是纯粹跟自己过不去。最后一个建议排序完成之后不要只看一眼“好像是排好了”一定要写is_sorted这样的自动校验。再顺手打印一下中间状态观察最后一轮或几轮是否真的没有大量移动。经验丰富不体现在能默写多少遍快排而体现在能预判边界条件、能设计验证方法、能在踩坑之后总结出规律。这四种排序只是起点把它们的循环边界、递归终止条件和稳定性分析吃透后面再学归并、堆排序和希尔排序你会觉得整个知识体系一下子通畅了。