简介一份面向编程学习者的C排序算法实践资源聚焦随机生成1000个整数后分别用冒泡、插入、选择、快速、归并、堆排序处理并统计各算法赋值次数以对比效率适合正在学习数据结构与算法、希望从操作层面理解排序性能的人群。压缩包内仅含1个C源文件大小约3KB代码结构清晰包含随机数生成、多种排序函数实现以及统计赋值次数的逻辑便于直接运行和修改。目前已有1627人浏览学习。通过该代码可直观观察不同排序算法在相同数据下的赋值次数差异同时复习 库用法及算法复杂度等知识点也可作为扩展实验模板尝试增加算法变体或数据规模继续测试是一份紧凑实用的算法练习材料。1. 为什么排序算法的赋值次数比比较次数更值得看排序算法课上讲复杂度只看比较次数但真到压测和选型阶段赋值次数才是最让人意外的黑匣子。同样是随机生成的 1000 个数字冒泡和快排都能排完赋值次数却能差出一个量级选择排序比较次数固定在 O(n²)赋值却只有 O(n)插入排序的赋值随数据有序度剧烈摆动归并排序比较次数不算少赋值反而是最稳定的。下面我用固定种子随机生成 1000 个数字分别跑冒泡、选择、插入、快排、归并五种排序算法在每次元素赋值的位置插入计数把赋值次数一点点拆给你看统计口径怎么定、埋点埋在哪、结果怎么解读以及统计过程中最容易翻车的五个细节。2. 准备可复现的随机数据1000 个数字的三种测试集2.1 固定种子与唯一值让每次实验都能重放排序对比实验的第一步是生成数据。很多人的习惯是rand()裸奔跑一遍但这样每次拿到的序列都不一样冒泡这次快、快排下次慢根本没法归因。我一般会先固定随机种子保证同一个输入在所有算法面前是完全一致的。#include stdio.h #include stdlib.h #define N 1000 void generate_int_array(int arr[], int n, unsigned int seed, int bound) { srand(seed); for (int i 0; i n; i) { arr[i] rand() % bound; } }seed是随机种子bound是取值范围上限。这里arr[i] rand() % bound是最常见的生成方式但有个隐患1000 个数落进 10000 个槽位时期望重复约 50 个重复数据会让逆序对数量缩水赋值次数也跟着缩水。为了得到更干净的随机分布我倾向于直接生成唯一值。void generate_unique_array(int arr[], int n) { int pool[10000]; for (int i 0; i 10000; i) pool[i] i; srand(2024001); for (int i 9999; i 0; i--) { int j rand() % (i 1); int t pool[i]; pool[i] pool[j]; pool[j] t; } for (int i 0; i n; i) arr[i] pool[i]; }这是 Fisher-Yates 洗牌先把 0 到 9999 的完整序列放进池子从后往前随机交换最后取前 1000 个。这样得到的 1000 个数两两不同随机分布也均匀逆序对期望值大约在 25 万附近。注意洗牌过程本身也有交换但那是测试数据生成阶段不计入排序算法的赋值统计。2.2 三种测试集随机、近有序、逆序各考察什么只测一组随机数据是不够的。赋值次数跟初始有序度高度相关生产环境里数据往往是局部有序的所以我会同时准备三组数据随机、近有序、完全逆序。测试集生成方式逆序对规模考察目标随机洗牌取前 1000 个约 25 万算法平均表现近有序有序数组打乱 50 对几十到几百生产数据常见形态逆序从 999 到 0 递减填充约 50 万最坏情况近有序数据不是简单地把数组大部分排序而是让绝大多数元素保持在正确位置上。用代码生成更直观void generate_nearly_sorted(int arr[], int n) { for (int i 0; i n; i) arr[i] i; srand(2024002); for (int k 0; k 50; k) { int a rand() % n, b rand() % n; int t arr[a]; arr[a] arr[b]; arr[b] t; } }先填一个完全有序的数组再随机挑 50 对位置交换。1000 个元素里只有 100 个左右的位置被扰动整体逆序对数量很少。这个形态非常接近实际业务里的日志表、按主键插入后少量更新的数据。2.3 统计口径什么算一次赋值什么不算赋值次数这个指标最容易翻车的地方是口径不一致。我采用的统计口径是只有「一个数组元素的值被写入另一个位置」才算一次赋值。具体来说swap(a, b)算三次赋值tmp a、a b、b tmp。插入排序里的腾挪a[j 1] a[j]算一次。归并排序里把元素从临时数组拷回a[l k] tmp[k]算一次。i、j--、k这类循环游标自增不算。快排里pivot a[r]算一次因为读取元素并存入局部变量也是一次值传递。这个口径定下来之后所有算法才有可比性。3. 五种排序算法的赋值来源计数埋点应该放哪数据结构排序算法课里统计的是比较次数八大排序算法总结比来比去也比的是比较次数但赋值次数反映的是元素搬运成本埋点位置和比较次数的埋点完全不同。下面的代码片段统一用COUNT()表示一次计数完整的宏定义和可编译版本在下一章给出。3.1 冒泡与选择排序交换次数决定赋值总量冒泡排序的核心操作是相邻交换一次交换计三次赋值// 冒泡排序核心段示意 if (a[j] a[j 1]) { int tmp a[j]; COUNT(); a[j] a[j 1]; COUNT(); a[j 1] tmp; COUNT(); }内层比较总次数是n(n-1)/2也就是约 49.95 万次但交换次数并没有那么多。每一次交换会消除恰好一个逆序对随机数据下交换次数约等于逆序对数 25 万赋值次数约 75 万逆序数据直接翻倍到 150 万量级。选择排序完全是另一副面孔// 选择排序核心段示意 if (min ! i) { int tmp a[i]; COUNT(); a[i] a[min]; COUNT(); a[min] tmp; COUNT(); }每轮外层循环最多触发一次交换所以 1000 个数据的赋值次数上界就是3 * (n-1) 2997。不管数据是随机还是逆序这个数都不变。这就是赋值次数视角和比较次数视角最典型的冲突选择排序比较次数固定接近 50 万但赋值次数极低在元素拷贝成本高的场景里反而可能是赢家。3.2 插入排序搬移次数直接等于逆序对数量插入排序的赋值点有两处读取当前元素、腾挪时右移元素。// 插入排序核心段示意 int key a[i]; COUNT(); while (j 0 a[j] key) { a[j 1] a[j]; COUNT(); j--; } a[j 1] key; COUNT();key a[i]算一次a[j 1] a[j]每次右移算一次最后把 key 写回去再算一次。总赋值次数恰好等于n 逆序对数。随机数据的逆序对期望值约 25 万赋值次数大约 25.1 万逆序数据约 50.1 万而近有序数据只要几百个逆序对赋值次数可能只有 1000 出头。插入排序是五种算法里对初始有序度最敏感的数据越整齐它的赋值成本越低。这个特性让插入排序在很多工业实现里不是主角而是快排的小数组收尾工具。当递归切分到 20 个元素以内时数据已经接近局部有序插入排序的赋值次数进入线性区间反而比继续分区更快。3.3 快排与归并分治思想把赋值成本摊进递归过程快排的赋值集中在partition的交换动作上。以最右元素为枢轴的经典写法// 快速排序分区段示意 int pivot a[r]; COUNT(); for (int j l; j r; j) { if (a[j] pivot) { i; int tmp a[i]; COUNT(); a[i] a[j]; COUNT(); a[j] tmp; COUNT(); } } int tmp a[i 1]; COUNT(); a[i 1] a[r]; COUNT(); a[r] tmp; COUNT();pivot a[r]是一次赋值分区中的每一次交换是三次。随机数据下交换总次数在十万量级整体赋值次数大约在 10 万到 30 万之间浮动。但如果数据本身是逆序的直接用最右元素做枢轴会让递归树退化成链交换次数逼近n²/2赋值次数会冲到百万量级和冒泡一个水平。三数取中能缓解退化但赋值次数的波动依然远大于归并。归并排序的赋值是一笔确定性的账// 归并排序合并段示意 while (i m j r) { if (a[i] a[j]) { tmp[k] a[i]; COUNT(); k; i; } else { tmp[k] a[j]; COUNT(); k; j; } } for (k 0; k r - l 1; k) { a[l k] tmp[k]; COUNT(); }每层递归大约做n次赋值总层数是log2(n)所以 1000 个数据的归并赋值次数稳定在1000 * 10 10000左右几乎不随数据初始有序度变化。分治思想在这里的价值特别明显归并用确定的搬运次数换来了最稳定的赋值行为代价是额外的 O(n) 临时空间。堆排序也走交换路线建堆加 n 次下沉约产生 2n log2 n 量级的赋值比归并多一些但胜在空间复杂度 O(1)。4. 跑通对比实验C 语言代码与赋值计数输出解读4.1 评测框架统一计数器与交换宏先把计数基础设施搭好。我用一个static long做全局计数器用宏把赋值语句包装起来。#include stdio.h #include stdlib.h #include string.h #define N 1000 static long assign_count; #define COUNT() (assign_count) #define SWAP(x, y) do { \ int tmp (x); COUNT(); \ (x) (y); COUNT(); \ (y) tmp; COUNT(); \ } while (0)COUNT()是空参数宏每次调用让assign_count加一。SWAP宏展开后正好三次赋值三次计数。用宏而不是函数是为了保证计数能落在调用处而不是躲在函数内部看不见。assign_count用long是因为最坏情况下冒泡赋值接近 150 万普通int虽然也装得下但养成用long的习惯更稳妥。4.2 五个排序函数的完整埋点实现冒泡排序void bubble_sort(int a[], int n) { for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int tmp a[j]; COUNT(); a[j] a[j 1]; COUNT(); a[j 1] tmp; COUNT(); } } } }这里没有直接用SWAP宏而是把三次赋值展开写便于看清楚每个COUNT()到底对应哪个赋值动作。内层循环的比较次数是固定的但只有比较成立时才触发赋值所以计数结果能直接反映数据的逆序程度。选择排序void selection_sort(int a[], int n) { for (int i 0; i n - 1; i) { int min i; for (int j i 1; j n; j) { if (a[j] a[min]) min j; } if (min ! i) { int tmp a[i]; COUNT(); a[i] a[min]; COUNT(); a[min] tmp; COUNT(); } } }注意min i和min j是索引赋值不是元素值搬运不计数。只有当min ! i时才产生一次交换、三次计数。这是选择排序赋值次数远低于其他简单排序的关键。插入排序void insertion_sort(int a[], int n) { for (int i 1; i n; i) { int key a[i]; COUNT(); int j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; COUNT(); j--; } a[j 1] key; COUNT(); } }key a[i]是一次赋值右移腾挪每次计一次最后写回一次。j--是游标移动不计数。这个函数埋点后统计出来的赋值次数理论上等于n 逆序对数可以直接用逆序对理论值交叉验证。快速排序int partition(int a[], int l, int r) { int pivot a[r]; COUNT(); int i l - 1; for (int j l; j r; j) { if (a[j] pivot) { i; int tmp a[i]; COUNT(); a[i] a[j]; COUNT(); a[j] tmp; COUNT(); } } int tmp a[i 1]; COUNT(); a[i 1] a[r]; COUNT(); a[r] tmp; COUNT(); return i 1; } void quick_sort(int a[], int l, int r) { if (l r) return; int p partition(a, l, r); quick_sort(a, l, p - 1); quick_sort(a, p 1, r); }枢轴选取会影响partition的交换次数。这里取a[r]计一次赋值后续每次交换计三次。逆序输入时递归深度退化为 n交换次数会陡增这是后面避坑章节要展开的重点。归并排序临时数组一次性分配void merge(int a[], int l, int m, int r, int tmp[]) { int i l, j m 1, k 0; while (i m j r) { if (a[i] a[j]) { tmp[k] a[i]; COUNT(); k; i; } else { tmp[k] a[j]; COUNT(); k; j; } } while (i m) { tmp[k] a[i]; COUNT(); k; i; } while (j r) { tmp[k] a[j]; COUNT(); k; j; } for (k 0; k r - l 1; k) { a[l k] tmp[k]; COUNT(); } } void merge_sort(int a[], int l, int r, int tmp[]) { if (l r) return; int m (l r) / 2; merge_sort(a, l, m, tmp); merge_sort(a, m 1, r, tmp); merge(a, l, m, r, tmp); }tmp在最外层统一分配避免在递归里反复malloc。合并阶段每次写入tmp[k]计一次回拷时每次写入a[l k]再计一次所以归并的赋值次数天然是确定性的分成「写进临时数组」和「写回原数组」两笔账。4.3 统一入口每次排序前恢复原始副本主函数的职责是生成一组随机数据然后让五个算法分别在这组数据的副本上运行。void quick_sort_wrapper(int a[], int n) { quick_sort(a, 0, n - 1); } void merge_sort_wrapper(int a[], int n) { int *tmp malloc(n * sizeof(int)); merge_sort(a, 0, n - 1, tmp); free(tmp); } void run_case(const char *name, int src[], int n, void (*sort_fn)(int[], int)) { int copy[N]; memcpy(copy, src, n * sizeof(int)); assign_count 0; sort_fn(copy, n); printf(%-12s : %ld\n, name, assign_count); } int main(void) { int base[N]; generate_unique_array(base, N); run_case(bubble, base, N, bubble_sort); run_case(selection, base, N, selection_sort); run_case(insertion, base, N, insertion_sort); run_case(quick, base, N, quick_sort_wrapper); run_case(merge, base, N, merge_sort_wrapper); return 0; }run_case每次都从base复制一份副本再排序保证五个算法面对完全相同的初始数组。memcpy和assign_count 0的执行顺序不能颠倒否则计数器清零会把上次结果覆盖。generate_unique_array来自第 2.1 节编译时放到main之前即可。4.4 结果解读数量级比精确值更重要按上述代码和种子跑出来的数值会有细微波动但数量级是确定的可以用理论推导交叉验证。算法随机数据近有序数据逆序数据冒泡约 75 万约 150约 150 万选择约 3000约 3000约 3000插入约 25.1 万约 1000约 50.1 万快排十万量级万量级接近 150 万归并约 1 万约 1 万约 1 万随机数据下最扎眼的是选择排序比较次数接近 50 万赋值次数却只有 3000正因为每轮最多交换一次。插入排序在近有序时只有 1000 次左右的赋值比选择排序还低这是它适合做快排收尾的原因。归并排序三列数值都稳定在 1 万附近如果不关心空间只求稳定它是首选。快排的赋值次数波动最大最坏情况下和冒泡同级所以「快排一定快」这种印象在赋值成本和逆序输入面前并不成立。5. 赋值次数统计的避坑记录五个让结论翻车的细节5.1 计数口径被循环自增加污染现象归并排序统计出来的赋值次数超过 10 万比插入排序还高和理论完全对不上。原因把COUNT()直接放在tmp[k] a[i]这类复合语句后面k和i也会触发计数器累加。归并排序的读写动作都带着游标自增游标移动被误当成元素赋值计数瞬间虚高。解决赋值表达式单独成行COUNT()紧跟其后游标自增放在计数器之后的下一条语句。例如先写tmp[k] a[i]; COUNT(); k; i;而不是把三条操作挤在一行里。5.2 排序前没有恢复原始数组现象先跑冒泡再跑选择两组赋值次数几乎一样而且都明显偏小。原因run_case里memcpy的源数据已经被上一次排序改成了有序数组后续每个算法都在排好序的副本上跑赋值事件自然变少。最典型的是冒泡跑完把数组排成升序选择排序再跑一遍几乎不触发交换。解决程序里维护一个只生成一次的base主数组run_case每次排序前从base用memcpy恢复副本排序只改副本不改主数组。这也是 4.3 节框架存在的意义。5.3 随机数范围太小导致重复值泛滥现象把rand() % 10000改成rand() % 100生成 1000 个数后冒泡的赋值次数从 75 万掉到 20 万左右。原因值域太小1000 个数挤在 100 个取值里大量重复元素让a[j] a[j 1]成立的概率大幅降低交换次数和逆序对数量同时缩水实验测的其实是「重复数据」而不是「随机数据」。解决要么把值域扩大到远大于 n要么直接采用洗牌生成唯一值。从实验严谨性角度我建议直接上唯一值方案避免重复值对后续所有算法造成不可控影响。5.4 把 swap 封装成函数后计数被隔离在函数体外现象冒泡排序的赋值次数恰好是预期值的三分之一比如 25 万而不是 75 万。原因为了代码整洁把交换抽成了void swap(int *a, int *b)函数函数内部的三次赋值没有放COUNT()只在调用swap的地方计了一次数。一次交换本该计三次却只计了一次总数自然缩水成三分之一。解决交换用宏在调用处展开保证三次赋值全部落在计数器可见的范围里或者把COUNT()放进swap函数体内部。前者更直观也是本章采用的方式。5.5 归并排序的临时数组在递归里反复分配现象同一个种子、同一组数据归并排序的赋值次数连续跑几次不一致有时多出几百次波动。原因第一版merge_sort把malloc写进递归函数每个递归层级都申请释放临时数组堆状态不稳定而且malloc返回的临时数组内容不确定调试时容易分不清哪一次赋值是排序本身产生的。解决在merge_sort_wrapper里一次性malloc一块长度为 n 的tmp通过参数一路传进递归排序结束后统一free。这样临时数组只分配一次归并的计数完全反映排序逻辑本身不受内存分配影响。6. 用赋值次数做选型不同数据画像下的排序算法取舍赋值次数统计出来不是用来发论文的是用来做选型判断的。我的习惯是拿比较次数和赋值次数两张表一起看数据画像决定算法选择。随机数据下快排的比较次数和赋值次数都在可接受区间选快排没有悬念。近有序数据下插入排序的赋值次数只有 1000 左右远低于快排和归并的万级成本所以遇到「整体有序、局部微调」的数据插入排序不该被轻视。逆序数据是最有意思的插入排序和快排同时翻车赋值次数冲到百万量级归并排序依然稳稳停在 1 万附近所以如果系统里会出现大段逆序数据又不在意那点内存直接上归并比冒险优化快排的枢轴靠谱得多。还有一个常被忽略的场景排序对象不是int而是几十字节的大结构体。赋值次数在这种场景下直接等于内存拷贝次数快排的交换操作会把结构体整个搬来搬去一次交换搬几十字节代价远高于比较两个整数。这时候选择排序虽然比较了 50 万次但赋值只有 3000 次实际跑起来可能比快排还快。程序员不会拿它排大数组但排百来个小结构体时它是值得考虑的廉价方案。更通用的做法是对索引或指针排序排序过程只搬指针最后再按指针重排原数组本质上就是把「搬大对象」降级成「搬小指针」。这是我踩过坑之后留下的习惯以前选排序只看教科书上的比较次数后来用一个几十 KB 的结构体数组做压测快排比归并慢了将近一倍翻了赋值次数才明白是大量结构体拷贝拖了后腿。现在每次评估排序方案我一定会把赋值次数当成第二硬指标和比较次数放在同一张表里看。希望帮到你。本文还有配套的精品资源点击获取