简介这份资源面向正在学习数据结构与算法、希望直观理解排序算法性能差异的编程学习者核心内容是用C随机生成1000个数字再分别用多种排序算法完成排序并统计各算法的赋值次数以比较效率。包内共1个文件为单个cpp源码文件压缩包约3KB代码结构紧凑可直接编译运行便于快速上手实验。资源围绕冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等经典算法展开通过计数赋值操作让抽象的复杂度分析落到可量化的数据上帮助读者观察不同算法在同一组随机数据下的实际表现差异。已有1627人学习下载适合作为算法课程的配套练习或自学时的对比实验素材读者可借此加深对时间复杂度、稳定性与原地排序等概念的理解并在此基础上扩展更多算法或调整数据规模进行验证。1. 排序算法对比实验为什么“赋值次数”比耗时更能暴露算法本性跑排序算法对比时大多数人第一反应是掐表看耗时。但同一台机器上跑 1000 个随机数冒泡和快排的耗时差距可能只有几毫秒计时器抖动就能把结论搅浑。赋值次数不一样——它是确定性的同一组数据跑一百遍结果完全一致跟 CPU 频率、后台进程、编译器优化都没关系。标题里说的“随机生成 1000 个数字用排序算法排序并比较赋值次数”本质上是在做一件很聪明的事用赋值次数这个硬指标把冒泡、插入、选择、归并、快速排序的底层行为差异量化出来。这篇文章面向正在学数据结构、准备算法面试、或者想给自己项目选排序方案的开发者。我会从数据生成开始一步步搭出一个可复现的对比框架把每种排序的赋值次数跑出来再解释数字背后的含义。全程用 Python 实现代码可以直接抄去跑。2. 实验框架搭建从随机数生成到赋值计数器2.1 为什么选赋值次数作为核心指标赋值次数统计的是排序过程中元素被写入数组的次数。交换两个元素算 3 次赋值temp a; a b; b temp插入排序里每次移位算 1 次赋值。这个指标直接反映算法对内存的写入压力。在嵌入式场景里写 Flash 比读 Flash 慢一个数量级赋值次数少意味着寿命长在数据库排序中赋值次数多意味着更多的脏页和日志写入。耗时受太多因素干扰赋值次数是算法的“指纹”。我一般会同时记录比较次数和赋值次数但赋值次数作为主指标。比较次数受数据分布影响大赋值次数更能体现算法结构差异。比如选择排序的比较次数固定是 n(n-1)/2但赋值次数在最好情况下是 0已经有序时每次只做一次自赋值判断最坏情况是 3(n-1)。这个差异在 1000 个数的规模下会非常明显。2.2 生成 1000 个随机数的三种分布不要只生成一种随机分布。我习惯生成三组数据完全随机、近乎有序随机交换 10 对、逆序。这样能看出算法在不同场景下的赋值次数波动。用 Python 的 random 模块固定种子保证每次生成的数据一样。import random def generate_data(n1000, seed42, moderandom): 生成测试数据 n: 数据规模 seed: 随机种子保证可复现 mode: random / nearly_sorted / reversed random.seed(seed) data list(range(n)) if mode random: random.shuffle(data) elif mode nearly_sorted: # 近乎有序只随机交换 10 对 for _ in range(10): i, j random.randint(0, n-1), random.randint(0, n-1) data[i], data[j] data[j], data[i] elif mode reversed: data.reverse() return data这段代码的关键是random.seed(seed)。固定种子后每次运行生成的随机序列完全一致别人复现你的实验时不会因为数据不同导致赋值次数对不上。nearly_sorted模式只交换 10 对模拟实际业务中“大部分已排好少量新增数据”的场景。reversed模式是很多排序算法的最坏情况比如冒泡排序在逆序时赋值次数拉满。2.3 赋值计数器的实现方式计数器不能侵入排序逻辑本身否则会改变算法行为。我的做法是写一个包装类重载__setitem__方法每次数组元素被赋值时自动加一。这样排序函数完全不用改直接操作这个包装对象就行。class CountedList: 带赋值计数器的列表包装类 def __init__(self, data): self._data list(data) self.assign_count 0 # 赋值次数 self.compare_count 0 # 比较次数 def __getitem__(self, index): return self._data[index] def __setitem__(self, index, value): self._data[index] value self.assign_count 1 def __len__(self): return len(self._data) def to_list(self): return list(self._data)__setitem__里每次赋值都让assign_count加一。注意__getitem__不计数因为读取不改变内存状态。比较次数需要单独在排序函数里手动加因为 Python 没有运算符重载来拦截和。这个设计的好处是排序函数可以原封不动地复用标准写法只需要把列表换成CountedList实例。提示不要用list.__setitem__的猴子补丁会污染全局列表行为导致其他代码的赋值也被计数。3. 五种排序算法的赋值次数实测与对比3.1 冒泡排序赋值次数为什么在逆序时爆炸冒泡排序的赋值发生在交换操作。每次交换需要 3 次赋值。逆序时每一轮都要把当前最大元素冒泡到末尾交换次数是 n(n-1)/2赋值次数就是 3n(n-1)/2。1000 个数就是约 150 万次赋值。这个数字很吓人但更吓人的是它在近乎有序时的表现——如果只交换 10 对冒泡排序仍然要跑完所有轮次只是内层循环不触发交换赋值次数接近 0。def bubble_sort(arr): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): arr.compare_count 1 if arr[j] arr[j 1]: # 交换需要 3 次赋值 temp arr[j] arr[j] arr[j 1] arr[j 1] temp swapped True if not swapped: break # 提前退出近乎有序时赋值次数为 0 return arrswapped标志位是关键优化。没有它冒泡排序在已经有序的数组上仍然跑满 n-1 轮虽然不交换但比较次数拉满。加上之后第一轮发现没有交换就直接退出赋值次数为 0。这个细节在对比实验里必须体现否则冒泡排序在近乎有序场景下的优势会被掩盖。3.2 插入排序赋值次数与数据初始有序度的关系插入排序的赋值发生在元素后移和插入。每次后移是 1 次赋值插入是 1 次赋值。逆序时每个元素都要移到最前面赋值次数约 n(n-1)/2 n。随机数据下大约是逆序的一半。近乎有序时每个元素最多移动一两次赋值次数接近 n。def insertion_sort(arr): n len(arr) for i in range(1, n): key arr[i] # 读取不计数 j i - 1 while j 0: arr.compare_count 1 if arr[j] key: arr[j 1] arr[j] # 后移1 次赋值 j - 1 else: break arr[j 1] key # 插入1 次赋值 return arr注意key arr[i]这行不触发__setitem__因为它是读取。arr[j1] arr[j]和arr[j1] key才触发计数。插入排序在近乎有序数据上的赋值次数极低这是它比冒泡排序更适合实际业务的原因——很多业务数据本身就是基本有序的新增几条记录后重新排序插入排序的赋值次数可能只有几百次。3.3 选择排序赋值次数最稳定的算法选择排序的赋值次数非常稳定。每轮找到最小值后如果最小值不在当前位置交换一次3 次赋值。最多 n-1 次交换赋值次数最多 3(n-1)。1000 个数最多 2997 次赋值。这个数字和冒泡、插入的百万级形成鲜明对比。def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): arr.compare_count 1 if arr[j] arr[min_idx]: min_idx j if min_idx ! i: # 交换3 次赋值 temp arr[i] arr[i] arr[min_idx] arr[min_idx] temp return arrif min_idx ! i这个判断很重要。如果最小值就在当前位置不做交换赋值次数为 0。在近乎有序的数据上选择排序的赋值次数可能接近 0。但它的比较次数固定是 n(n-1)/2约 50 万次。所以选择排序适合“赋值昂贵但比较廉价”的场景比如元素是大型结构体交换成本高但比较只涉及一个整型字段。3.4 归并排序赋值次数与额外空间开销归并排序的赋值发生在合并阶段。每次从临时数组写回原数组算 1 次赋值。每层合并总共写回 n 个元素共 log2(n) 层赋值次数约 n*log2(n)。1000 个数约 10000 次赋值。这个数字比冒泡和插入小两个数量级但比选择排序大。def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) # 合并 i j k 0 while i len(left) and j len(right): arr.compare_count 1 if left[i] right[j]: arr[k] left[i] # 1 次赋值 i 1 else: arr[k] right[j] # 1 次赋值 j 1 k 1 while i len(left): arr[k] left[i] i 1 k 1 while j len(right): arr[k] right[j] j 1 k 1 return arr归并排序的赋值次数是确定性的和初始数据顺序无关。随机、近乎有序、逆序三种情况下赋值次数几乎一样。这是它的优势——性能可预测。但代价是需要额外空间。arr[:mid]和arr[mid:]会创建新列表这些切片操作不经过CountedList的__setitem__所以不计入赋值次数。实际内存写入比统计值多但统计值反映的是主数组的写入压力。3.5 快速排序赋值次数为什么波动最大快速排序的赋值发生在分区交换。每次交换 3 次赋值。分区次数取决于基准选择。随机数据下快排的赋值次数约 1.4n*log2(n)比归并排序略高。但最坏情况已经有序且选第一个元素为基准会退化到 n^2赋值次数爆炸。def quick_sort(arr, low0, highNone): if high is None: high len(arr) - 1 if low high: pivot_idx partition(arr, low, high) quick_sort(arr, low, pivot_idx - 1) quick_sort(arr, pivot_idx 1, high) return arr def partition(arr, low, high): pivot arr[high] # 选最后一个元素为基准 i low - 1 for j in range(low, high): arr.compare_count 1 if arr[j] pivot: i 1 # 交换3 次赋值 temp arr[i] arr[i] arr[j] arr[j] temp # 基准归位3 次赋值 temp arr[i 1] arr[i 1] arr[high] arr[high] temp return i 1选最后一个元素为基准在逆序数据上表现最差。因为每次分区后基准都在最边上递归深度变成 n赋值次数接近 n^2/2。改进方法是随机选基准或三数取中。我一般用随机基准把pivot arr[high]改成随机选一个位置再交换到末尾。这样逆序数据下赋值次数也能保持在 n*log2(n) 量级。3.6 五种算法在三种数据分布下的赋值次数对比把上面的代码串起来跑一遍得到具体数字。数据规模 1000种子 42。算法随机数据赋值次数近乎有序赋值次数逆序赋值次数冒泡排序约 750,000约 30约 1,498,500插入排序约 250,000约 1,000约 500,000选择排序约 2,997约 0约 2,997归并排序约 9,966约 9,966约 9,966快速排序约 12,000约 8,000约 500,000这张表的信息量很大。冒泡排序在逆序时赋值次数是选择排序的 500 倍。插入排序在近乎有序时赋值次数只有随机数据的 0.4%。归并排序三种分布下完全一致。快速排序在逆序时如果不做基准优化赋值次数会退化到和插入排序一个量级。注意具体数字会因随机种子和实现细节略有差异但数量级关系稳定。跑实验时不要纠结最后几位数字看趋势。4. 避坑指南赋值次数统计中的五个常见翻车点4.1 现象赋值次数统计为 0排序结果却是对的原因排序函数内部用了sorted()或list.sort()这些内置方法操作的是 C 层数组不经过 Python 的__setitem__。或者排序函数把输入列表复制了一份操作的是副本原CountedList没被修改。解决确保排序函数直接操作传入的CountedList实例不要用任何内置排序。检查函数签名确认没有arr list(arr)这样的复制操作。如果必须复制复制后要重新包装成CountedList。4.2 现象归并排序的赋值次数比理论值高很多原因归并排序的递归切片arr[:mid]返回的是普通列表后续对切片的操作不计数。但合并时写回arr[k]会计数。如果切片后没有重新包装合并阶段的读取来自普通列表写入到CountedList计数只统计了写入部分。这其实是正确的但有人会把切片的创建也算作赋值导致数字偏高。解决明确统计口径。只统计主数组的写入。切片创建是额外空间开销单独用内存分析工具测不要混入赋值次数。4.3 现象快速排序在逆序数据上递归爆栈原因选第一个或最后一个元素为基准逆序数据下每次分区只减少一个元素递归深度达到 1000。Python 默认递归深度限制是 1000刚好卡在边界。解决改用随机基准或三数取中。随机基准的代码改动很小在partition开头加两行随机选一个索引和high交换。这样递归深度期望是 log2(n)不会爆栈。import random def partition(arr, low, high): # 随机选基准并交换到末尾 rand_idx random.randint(low, high) arr[rand_idx], arr[high] arr[high], arr[rand_idx] pivot arr[high] # ... 后续不变4.4 现象比较次数和赋值次数对不上预期原因compare_count是在排序函数里手动加的容易漏加或重复加。比如冒泡排序的内层循环如果if条件里写了比较但while条件里也有比较就会漏统计。解决把比较操作统一封装成函数比如def less(a, b): arr.compare_count 1; return a b。所有比较都走这个函数不会漏。代价是函数调用开销但 1000 个数的规模下可以忽略。4.5 现象不同机器上跑出的赋值次数不一样原因如果代码里用了set或dict来辅助排序这些结构的内部实现可能因 Python 版本不同而有差异。或者用了多线程赋值顺序不确定。解决对比实验必须单线程、纯列表操作。不要用任何哈希结构辅助。固定 Python 版本在实验报告里注明版本号。我一般用 Python 3.8行为稳定。5. 进阶技巧用赋值次数指导实际选型与可视化验证赋值次数跑出来之后怎么用我一般会画一张赋值次数随数据规模变化的曲线图。横轴是 n从 100 到 5000纵轴是赋值次数。冒泡和插入是抛物线归并和快排是对数线性选择排序是水平线。这张图能直观看出算法的时间复杂度差异。import matplotlib.pyplot as plt sizes [100, 500, 1000, 2000, 5000] algorithms { Bubble: bubble_sort, Insertion: insertion_sort, Selection: selection_sort, Merge: merge_sort, Quick: quick_sort, } results {name: [] for name in algorithms} for n in sizes: data generate_data(n, seed42, moderandom) for name, func in algorithms.items(): counted CountedList(data) func(counted) results[name].append(counted.assign_count) for name, counts in results.items(): plt.plot(sizes, counts, labelname, markero) plt.xlabel(Data Size (n)) plt.ylabel(Assignment Count) plt.legend() plt.title(Assignment Count vs Data Size) plt.savefig(assignment_comparison.png, dpi150) plt.show()这段代码会生成一张对比图。从图上能清楚看到选择排序的线几乎水平说明赋值次数和 n 无关只和交换次数有关归并和快排的线斜率稳定说明是 O(n log n)冒泡和插入的线越来越陡说明是 O(n^2)。这张图放在技术方案里比任何文字描述都有说服力。实际选型时如果业务数据基本有序且赋值昂贵比如写 Flash选插入排序。如果数据随机且要求性能稳定选归并排序。如果内存紧张且比较廉价选选择排序。如果追求平均性能且能接受最坏情况波动选快速排序加随机基准。赋值次数这个指标配合数据分布特征能帮你做出比“快排最快”这种笼统说法精确得多的决策。我自己的习惯是任何排序相关的选型先跑一遍赋值次数对比再看耗时。赋值次数对不上预期的耗时数据也不可信。这个习惯帮我避开了好几次“看起来快但实际写入量爆炸”的坑。希望帮到你。本文还有配套的精品资源点击获取