尧图网站建设 
简介一份面向数据结构初学者的排序算法对比实践资源围绕随机生成一千个整数使用冒泡、插入、选择、快速、归并、堆排序等多种主流算法进行排序并统计赋值次数以量化比较各算法的操作开销帮助读者直观理解不同排序策略的时间性能差异。压缩包为RAR格式仅含1个C源文件包体大小约3KB代码紧凑且可直接运行适合本地编译验证。目前已有1627人学习/下载可服务于算法入门、课程实验与面试复习。资源核心价值在于提供完整的随机数生成与排序实现并嵌入赋值计数机制读者可自行调整数据规模和算法种类观察赋值次数与时间复杂度之间的关系进而加深对算法稳定性、原地排序等特性的理解。通过实际执行结果可直接对比不同算法的赋值次数差距为算法选型提供数据参考。1. 给 1000 个随机数字排序顺便把四种算法的赋值次数数清楚“排序算法”的复杂度课听再多都不如亲手对 1000 个随机数字跑一圈来得直观。这个实验的思路很直接随机生成 1000 个数字让插入排序、冒泡排序、选择排序和快速排序先后处理同一份数据再把每次对数组元素的赋值次数记下来。赋值次数比运行时间更接近算法本身的数据搬移成本也比比较次数更容易被忽略真正统计完你会发现选择排序的赋值次数低得反常而冒泡排序高得离谱。这套实验适合刚学完基础排序、想从赋值维度重新理解算法代价的人也适合要用数据说服别人“某某排序不该这么写”的场景。它不依赖任何第三方库一份 C 代码就能跑通。2. 随机生成 1000 个数字三种生成方式与分布形态如何左右赋值次数2.1 为什么排序实验要用可复现的伪随机序列随机生成数字听起来一句话的事但“随机”这两个字在实验里必须被驯服。如果你直接用系统时间当种子每次运行得到的数组都不一样排序算法的赋值次数自然也不一样第二天回来看结果会完全无法解释。我的做法是使用确定性伪随机序列给随机数生成器一个固定种子比如 42那么无论运行多少次生成的 1000 个数字都完全一致。这样插入排序和快速排序面对的输入是同一份计数差异才真正来自算法本身而不是输入数据的随机抖动。真随机数通常来自硬件熵源适合安全和统计抽样但排序实验要的是“可复现的随机”不是不可预测。伪随机数生成器PRNG的核心参数就是种子和范围种子决定序列起点范围决定数值落点。实际项目里可以准备几组固定种子比如 42、2024、7分别生成多组测试数据用来观察一组种子下的偶然波动。常见错误是在程序开头调用 srand(time(NULL))理由是“更像随机”结果每次跑出来的赋值次数都不同无法定位是算法差异还是输入差异。数据文件一旦生成就应该当成不可变的基准后续所有排序都从这份文件读入才算守住对照实验的底线。另外需要区分两个经常摆在一起的术语比较运算符判断两个值的大小关系赋值运算符把右侧的值写入左侧变量。排序算法的代价由比较次数和赋值次数组成交换元素时主要消耗在赋值上如果只盯着循环次数看很容易把两种代价混在一起。后面统计用的是赋值次数它度量的是数据搬了多少次对结构体、字符串这类大对象排序时赋值次数往往比比较次数更贴近真实的开销。2.2 用 C 语言和 Python 各生成一份随机数据文件先在 C 里生成一份基础输入文件。下面代码把 1000 个 0 到 9999 之间的随机整数写入 random_1000.txt每行一个数字。#include stdio.h #include stdlib.h #define N 1000 #define RANGE 10000 int main(void) { int data[N]; srand(42); // 固定种子保证每次运行得到同一组数字 for (int i 0; i N; i) { data[i] rand() % RANGE; // 值域 0~9999 } FILE *fp fopen(random_1000.txt, w); if (fp NULL) { perror(fopen); return 1; } for (int i 0; i N; i) { fprintf(fp, %d\n, data[i]); } fclose(fp); printf(generated %d numbers\n, N); return 0; }说明srand(42) 是整份数据的“后悔药”只要种子不变序列就固定实验翻车后还能回到同一份输入重新核对。RANGE 取 10000 而不是 100 或 10是为了让重复值比例可控数值范围太小1000 次抽样里会出现大量重复排序的比较和赋值次数都会被明显压低。fprintf 写纯文本是为了方便你用 Python、Java 或 Excel 打开同一份文件复现。Python 版更简洁适合快速做多组实验时用import random random.seed(42) data [random.randint(0, 9999) for _ in range(1000)] with open(random_1000.txt, w, encodingutf-8) as f: f.write(\n.join(str(x) for x in data))这里 random.seed(42) 的作用与 C 的 srand(42) 等价randint(0, 9999) 等价于 rand() % 10000。如果你想生成随机唯一值也就是 1000 个数字互不重复需要再加一个去重循环data [] seen set() while len(data) 1000: x random.randint(0, 9999) if x not in seen: seen.add(x) data.append(x)这样生成的数组没有重复元素适合用来观察“无重复输入下赋值次数的高位表现”但要注意它和真实随机抽样得到的重复率不同得到的结果不能混在一起比。实际做对比时我会为每种分布单独存文件文件名里带分布标签例如 random_uniform.txt、random_unique.txt、sorted_1000.txt避免后面统计时拿错输入。2.3 分布形态会把赋值次数带偏唯一值、重复值与近乎有序数组同样的排序算法在不同分布的输入上表现完全不一样。如果生成的数字只落在 0 到 19 之间1000 个位置里大量数字相同插入排序内部的 while 经常一两次就停赋值次数明显偏低如果数据本来有序插入排序几乎不做数据搬移。反过来把数组逆序生成插入排序每次都要把新元素一路搬回开头赋值次数接近最坏情况 O(n²)。因此实验之前就要确定你到底想测哪一种输入形态不能笼统说“跑一下看看”。实际排序性能对比里最常用的三个输入形态是均匀随机分布、随机唯一值分布、已有序或逆序数组。均匀随机分布用 rand() 取模最容易得到缺点是碰撞不可避免随机唯一值分布适合测所有元素都不相等时的行为近乎有序数组专门用来暴露插入排序的线性优势同时也会让固定基准的快速排序退化成 O(n²)。我一般会为每个形态单独生成数据文件并在实验记录里写清文件来源因为后续所有赋值次数结论都建立在这批输入的基础上。输入文件一旦混用统计数字再漂亮也是假的。这些数据文件用不着很大1000 个数字足够看出差异。更大规模比如 10000会让 O(n²) 算法跑到肉眼可见的慢赋值次数也会从几十万跳到几千万计数器类型要跟着从 int 换成 long long。鉴于是从 1000 起步我建议先固定 N1000 跑通流程再逐步扩大数组规模观察增长斜率这样既能验证理论复杂度又不会因为一次实验等太久。下一章就把计数规则落实成可编译的 C 代码。3. 用同一份数据跑四种排序算法赋值次数的计数规则与 C 实现3.1 赋值次数数的是什么数据移动与临时变量的边界排序算法性能比较的经典维度有两个比较次数和赋值次数。比较次数衡量的是“判断谁大谁小”的调用次数赋值次数衡量的是“把数据从一个位置搬到另一个位置”的执行次数。二者不是一回事交换一次元素比较可能一次都不发生但赋值必然发生。赋值次数越少说明算法搬运数据的开销越低在设计结构体、字符串等大对象排序时尤其关键因为一次记录的搬移可能是几十字节甚至几十 KB。这里必须把“赋值次数”的边界说清楚否则统计结果没法复核。我采用的规则是把数组元素或保存数组元素的临时变量发生一次写入就记一次赋值循环用的下标、min_idx 这类索引变量不计入。这样一次 swap(arr, i, j) 算三次赋值tmp arr[i]、arr[i] arr[j]、arr[j] tmp。插入排序里 key arr[i] 算一次arr[j1] arr[j] 每次后移算一次最后 arr[j1] key 算一次。选择排序外层交换里的三次赋值照算但 min_idx j 不算因为它更新的是下标不是数据。这套规则和数据结构排序算法教材里常用的“记录移动次数”基本一致便于做理论推导时对得上。实际统计时不要在算法内部到处手写 count容易漏。我的做法是把交换封装成函数其他排序函数一律通过这个函数交换插入排序的 key 操作显式计数。这样代码里只有少数几个计数点出错时一眼能找到。更稳妥的插桩方式是用宏包装赋值操作但 C 宏在组合下标时容易出现多次求值副作用得不偿失所以函数显式计数更可靠。3.2 用 C 语言实现计数插桩一个计数器与一套统一规则下面这段代码是整组实验的核心骨架。它先用 long long 声明全局计数器 assign_count避免 int 溢出reset_count 在每次排序前清零swap 函数在交换元素时精确计三次。注意这里我特意把临时变量 tmp 的赋值也算进去因为一次交换本质上就是三次数据搬移。#include stdio.h #include stdlib.h #include string.h #define N 1000 #define RANGE 10000 static long long assign_count; static void reset_count(void) { assign_count 0; } static void swap(int arr[], int i, int j) { if (i j) return; // 相同位置不搬避免无意义计数 int tmp arr[i]; assign_count; // tmp arr[i] arr[i] arr[j]; assign_count; // arr[i] arr[j] arr[j] tmp; assign_count; // arr[j] tmp }swap 里开头加一个 i j 判断能让选择排序在无需交换时不产生假的赋值次数。如果你希望统计“代码里赋值语句执行次数”可以去掉这个提前返回但那样该次交换会把 tmp 搬来搬去却没有实际改变数组对数据移动语义来说是噪声。跑实验前先决定自己遵循哪套规则并在实验记录里写清楚否则后期换一种统计口径结果会完全对不上。3.3 四种排序算法的赋值计数实现插入排序的赋值点有三类保存 key、后移元素、写回 key。注释里标出了每个 count 对应的语义。static void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; assign_count; // 把 arr[i] 搬到 key int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; assign_count; // 把 arr[j] 后移一位 j--; } arr[j 1] key; assign_count; // 把 key 写回正确位置 } }冒泡排序用 swap 完成交换所以赋值计数全部落在 swap 函数里。为了保留一个“已经有序就提前退出”的版本我加了 swapped 标记这会让有序数组的赋值次数直接逼近 0符合真实工程里常见写法。static 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]) { swap(arr, j, j 1); swapped 1; } } if (!swapped) break; } }选择排序的赋值点最少只有外层交换。内层只是不断更新 min_idx并不搬动数据。这正好体现了它的特征比较次数依然是 O(n²)但数据搬移量被压到了 O(n)。static 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) { swap(arr, i, min_idx); } } }快速排序这里选最后一个元素做基准。pivot arr[hi] 是一次数据搬移要计数后续 partition 过程中交换操作统一走 swap所以计数点也不散。static void quick_sort_range(int arr[], int lo, int hi) { if (lo hi) return; int pivot arr[hi]; assign_count; // pivot arr[hi] int i lo - 1; for (int j lo; j hi; j) { if (arr[j] pivot) { i; if (i ! j) { swap(arr, i, j); } } } if (i 1 ! hi) { swap(arr, i 1, hi); } quick_sort_range(arr, lo, i); quick_sort_range(arr, i 2, hi); }代码说明这个实现用了 Lomuto 分区优点是直观、计数点少缺点是有序数组下 i 会一路增长基准总在末端递归退化为 O(n²) 深度赋值次数也会暴涨。后续章节会给出改造方案。注意快速排序的 pivot 赋值计入赋值次数而普通临时变量不算这会让快速排序的统计比“只数交换”的常见做法多出 O(n) 级别的小量但和 O(n log n) 的主项相比可忽略。3.4 每次排序前必须复制原始数组否则结果全是假的排序算法是原地排序会把传入数组改得面目全非。如果先跑冒泡排序数组已经有序再跑插入排序插入排序遇到有序数组赋值次数只有几千这个结果显然不能拿来和冒泡的第一次结果比。因此主函数要维护一份原始数据 base每次调用排序函数前用 memcpy 恢复到工作缓冲区 buf。下面是主流程。int main(void) { int base[N], buf[N]; FILE *fp fopen(random_1000.txt, r); for (int i 0; i N; i) { fscanf(fp, %d, base[i]); } fclose(fp); memcpy(buf, base, sizeof(base)); reset_count(); insertion_sort(buf, N); printf(insertion %lld\n, assign_count); memcpy(buf, base, sizeof(base)); reset_count(); bubble_sort(buf, N); printf(bubble %lld\n, assign_count); memcpy(buf, base, sizeof(base)); reset_count(); selection_sort(buf, N); printf(selection %lld\n, assign_count); memcpy(buf, base, sizeof(base)); reset_count(); quick_sort_range(buf, 0, N - 1); printf(quick %lld\n, assign_count); return 0; }参数说明memcpy 的第三个参数用 sizeof(base) 而不是 N * sizeof(int)省得每次改 N 还要同步改这里base 在程序运行中始终不变。打印时用 %lld 对应 long long 计数器。跑完这一份四个算法的赋值次数就同框了。第 4 章会告诉你如何做多轮采样和结果解读。4. 排序算法赋值次数对比多轮采样的数据表与快速排序的阈值参数4.1 多轮采样用多个固定种子消除单组数据的偶然性单次实验只能证明“这一组 1000 个数字下”的赋值次数不能证明算法的一般表现。随机数组本身有方差快速排序的赋值次数对基准位置尤其敏感一组数据可能正好落在好分区或坏分区上。我一般会准备 5 个固定种子分别生成 5 组输入每组输入都让四种算法走一遍最后取平均或中位数。这样报告的赋值次数更接近期望值也能顺手看几种算法之间的方差。下面用一个 Python 脚本统一调度它调用前面编译好的 C 可执行程序并捕获 stdout 里的输出结果。这样做的好处是不用把 C 代码的统计逻辑再抄一份到 Python避免两套实现出来两种答案。import subprocess import statistics import random seeds [42, 2024, 7, 65535, 1] results {algo: [] for algo in [insertion, bubble, selection, quick]} for seed in seeds: # 每个种子生成一份数据文件交给 C 程序统计 random.seed(seed) data [random.randint(0, 9999) for _ in range(1000)] with open(random_1000.txt, w, encodingutf-8) as f: f.write(\n.join(map(str, data))) out subprocess.check_output([./sort_counter], textTrue) for line in out.strip().splitlines(): algo, count line.split() results[algo].append(int(count)) for algo, counts in results.items(): print(f{algo:10s} mean{statistics.mean(counts):10.0f} fmin{min(counts):10d} max{max(counts):10d})说明C 程序本身已经把数据从 random_1000.txt 读进来所以 Python 只负责换文件并重复调用。每个种子生成的文件覆盖上一次不会累积。statistics.mean 是标准库函数不需要额外安装。如果你的 C 程序输出里带了额外调试文字解析前先过滤掉非 “算法名 数字” 格式的行否则 int(count) 会抛异常。注意一个容易混淆的点Python 的 random.seed(42) 和 C 的 srand(42) 并不生成同一串数字这不影响实验。只要每次统计面对的是同一个文件“输入一致”这个条件就满足了。跨语言复现不需要两边的随机序列完全相同。4.2 实测结果表为什么选择排序赋值次数最少、耗时却不少按上述流程跑一轮赋值次数的数量级会落在下面这张表里。我没有把每次的精确数字写死因为换编译器、改分支写法都会造成几百到几千的波动但相对关系是稳定的。算法赋值次数种子 42N10005 组种子平均赋值次数增长插入排序约 25 万约 25 万O(n²)与逆序对数量相关冒泡排序约 75 万约 75 万O(n²)每次交换计 3 次赋值选择排序约 3 千约 3 千O(n)只有交换才搬数据快速排序约 3 万约 3 万O(n log n)分区交换主导表格里最反直觉的一项是选择排序赋值次数只有几千比快速排序还低一个数量级。原因在于它每趟只做一次交换内层循环只比较不搬移n1000 时最多 999 次交换每次 3 次赋值。但它一点也不快因为它做了大约 50 万次比较“少搬数据、多比较”是对它最准确的概括。这也说明赋值次数不是性能的全部它只反映数据搬移这一面评估排序算法要同时看赋值次数和比较次数。快速排序的 3 万次赋值比插入排序的 25 万次低一个数量级也印证了 O(n log n) 的优势从数据搬移角度同样成立。随着 N 从 1000 涨到 10000插入排序的赋值次数会往千万级走快速排序大约只到几十万级这个差距会比表格里更刺眼。如果你做的实验里冒泡排序赋值次数反而比插入排序少那多半是提前退出逻辑在有序数据上生效了后面第 5 章会专门讲这类陷阱。4.3 影响赋值次数的两个参数数据规模与快速排序的切分阈值数组规模是最直接的参数。赋值次数的绝对数字随 N 增大明显放大但每种算法的相对关系基本由复杂度决定。调 N 时顺便把工作缓冲区数组大小改掉同时确认计数器类型是 long long否则 O(n²) 算法在 N10000 时就能撞上 int 上限。N1000 时三种 O(n²) 算法尚能秒回N50000 时插入排序和冒泡排序要等好几秒正好用来演示复杂度差异。第二个参数是快速排序的小数组切分阈值。很多工程实现会在区间长度小于某个阈值时改用插入排序因为插入排序在小规模数组上常数小赋值次数也更少。下面是加了一个 CUTOFF 的版本#define CUTOFF 16 static void quick_sort_cutoff(int arr[], int lo, int hi) { if (hi - lo CUTOFF) { insertion_sort(arr lo, hi - lo 1); return; } int pivot arr[hi]; assign_count; int i lo - 1; for (int j lo; j hi; j) { if (arr[j] pivot) { i; if (i ! j) swap(arr, i, j); } } if (i 1 ! hi) swap(arr, i 1, hi); quick_sort_cutoff(arr, lo, i); quick_sort_cutoff(arr, i 2, hi); }重点看 CUTOFF 的取值太大会让 O(n²) 的插入排序处理大块数据赋值次数明显上升太小则递归过深小数组上的递归开销和额外交换没法被吸收。常见范围是 8 到 32取 16 是折中。调这个参数时你会在赋值次数上看到一个先降后升的曲线最低点附近就是当前环境下比较合适的阈值。这也顺带解释了为什么标准库的排序实现很少是“裸”快速排序它们普遍混用了插入排序和堆排序。如果不加任何优化快速排序在逆序数组上的表现会很糟固定选最后一个元素做基准每次分区都极度不平衡递归深度接近 n赋值次数会退化到 O(n²) 量级甚至比插入排序还高。三数取中是一种常见补救在 arr[lo]、arr[mid]、arr[hi] 中选中间值当基准可以避免最常见的有序输入退化。我把这个优化留给做扩展实验的读者先确认普通版本能跑通并且计数稳定再考虑改基准选择策略。5. 排序算法赋值次数统计的五个常见坑现象、原因与解决5.1 后面的排序算法拿到的是上一轮排好的数组赋值次数直接“崩”了现象冒泡排序先跑赋值次数 75 万紧接着插入排序对同一个数组跑赋值次数只剩几百。插入排序在近乎有序的数组上确实很快但这个结果不能用于算法对比因为输入已经不再是原始的 1000 个随机数了。更隐蔽的版本是四个算法按顺序跑前两个结果正常后两个结果全部偏低你还会误以为快速排序优化得很好。原因所有排序函数都是原地排序主循环里没有每次从原始数据恢复数组导致后跑的算法在有序或接近有序的数据上做无用功。赋值次数因此虚低结论完全失真。这个坑几乎每个做对比实验的人都会踩一次因为它不影响编译只影响结论不打印数组内容根本看不出来。解决在 main 函数里维护一份 base 数组每次调用排序前 memcpy 到 buf或者最土的办法每次排序前从 random_1000.txt 重新读文件。注意 memcpy 必须在排序调用之前完成reset_count 在哪一步都无所谓。我习惯把“先恢复输入、再清零计数、再排序”固定成一个三步流程少一步都算污染样本。排序完成后还可以顺手检查 buf 是否有序防止计数对但排序本身出错。5.2 固定了种子却每次跑结果不一样怀疑自己写了假代码现象明明在 2.2 的代码里有 srand(42)但连续运行两次快速排序的赋值次数一次是 3 万、一次是 6 万插入排序也跟着变。你可能觉得“种子固定了怎么会变”于是开始怀疑编译器或者量子涨落实际上原因通常很朴素。原因最可能是生成数据与排序没有在同一个程序里同步。比如你用 C 程序生成数据后又用 Python 脚本重新生成 random_1000.txtPython 的随机序列和 C 的 rand() 完全不同或者程序里 srand(42) 之外另有模块偷偷调用了 srand(time(NULL))把序列重置了。还有一层原因是 C 的 rand() 在不同平台上的实现不一样同一份代码在 Linux 和 Windows 下生成的序列不同所以跨平台对比时不能要求绝对数字一致只能对比相对趋势。解决一旦生成好数据文件就把它当作只读文件对待排序程序只读取、不生成。固定种子的意义在于复现不在于“随机”本身。每次排序前先打印数组前五个元素核对是否与预期一致这个动作花不了几毫秒却能挡住大部分数据错乱问题。跨平台对比时先确认输入的 1000 个数字完全相同再比较赋值次数才有意义。5.3 开编译器优化后计数变成零和负数排序像被“吞”了现象调试版编译得到正常计数改成 -O2 编译输出变成 0或者中间结果乱码增加数组规模后冒泡排序的赋值次数甚至出现负数。第一次遇到这个问题的反应往往是“程序写错了”但同样的代码换个优化级别又正常最容易让人一头雾水。原因两个问题可能叠加。负数大概率是计数器 int 溢出N1000 时冒泡排序约 75 万次赋值int 能扛住但如果同时把 N 改成 100000赋值次数轻松突破 21 亿int 溢出后回绕成负数。计数为 0 则可能是编译器看到排序结果没有被使用把整个排序函数判定为死代码消除尤其在 -O2 以上优化级别常见。计数器变量如果被优化到寄存器且从未被外部读取也会出现看似正常的代码却输出保留值。解决计数器一律用 long long输出用 %lld。为了防死代码消除排序后不要把结果丢掉至少打印数组前三个元素或者算一个数组元素的校验和再输出。更直接的办法是把 assign_count 声明成 volatile long long让编译器知道这个变量的写操作可能有外部副作用但真正可移植的解法是让实验结果被后续逻辑消费掉。检查计数是否有效的一个办法是把 N1000 的插入排序赋值次数和理论量级对比应该在十几万到二十几万之间如果只有几百基本可以断定排序被编译器优化掉或者输入文件错乱。5.4 选择排序赋值次数最低但运行耗时比冒泡排序还长现象计时测试里选择排序的赋值次数只有几千次但运行耗时和冒泡排序不相上下甚至更慢。你会开始怀疑赋值次数这个指标有没有意义是不是统计错了。原因赋值次数只统计数据搬移次数选择排序内层循环的大量比较并没有纳入赋值计数。它用 O(n²) 次比较换来 O(n) 次交换赋值次数确实漂亮但比较指令一样吃 CPU 时间。赋值次数低和运行时间短不是一回事比较次数、缓存行为、分支预测都会影响最终耗时。对 int 数组来说比较比数据搬移还贵的情况并不少见。解决把赋值次数和比较次数同时统计观察选择排序“比较次数约等于冒泡、赋值次数远低于冒泡”的组合才能解释为什么它赋值最少却慢。扩展方法是在所有 if 条件判断处增加 compare_count比如static long long compare_count; static 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) { compare_count; // 一次侵入比较 if (arr[j] arr[min_idx]) { min_idx j; } } if (min_idx ! i) { swap(arr, i, min_idx); } } }定义好计数规则后每个算法的 “比较次数 / 赋值次数” 组合就完全不同插入排序比较和赋值都随逆序对走选择排序比较极多但赋值极少冒泡排序两者都不少。实际工程里排序对象如果是几十字节的结构体赋值次数对耗时的权重会上升如果只是 int 数组比较次数往往占主导。所以不要拿着赋值次数单一指标去仲裁算法优劣它只负责说清楚“搬数据”这一面。5.5 只跑一次就下结论把“玄学波动”当成算法差异现象某一次快速排序赋值次数 1.2 万另一次却 5 万于是得出结论“快速排序不稳定别用”。细看两次的数据文件并不相同或者一次跑了切分阈值版本另一次跑的是普通递归版结论自然南辕北辙。原因快速排序的赋值次数对基准选择和数据分布都很敏感。固定选择最后一个元素做基准时有序或近似有序数组会退化成 O(n²)赋值次数暴涨随机打乱过的数组赋值次数本身也有波动。单次实验落入好情况或坏情况的偶然性太大尤其 N1000 这个规模一次好运气可能让冒泡排序少跑一半交换单点结果毫无统计意义。解决多组种子取均值或对同一文件重复运行 5 到 10 次取中位数。做基准测试时永远保持同一份输入文件、同一个排序实现只改你想改的参数。我习惯把每次运行的种子、数据范围、CUTOFF 阈值记在输出里让实验日志自带“后悔药”过后能定位是哪一步改坏了结果。如果两组数据结论相反不要急着怀疑算法先回放输入文件和编译参数绝大多数冲突都是实验变量没有控制住造成的。6. 把赋值次数对比做成可重复的基准脚本自检与扩展技巧到这里你已经有一套能跑通的最小实验固定种子生成 1000 个数字用 C 插桩统计四种排序的赋值次数再用 Python 做多组均值。最后一步是让脚本自己验证结果可信。我一般会在 C 程序里加一个自检函数每次排序后判断 buf 是否已经升序一旦乱序立刻报错并退出。这个自检不花太多时间却能挡住绝大多数“计数对、排序错”的翻车现场。static int is_sorted(int arr[], int n) { for (int i 1; i n; i) { if (arr[i - 1] arr[i]) return 0; } return 1; }在主流程里每个排序函数跑完后补一句 if (!is_sorted(buf, N)) 就打印 FAIL。排序结果正确都保证不了赋值次数再低也没有意义。另一个验证技巧是把计数器输出和理论量级对号插入排序赋值次数大约在 n²/4 附近冒泡排序大约在 3n²/4 附近选择排序是 3n 量级快速排序是 n log n 量级。如果实测数量级差了一百倍优先怀疑输入文件错了或者计数点漏了而不是算法本身多神秘。再往下走你可以把实验朝三个方向扩展把 N 改成 5000、10000观察赋值次数随规模的增长是否符合复杂度曲线把数据换成唯一直分布或近乎有序数组测试相同算法在不同输入下的表现差异给快速排序加三数取中或切分阈值对比优化前后的赋值次数。这些扩展都不需要换语言或换框架仍然围绕“随机生成、排序、比较赋值次数”这个主轴转。我个人的操作习惯是把生成数据、跑排序、打印结果三步拆成三个独立小脚本留出 shell 管道这样调参数时不用反复改 C 代码也不会因为注释了某行导致数据文件被覆盖。说句实话这个实验最大的坑不是排序算法本身而是输入数据不干净、计数规则不统一。只要你每次跑实验前都先看一眼随机文件是否和预期一致每次排序前都恢复数组赋值次数这个指标就是可靠且可解释的。希望帮到你。本文还有配套的精品资源点击获取 排序算法赋值次数对比实验：用1000个随机数测四种排序
简介一份面向数据结构初学者的排序算法对比实践资源围绕随机生成一千个整数使用冒泡、插入、选择、快速、归并、堆排序等多种主流算法进行排序并统计赋值次数以量化比较各算法的操作开销帮助读者直观理解不同排序策略的时间性能差异。压缩包为RAR格式仅含1个C源文件包体大小约3KB代码紧凑且可直接运行适合本地编译验证。目前已有1627人学习/下载可服务于算法入门、课程实验与面试复习。资源核心价值在于提供完整的随机数生成与排序实现并嵌入赋值计数机制读者可自行调整数据规模和算法种类观察赋值次数与时间复杂度之间的关系进而加深对算法稳定性、原地排序等特性的理解。通过实际执行结果可直接对比不同算法的赋值次数差距为算法选型提供数据参考。1. 给 1000 个随机数字排序顺便把四种算法的赋值次数数清楚“排序算法”的复杂度课听再多都不如亲手对 1000 个随机数字跑一圈来得直观。这个实验的思路很直接随机生成 1000 个数字让插入排序、冒泡排序、选择排序和快速排序先后处理同一份数据再把每次对数组元素的赋值次数记下来。赋值次数比运行时间更接近算法本身的数据搬移成本也比比较次数更容易被忽略真正统计完你会发现选择排序的赋值次数低得反常而冒泡排序高得离谱。这套实验适合刚学完基础排序、想从赋值维度重新理解算法代价的人也适合要用数据说服别人“某某排序不该这么写”的场景。它不依赖任何第三方库一份 C 代码就能跑通。2. 随机生成 1000 个数字三种生成方式与分布形态如何左右赋值次数2.1 为什么排序实验要用可复现的伪随机序列随机生成数字听起来一句话的事但“随机”这两个字在实验里必须被驯服。如果你直接用系统时间当种子每次运行得到的数组都不一样排序算法的赋值次数自然也不一样第二天回来看结果会完全无法解释。我的做法是使用确定性伪随机序列给随机数生成器一个固定种子比如 42那么无论运行多少次生成的 1000 个数字都完全一致。这样插入排序和快速排序面对的输入是同一份计数差异才真正来自算法本身而不是输入数据的随机抖动。真随机数通常来自硬件熵源适合安全和统计抽样但排序实验要的是“可复现的随机”不是不可预测。伪随机数生成器PRNG的核心参数就是种子和范围种子决定序列起点范围决定数值落点。实际项目里可以准备几组固定种子比如 42、2024、7分别生成多组测试数据用来观察一组种子下的偶然波动。常见错误是在程序开头调用 srand(time(NULL))理由是“更像随机”结果每次跑出来的赋值次数都不同无法定位是算法差异还是输入差异。数据文件一旦生成就应该当成不可变的基准后续所有排序都从这份文件读入才算守住对照实验的底线。另外需要区分两个经常摆在一起的术语比较运算符判断两个值的大小关系赋值运算符把右侧的值写入左侧变量。排序算法的代价由比较次数和赋值次数组成交换元素时主要消耗在赋值上如果只盯着循环次数看很容易把两种代价混在一起。后面统计用的是赋值次数它度量的是数据搬了多少次对结构体、字符串这类大对象排序时赋值次数往往比比较次数更贴近真实的开销。2.2 用 C 语言和 Python 各生成一份随机数据文件先在 C 里生成一份基础输入文件。下面代码把 1000 个 0 到 9999 之间的随机整数写入 random_1000.txt每行一个数字。#include stdio.h #include stdlib.h #define N 1000 #define RANGE 10000 int main(void) { int data[N]; srand(42); // 固定种子保证每次运行得到同一组数字 for (int i 0; i N; i) { data[i] rand() % RANGE; // 值域 0~9999 } FILE *fp fopen(random_1000.txt, w); if (fp NULL) { perror(fopen); return 1; } for (int i 0; i N; i) { fprintf(fp, %d\n, data[i]); } fclose(fp); printf(generated %d numbers\n, N); return 0; }说明srand(42) 是整份数据的“后悔药”只要种子不变序列就固定实验翻车后还能回到同一份输入重新核对。RANGE 取 10000 而不是 100 或 10是为了让重复值比例可控数值范围太小1000 次抽样里会出现大量重复排序的比较和赋值次数都会被明显压低。fprintf 写纯文本是为了方便你用 Python、Java 或 Excel 打开同一份文件复现。Python 版更简洁适合快速做多组实验时用import random random.seed(42) data [random.randint(0, 9999) for _ in range(1000)] with open(random_1000.txt, w, encodingutf-8) as f: f.write(\n.join(str(x) for x in data))这里 random.seed(42) 的作用与 C 的 srand(42) 等价randint(0, 9999) 等价于 rand() % 10000。如果你想生成随机唯一值也就是 1000 个数字互不重复需要再加一个去重循环data [] seen set() while len(data) 1000: x random.randint(0, 9999) if x not in seen: seen.add(x) data.append(x)这样生成的数组没有重复元素适合用来观察“无重复输入下赋值次数的高位表现”但要注意它和真实随机抽样得到的重复率不同得到的结果不能混在一起比。实际做对比时我会为每种分布单独存文件文件名里带分布标签例如 random_uniform.txt、random_unique.txt、sorted_1000.txt避免后面统计时拿错输入。2.3 分布形态会把赋值次数带偏唯一值、重复值与近乎有序数组同样的排序算法在不同分布的输入上表现完全不一样。如果生成的数字只落在 0 到 19 之间1000 个位置里大量数字相同插入排序内部的 while 经常一两次就停赋值次数明显偏低如果数据本来有序插入排序几乎不做数据搬移。反过来把数组逆序生成插入排序每次都要把新元素一路搬回开头赋值次数接近最坏情况 O(n²)。因此实验之前就要确定你到底想测哪一种输入形态不能笼统说“跑一下看看”。实际排序性能对比里最常用的三个输入形态是均匀随机分布、随机唯一值分布、已有序或逆序数组。均匀随机分布用 rand() 取模最容易得到缺点是碰撞不可避免随机唯一值分布适合测所有元素都不相等时的行为近乎有序数组专门用来暴露插入排序的线性优势同时也会让固定基准的快速排序退化成 O(n²)。我一般会为每个形态单独生成数据文件并在实验记录里写清文件来源因为后续所有赋值次数结论都建立在这批输入的基础上。输入文件一旦混用统计数字再漂亮也是假的。这些数据文件用不着很大1000 个数字足够看出差异。更大规模比如 10000会让 O(n²) 算法跑到肉眼可见的慢赋值次数也会从几十万跳到几千万计数器类型要跟着从 int 换成 long long。鉴于是从 1000 起步我建议先固定 N1000 跑通流程再逐步扩大数组规模观察增长斜率这样既能验证理论复杂度又不会因为一次实验等太久。下一章就把计数规则落实成可编译的 C 代码。3. 用同一份数据跑四种排序算法赋值次数的计数规则与 C 实现3.1 赋值次数数的是什么数据移动与临时变量的边界排序算法性能比较的经典维度有两个比较次数和赋值次数。比较次数衡量的是“判断谁大谁小”的调用次数赋值次数衡量的是“把数据从一个位置搬到另一个位置”的执行次数。二者不是一回事交换一次元素比较可能一次都不发生但赋值必然发生。赋值次数越少说明算法搬运数据的开销越低在设计结构体、字符串等大对象排序时尤其关键因为一次记录的搬移可能是几十字节甚至几十 KB。这里必须把“赋值次数”的边界说清楚否则统计结果没法复核。我采用的规则是把数组元素或保存数组元素的临时变量发生一次写入就记一次赋值循环用的下标、min_idx 这类索引变量不计入。这样一次 swap(arr, i, j) 算三次赋值tmp arr[i]、arr[i] arr[j]、arr[j] tmp。插入排序里 key arr[i] 算一次arr[j1] arr[j] 每次后移算一次最后 arr[j1] key 算一次。选择排序外层交换里的三次赋值照算但 min_idx j 不算因为它更新的是下标不是数据。这套规则和数据结构排序算法教材里常用的“记录移动次数”基本一致便于做理论推导时对得上。实际统计时不要在算法内部到处手写 count容易漏。我的做法是把交换封装成函数其他排序函数一律通过这个函数交换插入排序的 key 操作显式计数。这样代码里只有少数几个计数点出错时一眼能找到。更稳妥的插桩方式是用宏包装赋值操作但 C 宏在组合下标时容易出现多次求值副作用得不偿失所以函数显式计数更可靠。3.2 用 C 语言实现计数插桩一个计数器与一套统一规则下面这段代码是整组实验的核心骨架。它先用 long long 声明全局计数器 assign_count避免 int 溢出reset_count 在每次排序前清零swap 函数在交换元素时精确计三次。注意这里我特意把临时变量 tmp 的赋值也算进去因为一次交换本质上就是三次数据搬移。#include stdio.h #include stdlib.h #include string.h #define N 1000 #define RANGE 10000 static long long assign_count; static void reset_count(void) { assign_count 0; } static void swap(int arr[], int i, int j) { if (i j) return; // 相同位置不搬避免无意义计数 int tmp arr[i]; assign_count; // tmp arr[i] arr[i] arr[j]; assign_count; // arr[i] arr[j] arr[j] tmp; assign_count; // arr[j] tmp }swap 里开头加一个 i j 判断能让选择排序在无需交换时不产生假的赋值次数。如果你希望统计“代码里赋值语句执行次数”可以去掉这个提前返回但那样该次交换会把 tmp 搬来搬去却没有实际改变数组对数据移动语义来说是噪声。跑实验前先决定自己遵循哪套规则并在实验记录里写清楚否则后期换一种统计口径结果会完全对不上。3.3 四种排序算法的赋值计数实现插入排序的赋值点有三类保存 key、后移元素、写回 key。注释里标出了每个 count 对应的语义。static void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; assign_count; // 把 arr[i] 搬到 key int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; assign_count; // 把 arr[j] 后移一位 j--; } arr[j 1] key; assign_count; // 把 key 写回正确位置 } }冒泡排序用 swap 完成交换所以赋值计数全部落在 swap 函数里。为了保留一个“已经有序就提前退出”的版本我加了 swapped 标记这会让有序数组的赋值次数直接逼近 0符合真实工程里常见写法。static 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]) { swap(arr, j, j 1); swapped 1; } } if (!swapped) break; } }选择排序的赋值点最少只有外层交换。内层只是不断更新 min_idx并不搬动数据。这正好体现了它的特征比较次数依然是 O(n²)但数据搬移量被压到了 O(n)。static 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) { swap(arr, i, min_idx); } } }快速排序这里选最后一个元素做基准。pivot arr[hi] 是一次数据搬移要计数后续 partition 过程中交换操作统一走 swap所以计数点也不散。static void quick_sort_range(int arr[], int lo, int hi) { if (lo hi) return; int pivot arr[hi]; assign_count; // pivot arr[hi] int i lo - 1; for (int j lo; j hi; j) { if (arr[j] pivot) { i; if (i ! j) { swap(arr, i, j); } } } if (i 1 ! hi) { swap(arr, i 1, hi); } quick_sort_range(arr, lo, i); quick_sort_range(arr, i 2, hi); }代码说明这个实现用了 Lomuto 分区优点是直观、计数点少缺点是有序数组下 i 会一路增长基准总在末端递归退化为 O(n²) 深度赋值次数也会暴涨。后续章节会给出改造方案。注意快速排序的 pivot 赋值计入赋值次数而普通临时变量不算这会让快速排序的统计比“只数交换”的常见做法多出 O(n) 级别的小量但和 O(n log n) 的主项相比可忽略。3.4 每次排序前必须复制原始数组否则结果全是假的排序算法是原地排序会把传入数组改得面目全非。如果先跑冒泡排序数组已经有序再跑插入排序插入排序遇到有序数组赋值次数只有几千这个结果显然不能拿来和冒泡的第一次结果比。因此主函数要维护一份原始数据 base每次调用排序函数前用 memcpy 恢复到工作缓冲区 buf。下面是主流程。int main(void) { int base[N], buf[N]; FILE *fp fopen(random_1000.txt, r); for (int i 0; i N; i) { fscanf(fp, %d, base[i]); } fclose(fp); memcpy(buf, base, sizeof(base)); reset_count(); insertion_sort(buf, N); printf(insertion %lld\n, assign_count); memcpy(buf, base, sizeof(base)); reset_count(); bubble_sort(buf, N); printf(bubble %lld\n, assign_count); memcpy(buf, base, sizeof(base)); reset_count(); selection_sort(buf, N); printf(selection %lld\n, assign_count); memcpy(buf, base, sizeof(base)); reset_count(); quick_sort_range(buf, 0, N - 1); printf(quick %lld\n, assign_count); return 0; }参数说明memcpy 的第三个参数用 sizeof(base) 而不是 N * sizeof(int)省得每次改 N 还要同步改这里base 在程序运行中始终不变。打印时用 %lld 对应 long long 计数器。跑完这一份四个算法的赋值次数就同框了。第 4 章会告诉你如何做多轮采样和结果解读。4. 排序算法赋值次数对比多轮采样的数据表与快速排序的阈值参数4.1 多轮采样用多个固定种子消除单组数据的偶然性单次实验只能证明“这一组 1000 个数字下”的赋值次数不能证明算法的一般表现。随机数组本身有方差快速排序的赋值次数对基准位置尤其敏感一组数据可能正好落在好分区或坏分区上。我一般会准备 5 个固定种子分别生成 5 组输入每组输入都让四种算法走一遍最后取平均或中位数。这样报告的赋值次数更接近期望值也能顺手看几种算法之间的方差。下面用一个 Python 脚本统一调度它调用前面编译好的 C 可执行程序并捕获 stdout 里的输出结果。这样做的好处是不用把 C 代码的统计逻辑再抄一份到 Python避免两套实现出来两种答案。import subprocess import statistics import random seeds [42, 2024, 7, 65535, 1] results {algo: [] for algo in [insertion, bubble, selection, quick]} for seed in seeds: # 每个种子生成一份数据文件交给 C 程序统计 random.seed(seed) data [random.randint(0, 9999) for _ in range(1000)] with open(random_1000.txt, w, encodingutf-8) as f: f.write(\n.join(map(str, data))) out subprocess.check_output([./sort_counter], textTrue) for line in out.strip().splitlines(): algo, count line.split() results[algo].append(int(count)) for algo, counts in results.items(): print(f{algo:10s} mean{statistics.mean(counts):10.0f} fmin{min(counts):10d} max{max(counts):10d})说明C 程序本身已经把数据从 random_1000.txt 读进来所以 Python 只负责换文件并重复调用。每个种子生成的文件覆盖上一次不会累积。statistics.mean 是标准库函数不需要额外安装。如果你的 C 程序输出里带了额外调试文字解析前先过滤掉非 “算法名 数字” 格式的行否则 int(count) 会抛异常。注意一个容易混淆的点Python 的 random.seed(42) 和 C 的 srand(42) 并不生成同一串数字这不影响实验。只要每次统计面对的是同一个文件“输入一致”这个条件就满足了。跨语言复现不需要两边的随机序列完全相同。4.2 实测结果表为什么选择排序赋值次数最少、耗时却不少按上述流程跑一轮赋值次数的数量级会落在下面这张表里。我没有把每次的精确数字写死因为换编译器、改分支写法都会造成几百到几千的波动但相对关系是稳定的。算法赋值次数种子 42N10005 组种子平均赋值次数增长插入排序约 25 万约 25 万O(n²)与逆序对数量相关冒泡排序约 75 万约 75 万O(n²)每次交换计 3 次赋值选择排序约 3 千约 3 千O(n)只有交换才搬数据快速排序约 3 万约 3 万O(n log n)分区交换主导表格里最反直觉的一项是选择排序赋值次数只有几千比快速排序还低一个数量级。原因在于它每趟只做一次交换内层循环只比较不搬移n1000 时最多 999 次交换每次 3 次赋值。但它一点也不快因为它做了大约 50 万次比较“少搬数据、多比较”是对它最准确的概括。这也说明赋值次数不是性能的全部它只反映数据搬移这一面评估排序算法要同时看赋值次数和比较次数。快速排序的 3 万次赋值比插入排序的 25 万次低一个数量级也印证了 O(n log n) 的优势从数据搬移角度同样成立。随着 N 从 1000 涨到 10000插入排序的赋值次数会往千万级走快速排序大约只到几十万级这个差距会比表格里更刺眼。如果你做的实验里冒泡排序赋值次数反而比插入排序少那多半是提前退出逻辑在有序数据上生效了后面第 5 章会专门讲这类陷阱。4.3 影响赋值次数的两个参数数据规模与快速排序的切分阈值数组规模是最直接的参数。赋值次数的绝对数字随 N 增大明显放大但每种算法的相对关系基本由复杂度决定。调 N 时顺便把工作缓冲区数组大小改掉同时确认计数器类型是 long long否则 O(n²) 算法在 N10000 时就能撞上 int 上限。N1000 时三种 O(n²) 算法尚能秒回N50000 时插入排序和冒泡排序要等好几秒正好用来演示复杂度差异。第二个参数是快速排序的小数组切分阈值。很多工程实现会在区间长度小于某个阈值时改用插入排序因为插入排序在小规模数组上常数小赋值次数也更少。下面是加了一个 CUTOFF 的版本#define CUTOFF 16 static void quick_sort_cutoff(int arr[], int lo, int hi) { if (hi - lo CUTOFF) { insertion_sort(arr lo, hi - lo 1); return; } int pivot arr[hi]; assign_count; int i lo - 1; for (int j lo; j hi; j) { if (arr[j] pivot) { i; if (i ! j) swap(arr, i, j); } } if (i 1 ! hi) swap(arr, i 1, hi); quick_sort_cutoff(arr, lo, i); quick_sort_cutoff(arr, i 2, hi); }重点看 CUTOFF 的取值太大会让 O(n²) 的插入排序处理大块数据赋值次数明显上升太小则递归过深小数组上的递归开销和额外交换没法被吸收。常见范围是 8 到 32取 16 是折中。调这个参数时你会在赋值次数上看到一个先降后升的曲线最低点附近就是当前环境下比较合适的阈值。这也顺带解释了为什么标准库的排序实现很少是“裸”快速排序它们普遍混用了插入排序和堆排序。如果不加任何优化快速排序在逆序数组上的表现会很糟固定选最后一个元素做基准每次分区都极度不平衡递归深度接近 n赋值次数会退化到 O(n²) 量级甚至比插入排序还高。三数取中是一种常见补救在 arr[lo]、arr[mid]、arr[hi] 中选中间值当基准可以避免最常见的有序输入退化。我把这个优化留给做扩展实验的读者先确认普通版本能跑通并且计数稳定再考虑改基准选择策略。5. 排序算法赋值次数统计的五个常见坑现象、原因与解决5.1 后面的排序算法拿到的是上一轮排好的数组赋值次数直接“崩”了现象冒泡排序先跑赋值次数 75 万紧接着插入排序对同一个数组跑赋值次数只剩几百。插入排序在近乎有序的数组上确实很快但这个结果不能用于算法对比因为输入已经不再是原始的 1000 个随机数了。更隐蔽的版本是四个算法按顺序跑前两个结果正常后两个结果全部偏低你还会误以为快速排序优化得很好。原因所有排序函数都是原地排序主循环里没有每次从原始数据恢复数组导致后跑的算法在有序或接近有序的数据上做无用功。赋值次数因此虚低结论完全失真。这个坑几乎每个做对比实验的人都会踩一次因为它不影响编译只影响结论不打印数组内容根本看不出来。解决在 main 函数里维护一份 base 数组每次调用排序前 memcpy 到 buf或者最土的办法每次排序前从 random_1000.txt 重新读文件。注意 memcpy 必须在排序调用之前完成reset_count 在哪一步都无所谓。我习惯把“先恢复输入、再清零计数、再排序”固定成一个三步流程少一步都算污染样本。排序完成后还可以顺手检查 buf 是否有序防止计数对但排序本身出错。5.2 固定了种子却每次跑结果不一样怀疑自己写了假代码现象明明在 2.2 的代码里有 srand(42)但连续运行两次快速排序的赋值次数一次是 3 万、一次是 6 万插入排序也跟着变。你可能觉得“种子固定了怎么会变”于是开始怀疑编译器或者量子涨落实际上原因通常很朴素。原因最可能是生成数据与排序没有在同一个程序里同步。比如你用 C 程序生成数据后又用 Python 脚本重新生成 random_1000.txtPython 的随机序列和 C 的 rand() 完全不同或者程序里 srand(42) 之外另有模块偷偷调用了 srand(time(NULL))把序列重置了。还有一层原因是 C 的 rand() 在不同平台上的实现不一样同一份代码在 Linux 和 Windows 下生成的序列不同所以跨平台对比时不能要求绝对数字一致只能对比相对趋势。解决一旦生成好数据文件就把它当作只读文件对待排序程序只读取、不生成。固定种子的意义在于复现不在于“随机”本身。每次排序前先打印数组前五个元素核对是否与预期一致这个动作花不了几毫秒却能挡住大部分数据错乱问题。跨平台对比时先确认输入的 1000 个数字完全相同再比较赋值次数才有意义。5.3 开编译器优化后计数变成零和负数排序像被“吞”了现象调试版编译得到正常计数改成 -O2 编译输出变成 0或者中间结果乱码增加数组规模后冒泡排序的赋值次数甚至出现负数。第一次遇到这个问题的反应往往是“程序写错了”但同样的代码换个优化级别又正常最容易让人一头雾水。原因两个问题可能叠加。负数大概率是计数器 int 溢出N1000 时冒泡排序约 75 万次赋值int 能扛住但如果同时把 N 改成 100000赋值次数轻松突破 21 亿int 溢出后回绕成负数。计数为 0 则可能是编译器看到排序结果没有被使用把整个排序函数判定为死代码消除尤其在 -O2 以上优化级别常见。计数器变量如果被优化到寄存器且从未被外部读取也会出现看似正常的代码却输出保留值。解决计数器一律用 long long输出用 %lld。为了防死代码消除排序后不要把结果丢掉至少打印数组前三个元素或者算一个数组元素的校验和再输出。更直接的办法是把 assign_count 声明成 volatile long long让编译器知道这个变量的写操作可能有外部副作用但真正可移植的解法是让实验结果被后续逻辑消费掉。检查计数是否有效的一个办法是把 N1000 的插入排序赋值次数和理论量级对比应该在十几万到二十几万之间如果只有几百基本可以断定排序被编译器优化掉或者输入文件错乱。5.4 选择排序赋值次数最低但运行耗时比冒泡排序还长现象计时测试里选择排序的赋值次数只有几千次但运行耗时和冒泡排序不相上下甚至更慢。你会开始怀疑赋值次数这个指标有没有意义是不是统计错了。原因赋值次数只统计数据搬移次数选择排序内层循环的大量比较并没有纳入赋值计数。它用 O(n²) 次比较换来 O(n) 次交换赋值次数确实漂亮但比较指令一样吃 CPU 时间。赋值次数低和运行时间短不是一回事比较次数、缓存行为、分支预测都会影响最终耗时。对 int 数组来说比较比数据搬移还贵的情况并不少见。解决把赋值次数和比较次数同时统计观察选择排序“比较次数约等于冒泡、赋值次数远低于冒泡”的组合才能解释为什么它赋值最少却慢。扩展方法是在所有 if 条件判断处增加 compare_count比如static long long compare_count; static 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) { compare_count; // 一次侵入比较 if (arr[j] arr[min_idx]) { min_idx j; } } if (min_idx ! i) { swap(arr, i, min_idx); } } }定义好计数规则后每个算法的 “比较次数 / 赋值次数” 组合就完全不同插入排序比较和赋值都随逆序对走选择排序比较极多但赋值极少冒泡排序两者都不少。实际工程里排序对象如果是几十字节的结构体赋值次数对耗时的权重会上升如果只是 int 数组比较次数往往占主导。所以不要拿着赋值次数单一指标去仲裁算法优劣它只负责说清楚“搬数据”这一面。5.5 只跑一次就下结论把“玄学波动”当成算法差异现象某一次快速排序赋值次数 1.2 万另一次却 5 万于是得出结论“快速排序不稳定别用”。细看两次的数据文件并不相同或者一次跑了切分阈值版本另一次跑的是普通递归版结论自然南辕北辙。原因快速排序的赋值次数对基准选择和数据分布都很敏感。固定选择最后一个元素做基准时有序或近似有序数组会退化成 O(n²)赋值次数暴涨随机打乱过的数组赋值次数本身也有波动。单次实验落入好情况或坏情况的偶然性太大尤其 N1000 这个规模一次好运气可能让冒泡排序少跑一半交换单点结果毫无统计意义。解决多组种子取均值或对同一文件重复运行 5 到 10 次取中位数。做基准测试时永远保持同一份输入文件、同一个排序实现只改你想改的参数。我习惯把每次运行的种子、数据范围、CUTOFF 阈值记在输出里让实验日志自带“后悔药”过后能定位是哪一步改坏了结果。如果两组数据结论相反不要急着怀疑算法先回放输入文件和编译参数绝大多数冲突都是实验变量没有控制住造成的。6. 把赋值次数对比做成可重复的基准脚本自检与扩展技巧到这里你已经有一套能跑通的最小实验固定种子生成 1000 个数字用 C 插桩统计四种排序的赋值次数再用 Python 做多组均值。最后一步是让脚本自己验证结果可信。我一般会在 C 程序里加一个自检函数每次排序后判断 buf 是否已经升序一旦乱序立刻报错并退出。这个自检不花太多时间却能挡住绝大多数“计数对、排序错”的翻车现场。static int is_sorted(int arr[], int n) { for (int i 1; i n; i) { if (arr[i - 1] arr[i]) return 0; } return 1; }在主流程里每个排序函数跑完后补一句 if (!is_sorted(buf, N)) 就打印 FAIL。排序结果正确都保证不了赋值次数再低也没有意义。另一个验证技巧是把计数器输出和理论量级对号插入排序赋值次数大约在 n²/4 附近冒泡排序大约在 3n²/4 附近选择排序是 3n 量级快速排序是 n log n 量级。如果实测数量级差了一百倍优先怀疑输入文件错了或者计数点漏了而不是算法本身多神秘。再往下走你可以把实验朝三个方向扩展把 N 改成 5000、10000观察赋值次数随规模的增长是否符合复杂度曲线把数据换成唯一直分布或近乎有序数组测试相同算法在不同输入下的表现差异给快速排序加三数取中或切分阈值对比优化前后的赋值次数。这些扩展都不需要换语言或换框架仍然围绕“随机生成、排序、比较赋值次数”这个主轴转。我个人的操作习惯是把生成数据、跑排序、打印结果三步拆成三个独立小脚本留出 shell 管道这样调参数时不用反复改 C 代码也不会因为注释了某行导致数据文件被覆盖。说句实话这个实验最大的坑不是排序算法本身而是输入数据不干净、计数规则不统一。只要你每次跑实验前都先看一眼随机文件是否和预期一致每次排序前都恢复数组赋值次数这个指标就是可靠且可解释的。希望帮到你。本文还有配套的精品资源点击获取