简介面向算法初学者与编程学习者该C项目演示如何随机生成1000个数字并利用冒泡、插入、选择、快速、归并、堆排序等六种常见排序算法进行排序同时统计各算法的赋值次数直观比较不同算法的运行开销与性能差异适合用于算法课程实验、期末作业参考或自学练手。资源为单个cpp源文件压缩包整体仅3KB结构精简、无冗余依赖可直接在主流C编译环境中运行便于读者快速查看核心实现并动手修改测试。已有1627人浏览学习该资源。通过阅读源码读者可以掌握使用C 库生成随机数的具体写法并理解不同排序算法的实现思路与赋值次数统计方式进而在实际场景中更准确地评估算法效率。1. 先说说这个题目到底在考什么随机 1000 个数字为什么要盯住赋值次数在算法课和面试题里“随机生成 1000 个数字用排序算法排序并比较算法的赋值次数”是一道出现率很高的动手题。多数人拿到它第一反应是把冒泡、插入、归并各跑一遍然后输出比较次数可一旦把观察点换成赋值次数代码里的交换、移动、临时数组拷贝就会变成一笔糊涂账。比较次数在每本教材里都写得清楚赋值次数却往往被语言层的交换语法和递归开销搅浑。赋值次数直接反映数据搬移的代价搬一次元素就是一次内存写操作比“比一次大小”更贴近真实开销。这篇文章从随机数组怎么生成、计数器怎么埋点到三种排序的实测数值与常见统计陷阱按可以复现的粒度写给你。2. 随机生成 1000 个数字数据源不定好结果全是玄学排序对比实验最容易被质疑的就是数据来源。同样是 1000 个随机整数有的种子生成接近有序有的生成大量重复冒泡和插入的赋值次数差出几千一点都不奇怪。所以第一步不是写排序而是把数据源封死。实验全部用 Python 3 写随机模块用random.seed控制排序函数按第三章的计数器统一埋点。2.1 用 random.seed 锁住随机序列同一个种子同一批数字Python 的 random 模块默认从系统熵拿种子两次运行生成的序列大概率不同。对算法对比来说这意味着冒泡和插入排序可能被喂给了两组不同的输入最后谁快谁慢完全说不清。常见做法是实验开头固定random.seed(42)把待排序数组生成一次再分发给所有排序函数。import random random.seed(42) arr [random.randint(0, 10000) for _ in range(1000)] print(len(arr), min(arr), max(arr))逻辑说明random.seed(42)之后arr 序列完全确定。1000 个元素每个都是 0 到 10000 的整数randint是闭区间上限 10000 可能被取到。这里要特别注意randint允许重复是从离散均匀分布里采样而random.sample(range(10000), 1000)是从 10000 个候选值里无放回抽 1000 个得到的是随机生成唯一值。这两种数组对排序结果的影响会在 2.2 节展开。参数说明种子 42 没有特殊含义只是保证可复现。发布实验结果时写明种子即可。范围我习惯取 0~10000因为值域远大于长度 1000重复率不至于太高。如果你想制造更多重复可以把范围缩到 0~1000赋值次数会明显变化原因在于相等元素会跳过搬移分支。自检方式也简单len(set(arr))和len(arr)的差能直接告诉你重复了多少。2.2 允许重复还是随机生成唯一值两种数据分布会带偏赋值次数“随机生成唯一值”和“随机生成数字”在题目里经常被混用。前者要求不重复后者允许重复。很多学习者在交作业时用random.sample代码没问题但结论不能和允许重复的数据混在一起发。# 方式一允许重复默认实验 data_repeat [random.randint(0, 10000) for _ in range(1000)] # 方式二随机生成唯一值10000 个候选里抽样 1000 个 data_unique random.sample(range(10000), 1000) # 方式三先造有序数组再打乱可控逆序度 base list(range(1000)) random.shuffle(base)逻辑说明random.sample要求候选池长度大于等于抽样数否则抛出异常。data_unique没有重复元素可以让“相等不移动”这个分支完全不参与测试。第三种方式的数据来自 0..999实际是洗牌后的唯一值数组适合用来控制逆序度洗牌次数少数组接近有序洗牌次数多逆序度接近随机。三者生成的数据形态不同赋值次数也会不同后续所有排序必须跑在同一份输入或同一份输入的副本上不能混用。三种输入对实验结论的影响可以按下表理解。生成方式重复值逆序可控性适合场景randint有不可控默认的随机数组random.sample无不可控随机生成唯一值rangeshuffle无中等需要可解释的逆序度变化最后一句话要重复三遍排序函数内部会修改数组所以每个算法开始前都要复制一份输入。不复制第二个算法拿到的是第一个算法排好的有序数组赋值次数直接变成最好情况实验全部作废。我一般在run_experiment里统一做data[:]避免各排序函数各自复制导致的口径差异。3. 先把“赋值一次”的口径钉死计数器埋在哪才算公平排序实验最怕规则不清。“赋值次数”和“比较次数”“交换次数”这三个概念经常被混用。我的口径是只要数组元素从一个位置搬到另一个位置无论是否经过临时变量都算一次赋值。这个定义确定了计数器才不会埋错。3.1 赋值、比较、交换三类操作各自的计数点在哪里比较次数由比较运算符驱动赋值次数对应赋值运算符的触发。这就像比较运算符和赋值运算符名字只差一个字语义却完全不同。排序代码里最容易漏的是两类一类是交换的二次读数另一类是归并临时数组的写入和回写。为了统一我用一个计数器类包住所有计数点。class Counter: def __init__(self): self.assign 0 self.compare 0 def swap(self, arr, i, j): t arr[i] arr[i] arr[j] arr[j] t self.assign 3逻辑说明swap方法把交换固化成一个入口所有需要交换的算法都走它赋值次数按三次记。为什么不把 Python 的a[i], a[j] a[j], a[i]算成一次因为多元赋值在底层也是先取值、再依次写入两个位置至少发生两次写操作如果按“数据搬移一次算一次”的口径保守起见记三次最稳。比较计数放在if条件处counter.compare 1必须在判断前执行。for循环自增、while条件里的下标自增都不算数据搬移不要统计进去。如果你要用 C 语言排序算法实现同一套实验规则完全一样只是临时变量要自己声明交换入口同样按三次赋值。计数规则汇总如下。操作示例赋值计数arr[j1] arr[j]1key arr[i]1temp arr[i]; arr[i] arr[j]; arr[j] temp3归并写入临时数组1归并从临时数组回写原数组1i i 1下标自增0计数器推荐用类对象不要用全局变量加global。类实例作为参数传入排序函数递归调用时不会因为作用域问题丢失累加值。这一点在第四章归并排序里尤其关键。3.2 测试框架同一份输入、每个算法跑五轮、取中位数单次运行的结果受输入顺序影响很大。冒泡和插入在几乎有序的数组上赋值次数接近在逆序数组上一个天上一个地下。为了得到稳定结论我固定种子后把同一份数据分发给所有算法每个算法跑五轮取赋值次数中位数。def run_once(sort_func, data, counter): counter.assign 0 counter.compare 0 arr data[:] # 副本保证各算法拿到相同初始顺序 sort_func(arr, counter) return counter.assign, counter.compare def run_experiment(sort_func, data, rounds5): results [run_once(sort_func, data, Counter()) for _ in range(rounds)] results.sort() return results[len(results) // 2] # 中位数逻辑说明run_once里先清零计数器再复制数据。复制动作本身不计数因为我们要的是排序过程内部的数据搬移量不是测试框架的复制开销。每个算法跑五轮取中位数可以避免某些排序在数据规模边界上因为递归深度或分区选择产生的微小波动。参数说明rounds5够用取 9 也可以但不要取偶数否则中位数是两个值的平均报告里解释起来麻烦。data[:]成立的前提是数组里放的是不可变整数如果换成字符串数组或对象数组浅复制会带出引用共享的坑这里全部用整数就不用担心。4. 冒泡、插入、归并的赋值次数如何埋点三个可运行版本在数据结构排序算法里冒泡、插入、归并是经典对照组前两者贴着数组移动归并靠额外空间换时间。下面每个算法都直接给出可运行版本并标注赋值计数点。4.1 冒泡排序一次交换记三次赋值最好情况权当验证冒泡排序的赋值次数最容易算错。很多人把“交换”当成一次赋值实际一次交换要经过临时变量中转。由于Counter.swap统一记三次这里代码很干净。def bubble_sort(arr, counter): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): counter.compare 1 if arr[j] arr[j 1]: counter.swap(arr, j, j 1) swapped True if not swapped: break逻辑说明每一轮冒泡把当前未排序区间的最大值推到末尾n - 1 - i保证已排序部分不再参与比较。swapped是提前退出标记某一轮完全没有交换说明数组已经有序可以提前结束。赋值次数的来源只有counter.swap每次交换三次赋值。比较次数在if之前累加for循环自己的条件判断不计入。参数说明对 1000 个随机整数普通冒泡最坏情况约 499500 次比较交换次数等于数组逆序对数量赋值次数约等于逆序对数量的三倍。数组有序时赋值次数为 0比较次数仍然是 n-1 次。你会发现赋值次数和比较次数在这里出现了明显背离一个可以为 0一个永远大于等于 n-1。这是冒泡排序最值得在报告里讲清楚的观察点。4.2 插入排序移动一次算一次赋值数值近似逆序度插入排序是赋值次数最直观的算法把一个元素往前插需要把一串元素往右挪每次挪动就是一次赋值。整体赋值次数近似等于逆序度加插入开销。def insertion_sort(arr, counter): n len(arr) for i in range(1, n): key arr[i] counter.assign 1 # 取出待插入元素 j i - 1 while j 0 and arr[j] key: counter.compare 1 arr[j 1] arr[j] # 右移一次 counter.assign 1 j - 1 arr[j 1] key counter.assign 1 # 写回插入位置逻辑说明外层从第二个元素开始key arr[i]算一次赋值。内层while每次比较触发一次移动arr[j1] arr[j]是一次赋值。最后arr[j1] key写回再记一次。整体赋值次数 移动次数 2 × 已插入元素数量。这里比很多教材只写“移动次数”更严格因为key的读写也是真实发生的数据搬移。参数说明arr[j] key用严格大于相等元素不会继续移动排序是稳定的。如果改成相等元素也会右移赋值次数明显上涨排序失去稳定性。对随机数组插入排序的比较次数与赋值次数都在 n²/4 量级而冒泡的赋值次数约为逆序对数量三倍同样是 n²/4 量级的三倍。所以 n1000 时插入排序赋值次数通常比冒泡少一截但两者量级相同要到 n10000 才能看到更明确的倍数差。4.3 归并排序临时数组写入和回写都计别把切片当黑匣子归并排序把数组不断对半分再两两合并。合并时先把元素写进临时数组再回写到原数组。这两段都必须计入赋值次数否则统计出的赋值次数会低到失真甚至比冒泡还少。def merge_sort(arr, counter): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid], counter) right merge_sort(arr[mid:], counter) return merge(left, right, counter) def merge(left, right, counter): result [] i j 0 while i len(left) and j len(right): counter.compare 1 if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 counter.assign 1 while i len(left): result.append(left[i]) i 1 counter.assign 1 while j len(right): result.append(right[j]) j 1 counter.assign 1 return result逻辑说明merge_sort每次切片后递归merge中每append一个元素到result算一次赋值两个收尾while处理剩余元素也各算一次赋值。这种写法是“生成新数组”的归并切片发生在 Python 层严格讲切片本身也是一次次赋值。为了口径统一统计时不计切片只计merge内部的数据搬移。如果你做真正的原地归并需要在回写临时数组时再计数一次结论不会改变量级。参数说明left[i] right[j]用小于等于保证稳定改成时重复值会多走右分支比较次数上升赋值次数不变。切片归并的空间复杂度高但便于教学统计因为赋值点高度集中。归并排序的赋值总量大约与 n log n 同阶比冒泡和插入的 n² 量级低一个档。实测 1000 个随机数时归并赋值次数通常比插入还低这是算法复杂度决定的不是统计漏项但如果你看到归并赋值次数比冒泡还低一个量级以上先检查第五章第三个坑。如果还要加入快速排序对比常见做法是让所有交换走同一个counter.swap分区里的每次交换记三次赋值递归本身不额外计数。计数入口不变这里就不单独展开。5. 避坑指南赋值次数统计里最常翻车的五个现场把计数器埋好之后跑出来的数据仍然可能怪到离谱。以下五个坑是我实际踩过、也帮别人排查过的按现象、原因、解决的顺序写方便直接对照。5.1 递归计数器神秘清零现象归并排序跑完assign只有几百比预期低一个量级。单独打印merge里的计数值又显示每次都在累加但最终结果就是不对。原因递归函数里把Counter对象当普通变量重新赋值了。最常见的是在merge_sort开头写了一句counter Counter()每次递归都新建计数器最后只会留下最深层递归的那一份数据。另一种写法是把计数值作为返回值传但漏掉了某个递归分支的累加导致一半计数值丢弃。解决让所有排序函数共享同一个计数器对象不要在递归内部重新创建。用本章的Counter类实例即可它是可变对象传入递归后所有都是对同一个对象的修改。如果坚持用返回值累加必须在每个递归出口把返回值加起来少一条分支都会出问题。5.2 把交换当成一次赋值数字少了三分之二现象冒泡排序跑随机 1000 个数逆序对大约 25 万个赋值次数理论接近 75 万但计数器只有 25 万左右。原因写的是a[i], a[j] a[j], a[i]并且把整句当成一次赋值。Python 多元赋值底层要先读取两个值再按顺序写回实际发生的是两次写操作按“数据搬移”口径计算至少是两次如果按临时变量中转的教科书写法就是三次。解决所有交换统一走counter.swap。只要代码里还有一个地方用手写的多元赋值交换冒泡的赋值次数就会少算。排查手段也简单在实验里搜一遍a[.*], .* .*[.*], .*[.*]这种模式见到就替换成swap入口。5.3 归并排序的赋值次数比冒泡还低现象相同输入下归并排序assign只有冒泡的一半和教材里 n log n 与 n² 的差距完全对不上甚至出现归并比插入排序还低两个量级。原因只统计了回写到原数组的赋值没有统计临时数组的写入。merge里result.append(left[i])把数据从原数组搬到了临时数组这是实际发生的一次赋值如果漏掉整个归并的赋值次数少了一半还不止。解决把“进入临时数组”和“从临时数组回写”都各计一次。用上文的merge实现时append一次加一分收尾while里的append也要加。原地归并的写法更麻烦需要把临时数组传入并在主函数里统一计数别只数arr[lok] temp[k]。5.4 三个算法各跑一批随机数据结论无法解释现象同一台机器上冒泡某次跑得比插入快换一个种子结论又反过来。报告里的数值每次运行都变无法给任何人复现。原因每个排序函数都在入口自己生成了数组或者实验里多次调用random.seed但没有保持顺序一致。不同算法拿到不同输入比较和赋值次数自然不可比。解决统一在实验开头random.seed一次生成一份data所有算法通过run_once里的data[:]拿自己的副本。我还会把这份data存成文件后续实验直接从文件读入这样即便换机器数据还是一模一样。想更严格就在输出里打印数据的哈希值确保每个算法吃的是同一批数字。5.5 切片赋值吞噬计数统计结果直接失真现象归并排序里写了arr[0:len(merged)] merged赋值次数统计只有几十远低于预期。数据规模越到面容越离谱。原因切片赋值由 Python 解释器底层批量完成源码里看不到逐元素搬移计数器自然拦不住。内置list.sort同理它们把数据搬移藏进了黑匣子统计到的不是你的算法而是解释器。解决不要用切片赋值实现归并回写。把arr[lo:hi] merged改成for k in range(len(merged)): arr[lo k] merged[k]并在循环里counter.assign 1。宁可显式循环慢一点也要让每一次赋值都暴露在计数点下。这个坑最隐蔽因为代码看起来一点问题都没有结果却完全不能用。6. 进阶验证把 1000 个数字扩展成 500 到 10000 的曲线赋值次数统计完成之后先别急着下结论。把 n 从 1000 扩大到多个规模可以验证计数器的正确性也能看出每个算法到底呈什么量级。这是我每次做完实验必做的收尾工作。6.1 量级增长是否对得上用 log-log 斜率验证把 n 作为参数传入实验取 500、1000、2000、5000、10000 五个规模每个规模固定同一个种子。二者期望不同冒泡和插入的赋值次数接近 n²归并接近 n log n。画 log-log 图时前两者斜率接近 2后者接近 1。如果斜率动辄 3说明计数器里混进了循环自增。for n in [500, 1000, 2000, 5000, 10000]: random.seed(7) data [random.randint(0, 10000) for _ in range(n)] for name, func in [(bubble, bubble_sort), (insert, insertion_sort)]: assign, compare run_experiment(func, data) print(n, name, assign, compare)逻辑说明random.seed(7)放在每个 n 内部保证不同规模各有一份数据且冒泡和插入拿到的输入顺序一致。打印出来的assign随着 n 翻倍冒泡和插入大约变为四倍归并大约变为两倍多一点。如果冒泡赋值次数增长远超过四倍优先怀疑比较条件里混入了赋值操作。6.2 一个最顺手的最坏情况检测正序、逆序、随机三组数据只跑随机数据看不出计数器的边界。我会用同一算法在正序、逆序、随机三组数据上各跑一次检验赋值次数是否符合常识。以插入排序为例这一项几乎能立刻暴露计数漏项。random.seed(7) n 1000 asc list(range(n)) desc list(range(n, 0, -1)) rand [random.randint(0, 10000) for _ in range(n)] for label, data in [(asc, asc), (desc, desc), (rand, rand)]: assign, _ run_experiment(insertion_sort, data) print(label, assign)逻辑说明插入排序在正序数组上每个元素只需取出和写回赋值次数接近 2n逆序数组上每个新元素都要移动到最前面赋值次数接近 n²/2随机数组落在两者中间。如果你看到正序数组的赋值次数也有几十万说明计数器把key的重复读取或循环变量自增也算进去了。这个三组对照是我判断计数口径是否正确的最后防线。做这些实验我自己的流程是先固定种子生成一份数据并保存再用统一计数器跑三种排序最后用多规模曲线和三组输入对照验证。赋值次数确实比比较次数更容易翻车但只要把“数据搬移一次记一次”这个口径贯彻到底结果就能稳定复现。希望这个计数口径和验证方法帮到你。本文还有配套的精品资源点击获取