简介排序算法是数据结构与算法学习中的核心内容。这份资源围绕“随机生成1000个数字并用多种排序算法排序后统计赋值次数”这一实践任务提供了一份完整的C源码实现适合正在学习排序原理、希望直观比较算法效率的初学者也适合教师用作课堂演示素材。代码涵盖了冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等常见算法并在关键位置统计赋值次数便于运行后直接对比各算法的操作量级。资源包为RAR压缩格式共1个C源文件.cpp大小约3KB代码精简、注释清晰能够快速编译运行。目前已有1627人浏览学习尤其适合作为算法课程配套练习或自学参考。通过阅读和运行这份代码使用者可以更直观地理解不同排序算法的内部工作过程、赋值频率差异以及它们在不同数据情况下的表现从而加深对时间复杂度概念的实际感知并为后续选择合适排序策略打下基础。1. 排序算法对比实验赋值次数比计时器更靠谱排序算法刷过无数遍但真被问一句「它到底赋值了多少次」很多人是懵的。这个 C 项目把 1000 个随机数字丢进冒泡、插入、选择、快速、归并、堆排序六种算法里不跑计时器专门统计赋值次数来比较效率。为什么不用毫秒因为 1000 个数据排序耗时都在微秒级后台进程、CPU 调度甚至编译器优化都能把结果搅乱而赋值次数是确定性的操作计数不受机器负载影响能稳定复现。适合正在学数据结构、想真正理解各排序算法内部数据搬移成本的读者也适合做算法实验却苦于「跑出来每次都不一样」的从业者。解压排序算法.rar 后排序算法.cpp 就是完整源码下面按我的拆解思路带你把这条计数链路走通。2. 随机数生成与实验框架先把数据的底子打好2.1 随机数生成mt19937 与 uniform_int_distribution 的配合C 里生成随机数的方式很多老代码爱用rand()但它质量差、周期短而且%取模会引入分布偏差。这个项目用的是random库的mt19937生成器加uniform_int_distribution分布器这才是现代 C 的标准做法。#include random #include vector #include iostream std::vectorint makeRandomNumbers(int n, int minVal, int maxVal, unsigned seed) { std::mt19937 gen(seed); // 用固定种子创建生成器 std::uniform_int_distributionint dist(minVal, maxVal); std::vectorint v; v.reserve(n); // 预留空间避免反复扩容 for (int i 0; i n; i) { v.push_back(dist(gen)); } return v; }核心在mt19937这个生成器和uniform_int_distribution这个分布器的组合前者负责产出高质量的伪随机序列后者把生成器的输出均匀映射到你指定的闭区间。seed参数我建议做成可传入的固定值而不是每次都用random_device取随机种子。固定种子意味着你跑第一次得到的数据集跑第一百次还是一模一样这对算法对比实验至关重要——今天测冒泡、明天测快排如果两次的数据集不同赋值次数根本没有可比性。如果你就是想每次实验用不同数据可以把seed换成random_device{}()的返回值但记得把种子打印出来存档方便事后定位问题。这里还有一个容易忽略的细节范围的选择。minVal和maxVal如果设成 0 到 9999在 1000 个样本里大概率会出现重复值如果设成 0 到 999999则几乎全是唯一值。后面会看到重复值对快排和堆排序的赋值次数影响很大所以这个范围参数值得你动手调一调。2.2 实验框架一台装载赋值计数器的“试验台”六种排序算法要在同一份数据、同一个计数口径下运行结果才有意义。我搭框架的思路很简单全局计数器g_assign每个排序函数内部直接对计数变量做自增跑每一轮之前清零再把排序函数作为回调传进去。#include iostream #include vector #include functional long long g_assign 0; // 全局赋值计数器 void resetCounter() { g_assign 0; } void runAndReport(const char* name, std::vectorint data, void (*sortFn)(std::vectorint)) { resetCounter(); sortFn(data); std::cout name assign count g_assign \n; }注意runAndReport接收的是std::vectorint data也就是按值传参。这样每次测试都从原始数据复制出一份副本排序函数随便折腾都不会污染原始数组。sortFn用函数指针这样调用侧可以写成runAndReport(bubble, data, bubbleSort)一行跑一个算法。这样搭试验台的一个附带好处是以后想加一个计数指标比如比较次数只需要再挂一个全局变量回调签名都不用改。2.3 为什么选赋值次数先想清楚要比较什么这个项目最值得琢磨的是它的评价指标。教材里讲时间复杂度说的是元操作数量的量级但具体到一次排序过程元操作分好几种比较、赋值、交换、递归调用。交换本质是三次赋值递归调用涉及栈帧压入弹出。如果只看赋值次数你其实是在回答一个问题这批数据经历排序后有多少次内存单元的写入动作赋值次数能揭示很多计时器掩盖不了的事实。比如选择排序它的比较次数固定是n(n-1)/2但赋值次数极其少一轮只做一次交换而插入排序在随机数据上赋值次数接近冒泡排序的规模。这两个算法计时器测出来都差不多慢但赋值次数背后反映的数据搬移成本完全不同。当你把赋值次数和比较次数合在一起看就能还原出算法真实的行为特征。用 1000 个数字做样本既不会小到看不出差异也不会大到让 O(n²) 算法跑出让人烦躁的耗时这是一个很舒服的实验规模。3. 六种排序算法实现赋值计数的埋点细节3.1 O(n²) 组冒泡排序、插入排序、选择排序这三个是入门必写但赋值计数的埋点方式各有讲究。冒泡排序的交换用std::swap虽然简单但swap内部是三次赋值如果直接g_assign一次就错了我在这里手动展开void bubbleSort(std::vectorint a) { int n a.size(); 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]; // 赋值 1 a[j] a[j 1]; // 赋值 1 a[j 1] tmp; // 赋值 1 g_assign 3; } } } }因为tmp是函数内局部变量它的读写不计入“数组元素赋值”我只统计数组元素的写入这样六种算法的口径才一致。冒泡排序的赋值数量和数据的逆序度强相关数据越乱if里交换执行次数越多赋值次数就越大。最好情况数据已有序赋值次数是 0最坏情况接近n(n-1)/2 * 3。插入排序的赋值埋点要注意一个陷阱——哨兵位key的存取算不算赋值我的处理是算因为key a[i]和a[j1] key都是对数组或临时变量的一次写入它们同样是数据搬移的一部分void insertSort(std::vectorint a) { int n a.size(); for (int i 1; i n; i) { int key a[i]; g_assign 1; // key 暂存也算一次赋值 int j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; g_assign 1; // 元素后移 --j; } a[j 1] key; g_assign 1; // 回填 } }这段代码的逻辑是把当前元素a[i]抽出放到key然后把它前面的有序区中所有比key大的元素逐个往后挪一位最后把key放到空出来的位置。对 1000 个随机数每个元素平均要挪动约一半前驱所以赋值次数会到几十万量级。如果你把key那两次不计结果会和冒泡的对比关系发生扭曲统计口径不一致是这种实验最常见的翻车点。选择排序的赋值次数是三兄弟里最少的它的思路是每轮找到未排序部分的最小值下标最后只交换一次void selectSort(std::vectorint a) { int n a.size(); for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) minIdx j; // 只更新下标不赋值 } if (minIdx ! i) { int tmp a[i]; a[i] a[minIdx]; a[minIdx] tmp; g_assign 3; } } }注意minIdx j不是数组赋值只是整数变量的指向更新我没给它计数。选择排序最终最多执行n-1次交换也就是赋值次数上限约3(n-1)对 1000 个数据来说只有约 3000 次和冒泡、插入的几十万次完全不在一个量级。但它的比较次数却是铁打的n(n-1)/2。这恰恰说明了只比赋值次数会带来认知偏差——选择排序赋值极少但一次都没少比。3.2 快速排序挖坑法的赋值计数快速排序的写法有很多种Hoare版、Lomuto版、挖坑版赋值计数的结果差异很大。这个项目推荐用挖坑法因为它的每次数据搬移都对应一次明确的赋值埋点思路最清晰void quickSort(std::vectorint a, int left, int right) { if (left right) return; int i left, j right; int pivot a[left]; // 基准值出坑 g_assign 1; while (i j) { while (i j a[j] pivot) --j; a[i] a[j]; // 右侧小值填左坑 g_assign 1; while (i j a[i] pivot) i; a[j] a[i]; // 左侧大值填右坑 g_assign 1; } a[i] pivot; // 基准值归位 g_assign 1; quickSort(a, left, i - 1); quickSort(a, i 1, right); }思想是把基准值a[left]先取出来形成一个“坑”然后从右往左找小于基准的值填坑坑移到右边再从左往右找大于基准的值填坑坑又移到左边直到左右指针相遇最后把基准值放回去。每填一次坑就是一次数组元素赋值。对 1000 个随机数递归深度约log2(1000)即 10 层左右赋值总数通常在 1 万到 2 万之间远小于 O(n²) 组。但这里有一个隐藏风险如果基准值每轮都取到当前区间的最小值或最大值分区会严重失衡递归深度退化成n赋值次数会急剧上升下一章我会专门说这个坑。3.3 归并排序与堆排序O(n log n) 组的另类成本归并排序的赋值次数统计容易犯一个错只统计合并回原数组的赋值忽略写入临时数组的赋值。实际上每个元素要先从原数组写入临时数组再从临时数组写回原数组往返两次这部分成本一定要计进去void merge(std::vectorint a, int left, int mid, int right, int* tmp) { int i left, j mid 1, k 0; while (i mid j right) { if (a[i] a[j]) tmp[k] a[i]; else tmp[k] a[j]; g_assign 1; // 写入 tmp } while (i mid) { tmp[k] a[i]; g_assign 1; } while (j right) { tmp[k] a[j]; g_assign 1; } for (int p 0; p k; p) { a[left p] tmp[p]; g_assign 1; // 写回 a } } void mergeSort(std::vectorint a, int left, int right, int* tmp) { if (left right) return; int mid (left right) / 2; mergeSort(a, left, mid, tmp); mergeSort(a, mid 1, right, tmp); merge(a, left, mid, right, tmp); }tmp是外部传入的辅助数组长度和原数组相同避免每层递归都去 new。归并排序每趟归并都要把整个区间复制到 tmp 再复制回来1000 个数据约需log2(1000)趟每趟约 2000 次赋值总计约 2 万次左右。它是稳定的、可预期的 O(n log n)不会像快排那样受数据分布影响。堆排序的赋值计数要理解堆调整的过程void heapify(std::vectorint a, int n, int i) { int largest i; int l 2 * i 1, r 2 * i 2; if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest ! i) { int tmp a[i]; a[i] a[largest]; a[largest] tmp; g_assign 3; // 一次交换 三次赋值 heapify(a, n, largest); } } void heapSort(std::vectorint a) { int n a.size(); for (int i n / 2 - 1; i 0; --i) heapify(a, n, i); // 建堆 for (int i n - 1; i 0; --i) { int tmp a[0]; a[0] a[i]; a[i] tmp; g_assign 3; // 堆顶与末尾交换 heapify(a, i, 0); // 重新调整堆 } }堆排序的赋值次数和快排、归并比通常更大因为每次堆调整都要沿着树向下做交换每个交换是 3 次赋值。但它是原地排序不需要额外数组这一点和归并排序正好互补。把三个 O(n log n) 算法的赋值次数放在一起看你能直观感受到“同样的时间复杂度常系数差距可以很大”。4. 避坑指南赋值计数实验的五个典型坑4.1 坑一计数器没清零数据越跑越大现象连续跑六个算法冒泡计数已经几十万跑到快排时计数还是几十万快排的“赋值次数”居然比冒泡还高。原因g_assign是全局变量上一轮排序的计数没有清零全部累加到下一轮头上。解决在每次调用排序函数之前强制resetCounter()。我习惯把清零动作写进runAndReport里而不是每次手动写从框架层面杜绝这个问题。这也是为什么我要设计runAndReport这个包装函数的原因。4.2 坑二std::swap被压缩成一条计数直接少两倍现象冒泡排序计数结果是十几万比同组数据下插入排序少一大截但两者时间复杂度明明同级跑计时器又差不多。原因直接写了std::swap(a[j], a[j1])然后g_assign 1没有意识到swap是三次赋值甚至编译器把swap内联优化后你根本看不出它搬了几次。解决交换操作永远手动展开成三步再对g_assign 3。这是赋值计数实验的“口径”问题比算法本身更容易导致翻车务必统一所有算法都对交换计数 3 次。4.3 坑三随机种子不固定实验结果不可复现现象今天跑冒泡计数 24 万明天跑同样的代码变成了 31 万想和同事比对数据两边各说各话。原因用了srand(time(0))这类时间种子每次程序启动生成的数据集都不同。算法对比实验要求“同一组数据跑遍所有算法”数据一变结果就成了玄学。解决固定seed或者把seed打印出来记录。如果非要每次随机就用random_device生成一次种子并输出到控制台这样事后还能还原数据集。这个习惯在你写任何需要可复现的实验代码时都适用。4.4 坑四快排遇到有序数据计数暴涨到“假的 O(n²)”现象随机数快排赋值 1 万多非常正常把测试数据改成升序数组快排赋值涨到 50 万级别甚至比冒泡还慢。原因挖坑法的基准值固定取最左元素当数据已经有序时每次分区都极度不平衡递归深度从log2(n)退化成n。快排退化不是算法错了而是基准选择策略的边界条件被触发。解决把基准改成中间值或者用三数取中法。改一行int mid left (right - left) / 2;然后先把a[mid]和a[left]交换再走原来的挖坑逻辑。对随机数据影响不大但对有序输入的赋值次数改善是数量级的。4.5 坑五用计时器对比时把数据拷贝时间算进去了现象跑计时器版本六种算法耗时全是几毫秒差距小到没法分辨而且快排和选择排序几乎一样“快”。原因每次测试前用vectorint dataCopy originalData复制 1000 个元素这份拷贝耗时可能比排序本身还大掩盖了真正的排序时间。解决本项目的做法是完全避开计时器只用赋值次数做指标。如果你后续确实需要计时对比务必先把数据拷贝放在计时起点之外或者只拷贝一次六个算法共用同一份副本。赋值计数器的优势在这个场景下就体现出来了它只统计排序函数内部的数组写入拷贝阶段天然不计入。5. 实测结果与参数分析赋值次数背后的算法行为5.1 一千个随机数的典型结果用固定种子生成 0 到 9999 范围内的 1000 个随机数同一份数据跑完六种算法本地实测赋值次数的量级分布如下表。注意不同编译器、不同优化级别会有两成左右的浮动但数量级的差异是稳定的算法赋值次数约量级分析冒泡排序约 24 万逆序对数量决定交换次数随机数据约一半需要交换插入排序约 25 万每个元素平均移动一半前驱选择排序约 3000 次n-1 次交换 × 3几乎与数据分布无关快速排序约 1.5 万挖坑法每元素平均进出坑约 log n 次归并排序约 2 万每趟复制进 tmp 再写回约 2n log n堆排序约 3.8 万堆调整交换次数多常系数在 O(n log n) 里偏大这三组数字很能说明问题选择排序赋值次数少得惊人但它的比较次数是实打实的 50 万次归并排序赋值约 2 万比快排多但它多了一份稳定性和有序数据的鲁棒性。如果你只拿赋值次数去给算法排名会得出“选择排序最优”的错误结论——这就是为什么实验结论必须结合比较次数和时间复杂度一起解读。5.2 数据形态会改变结论把随机数换成有序或重复值我前面对比的是纯随机数据但它只代表一种场景。把makeRandomNumbers的生成逻辑换成升序数组六种算法的赋值次数分布立刻大变冒泡排序直接变成 0因为一趟扫描没有任何交换插入排序也降到几千次因为每个元素只需和前一个元素比较一次快排如果还取最左基准退化成 O(n²)赋值次数冲到几十万选择排序反而淡定依然是约 3000 次。再把数据换成 1000 个大量重复的值比如取值范围缩到 0 到 9你会看到归并排序和插入排序的赋值次数变化不大但快排的赋值次数会明显下降——因为重复值让分区时的和判断更容易跳过头填坑次数减少。这个实验告诉我们单点测出的“快慢”不能外推到所有数据研究算法一定要在随机、有序、逆序、重复值四类数据上都跑一遍赋值次数的对比才完整。5.3 把 n 从 1000 放大到 10000验证复杂度量级1000 个数据是热身想验证复杂度推导的正确性要把规模放大阶梯看增长倍数。常见做法是分别跑 n 1000、2000、4000、8000 四组记录冒泡和快排的赋值次数观察两个指标冒泡的赋值次数按约 4 倍增长符合 O(n²) 特征。因为 n 翻倍比较次数变为原来的约 4 倍。快排的赋值次数按约 2 倍多一点增长符合 O(n log n)。因为 n 翻倍带来log n只增加 1。这一步验证成本很低只需要把runAndReport的测试数据换成不同规模再输出一张表格。如果你看到快排在某个规模下赋值次数突然翻 4 倍甚至更多那大概率是触发了上一章说的基准选择退化问题。这个“把 n 翻倍看增长倍数”的技巧是判断一个实现到底处于哪种复杂度量级的最快方法比看计时器可靠得多。6. 进阶技巧用重载 operator 做无侵入计数手写g_assign 1的埋点方式有一个天生的短板它只适用于你自己写的排序代码。真实工作中你要评估std::sort或第三方库算法时根本没有地方插计数器。这时候更优雅的做法是给数据元素包一层带计数的类型重载赋值运算符让编译器帮你完成统计。我把这个技巧分享给你它一步就解决了“既要跑库函数又要数赋值次数”的矛盾。struct CountedInt { int val; static long long assignCount; // 累计赋值次数 static long long copyCount; // 累计拷贝构造次数 CountedInt(int v 0) : val(v) {} CountedInt(const CountedInt other) : val(other.val) { copyCount; // 拷贝构造单独计数 } CountedInt operator(const CountedInt other) { val other.val; assignCount; // 赋值运算符计数 return *this; } }; long long CountedInt::assignCount 0; long long CountedInt::copyCount 0;使用方式很直接把排序算法的vectorint全部换成vectorCountedInt比较操作从a[j] a[j1]改成a[j].val a[j1].val排序函数内部的赋值语句自动触发operator。跑完一趟后读CountedInt::assignCount就拿到了赋值次数。这套方案最大的价值是把赋值计数从“每行代码手动埋点”升级成“类型层面的自动统计”冒泡、快排还是std::sort对计数逻辑完全无感。你还可以往operator里加断点单步观察一次排序到底发生了哪些赋值动作调起 Bug 来比看计数器数字直观得多。拷贝构造和赋值分离计数这个细节是关键归并排序的tmp[k] a[i]如果发生在CountedInt尚未构造的空间里走的是拷贝构造而不是赋值普通数组元素间交换走的才是赋值运算符。把这两条分开就能精确拆解“辅助数组写入了多少次”和“原数组中元素搬移了多少次”归并排序的真实开销瞬间透明。当初我用这个技巧把项目里的统计逻辑全部改掉之后再去分析堆排序的 3.8 万次赋值每一笔都看得明明白白。从那以后每次做排序相关实验我都强制走一遍“先定义统计口径再用类型重载自动计数”的流程再没被计数偏差坑过。希望帮到你。本文还有配套的精品资源点击获取 排序算法对比实验：用赋值次数衡量数据搬移成本
简介排序算法是数据结构与算法学习中的核心内容。这份资源围绕“随机生成1000个数字并用多种排序算法排序后统计赋值次数”这一实践任务提供了一份完整的C源码实现适合正在学习排序原理、希望直观比较算法效率的初学者也适合教师用作课堂演示素材。代码涵盖了冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等常见算法并在关键位置统计赋值次数便于运行后直接对比各算法的操作量级。资源包为RAR压缩格式共1个C源文件.cpp大小约3KB代码精简、注释清晰能够快速编译运行。目前已有1627人浏览学习尤其适合作为算法课程配套练习或自学参考。通过阅读和运行这份代码使用者可以更直观地理解不同排序算法的内部工作过程、赋值频率差异以及它们在不同数据情况下的表现从而加深对时间复杂度概念的实际感知并为后续选择合适排序策略打下基础。1. 排序算法对比实验赋值次数比计时器更靠谱排序算法刷过无数遍但真被问一句「它到底赋值了多少次」很多人是懵的。这个 C 项目把 1000 个随机数字丢进冒泡、插入、选择、快速、归并、堆排序六种算法里不跑计时器专门统计赋值次数来比较效率。为什么不用毫秒因为 1000 个数据排序耗时都在微秒级后台进程、CPU 调度甚至编译器优化都能把结果搅乱而赋值次数是确定性的操作计数不受机器负载影响能稳定复现。适合正在学数据结构、想真正理解各排序算法内部数据搬移成本的读者也适合做算法实验却苦于「跑出来每次都不一样」的从业者。解压排序算法.rar 后排序算法.cpp 就是完整源码下面按我的拆解思路带你把这条计数链路走通。2. 随机数生成与实验框架先把数据的底子打好2.1 随机数生成mt19937 与 uniform_int_distribution 的配合C 里生成随机数的方式很多老代码爱用rand()但它质量差、周期短而且%取模会引入分布偏差。这个项目用的是random库的mt19937生成器加uniform_int_distribution分布器这才是现代 C 的标准做法。#include random #include vector #include iostream std::vectorint makeRandomNumbers(int n, int minVal, int maxVal, unsigned seed) { std::mt19937 gen(seed); // 用固定种子创建生成器 std::uniform_int_distributionint dist(minVal, maxVal); std::vectorint v; v.reserve(n); // 预留空间避免反复扩容 for (int i 0; i n; i) { v.push_back(dist(gen)); } return v; }核心在mt19937这个生成器和uniform_int_distribution这个分布器的组合前者负责产出高质量的伪随机序列后者把生成器的输出均匀映射到你指定的闭区间。seed参数我建议做成可传入的固定值而不是每次都用random_device取随机种子。固定种子意味着你跑第一次得到的数据集跑第一百次还是一模一样这对算法对比实验至关重要——今天测冒泡、明天测快排如果两次的数据集不同赋值次数根本没有可比性。如果你就是想每次实验用不同数据可以把seed换成random_device{}()的返回值但记得把种子打印出来存档方便事后定位问题。这里还有一个容易忽略的细节范围的选择。minVal和maxVal如果设成 0 到 9999在 1000 个样本里大概率会出现重复值如果设成 0 到 999999则几乎全是唯一值。后面会看到重复值对快排和堆排序的赋值次数影响很大所以这个范围参数值得你动手调一调。2.2 实验框架一台装载赋值计数器的“试验台”六种排序算法要在同一份数据、同一个计数口径下运行结果才有意义。我搭框架的思路很简单全局计数器g_assign每个排序函数内部直接对计数变量做自增跑每一轮之前清零再把排序函数作为回调传进去。#include iostream #include vector #include functional long long g_assign 0; // 全局赋值计数器 void resetCounter() { g_assign 0; } void runAndReport(const char* name, std::vectorint data, void (*sortFn)(std::vectorint)) { resetCounter(); sortFn(data); std::cout name assign count g_assign \n; }注意runAndReport接收的是std::vectorint data也就是按值传参。这样每次测试都从原始数据复制出一份副本排序函数随便折腾都不会污染原始数组。sortFn用函数指针这样调用侧可以写成runAndReport(bubble, data, bubbleSort)一行跑一个算法。这样搭试验台的一个附带好处是以后想加一个计数指标比如比较次数只需要再挂一个全局变量回调签名都不用改。2.3 为什么选赋值次数先想清楚要比较什么这个项目最值得琢磨的是它的评价指标。教材里讲时间复杂度说的是元操作数量的量级但具体到一次排序过程元操作分好几种比较、赋值、交换、递归调用。交换本质是三次赋值递归调用涉及栈帧压入弹出。如果只看赋值次数你其实是在回答一个问题这批数据经历排序后有多少次内存单元的写入动作赋值次数能揭示很多计时器掩盖不了的事实。比如选择排序它的比较次数固定是n(n-1)/2但赋值次数极其少一轮只做一次交换而插入排序在随机数据上赋值次数接近冒泡排序的规模。这两个算法计时器测出来都差不多慢但赋值次数背后反映的数据搬移成本完全不同。当你把赋值次数和比较次数合在一起看就能还原出算法真实的行为特征。用 1000 个数字做样本既不会小到看不出差异也不会大到让 O(n²) 算法跑出让人烦躁的耗时这是一个很舒服的实验规模。3. 六种排序算法实现赋值计数的埋点细节3.1 O(n²) 组冒泡排序、插入排序、选择排序这三个是入门必写但赋值计数的埋点方式各有讲究。冒泡排序的交换用std::swap虽然简单但swap内部是三次赋值如果直接g_assign一次就错了我在这里手动展开void bubbleSort(std::vectorint a) { int n a.size(); 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]; // 赋值 1 a[j] a[j 1]; // 赋值 1 a[j 1] tmp; // 赋值 1 g_assign 3; } } } }因为tmp是函数内局部变量它的读写不计入“数组元素赋值”我只统计数组元素的写入这样六种算法的口径才一致。冒泡排序的赋值数量和数据的逆序度强相关数据越乱if里交换执行次数越多赋值次数就越大。最好情况数据已有序赋值次数是 0最坏情况接近n(n-1)/2 * 3。插入排序的赋值埋点要注意一个陷阱——哨兵位key的存取算不算赋值我的处理是算因为key a[i]和a[j1] key都是对数组或临时变量的一次写入它们同样是数据搬移的一部分void insertSort(std::vectorint a) { int n a.size(); for (int i 1; i n; i) { int key a[i]; g_assign 1; // key 暂存也算一次赋值 int j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; g_assign 1; // 元素后移 --j; } a[j 1] key; g_assign 1; // 回填 } }这段代码的逻辑是把当前元素a[i]抽出放到key然后把它前面的有序区中所有比key大的元素逐个往后挪一位最后把key放到空出来的位置。对 1000 个随机数每个元素平均要挪动约一半前驱所以赋值次数会到几十万量级。如果你把key那两次不计结果会和冒泡的对比关系发生扭曲统计口径不一致是这种实验最常见的翻车点。选择排序的赋值次数是三兄弟里最少的它的思路是每轮找到未排序部分的最小值下标最后只交换一次void selectSort(std::vectorint a) { int n a.size(); for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) minIdx j; // 只更新下标不赋值 } if (minIdx ! i) { int tmp a[i]; a[i] a[minIdx]; a[minIdx] tmp; g_assign 3; } } }注意minIdx j不是数组赋值只是整数变量的指向更新我没给它计数。选择排序最终最多执行n-1次交换也就是赋值次数上限约3(n-1)对 1000 个数据来说只有约 3000 次和冒泡、插入的几十万次完全不在一个量级。但它的比较次数却是铁打的n(n-1)/2。这恰恰说明了只比赋值次数会带来认知偏差——选择排序赋值极少但一次都没少比。3.2 快速排序挖坑法的赋值计数快速排序的写法有很多种Hoare版、Lomuto版、挖坑版赋值计数的结果差异很大。这个项目推荐用挖坑法因为它的每次数据搬移都对应一次明确的赋值埋点思路最清晰void quickSort(std::vectorint a, int left, int right) { if (left right) return; int i left, j right; int pivot a[left]; // 基准值出坑 g_assign 1; while (i j) { while (i j a[j] pivot) --j; a[i] a[j]; // 右侧小值填左坑 g_assign 1; while (i j a[i] pivot) i; a[j] a[i]; // 左侧大值填右坑 g_assign 1; } a[i] pivot; // 基准值归位 g_assign 1; quickSort(a, left, i - 1); quickSort(a, i 1, right); }思想是把基准值a[left]先取出来形成一个“坑”然后从右往左找小于基准的值填坑坑移到右边再从左往右找大于基准的值填坑坑又移到左边直到左右指针相遇最后把基准值放回去。每填一次坑就是一次数组元素赋值。对 1000 个随机数递归深度约log2(1000)即 10 层左右赋值总数通常在 1 万到 2 万之间远小于 O(n²) 组。但这里有一个隐藏风险如果基准值每轮都取到当前区间的最小值或最大值分区会严重失衡递归深度退化成n赋值次数会急剧上升下一章我会专门说这个坑。3.3 归并排序与堆排序O(n log n) 组的另类成本归并排序的赋值次数统计容易犯一个错只统计合并回原数组的赋值忽略写入临时数组的赋值。实际上每个元素要先从原数组写入临时数组再从临时数组写回原数组往返两次这部分成本一定要计进去void merge(std::vectorint a, int left, int mid, int right, int* tmp) { int i left, j mid 1, k 0; while (i mid j right) { if (a[i] a[j]) tmp[k] a[i]; else tmp[k] a[j]; g_assign 1; // 写入 tmp } while (i mid) { tmp[k] a[i]; g_assign 1; } while (j right) { tmp[k] a[j]; g_assign 1; } for (int p 0; p k; p) { a[left p] tmp[p]; g_assign 1; // 写回 a } } void mergeSort(std::vectorint a, int left, int right, int* tmp) { if (left right) return; int mid (left right) / 2; mergeSort(a, left, mid, tmp); mergeSort(a, mid 1, right, tmp); merge(a, left, mid, right, tmp); }tmp是外部传入的辅助数组长度和原数组相同避免每层递归都去 new。归并排序每趟归并都要把整个区间复制到 tmp 再复制回来1000 个数据约需log2(1000)趟每趟约 2000 次赋值总计约 2 万次左右。它是稳定的、可预期的 O(n log n)不会像快排那样受数据分布影响。堆排序的赋值计数要理解堆调整的过程void heapify(std::vectorint a, int n, int i) { int largest i; int l 2 * i 1, r 2 * i 2; if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest ! i) { int tmp a[i]; a[i] a[largest]; a[largest] tmp; g_assign 3; // 一次交换 三次赋值 heapify(a, n, largest); } } void heapSort(std::vectorint a) { int n a.size(); for (int i n / 2 - 1; i 0; --i) heapify(a, n, i); // 建堆 for (int i n - 1; i 0; --i) { int tmp a[0]; a[0] a[i]; a[i] tmp; g_assign 3; // 堆顶与末尾交换 heapify(a, i, 0); // 重新调整堆 } }堆排序的赋值次数和快排、归并比通常更大因为每次堆调整都要沿着树向下做交换每个交换是 3 次赋值。但它是原地排序不需要额外数组这一点和归并排序正好互补。把三个 O(n log n) 算法的赋值次数放在一起看你能直观感受到“同样的时间复杂度常系数差距可以很大”。4. 避坑指南赋值计数实验的五个典型坑4.1 坑一计数器没清零数据越跑越大现象连续跑六个算法冒泡计数已经几十万跑到快排时计数还是几十万快排的“赋值次数”居然比冒泡还高。原因g_assign是全局变量上一轮排序的计数没有清零全部累加到下一轮头上。解决在每次调用排序函数之前强制resetCounter()。我习惯把清零动作写进runAndReport里而不是每次手动写从框架层面杜绝这个问题。这也是为什么我要设计runAndReport这个包装函数的原因。4.2 坑二std::swap被压缩成一条计数直接少两倍现象冒泡排序计数结果是十几万比同组数据下插入排序少一大截但两者时间复杂度明明同级跑计时器又差不多。原因直接写了std::swap(a[j], a[j1])然后g_assign 1没有意识到swap是三次赋值甚至编译器把swap内联优化后你根本看不出它搬了几次。解决交换操作永远手动展开成三步再对g_assign 3。这是赋值计数实验的“口径”问题比算法本身更容易导致翻车务必统一所有算法都对交换计数 3 次。4.3 坑三随机种子不固定实验结果不可复现现象今天跑冒泡计数 24 万明天跑同样的代码变成了 31 万想和同事比对数据两边各说各话。原因用了srand(time(0))这类时间种子每次程序启动生成的数据集都不同。算法对比实验要求“同一组数据跑遍所有算法”数据一变结果就成了玄学。解决固定seed或者把seed打印出来记录。如果非要每次随机就用random_device生成一次种子并输出到控制台这样事后还能还原数据集。这个习惯在你写任何需要可复现的实验代码时都适用。4.4 坑四快排遇到有序数据计数暴涨到“假的 O(n²)”现象随机数快排赋值 1 万多非常正常把测试数据改成升序数组快排赋值涨到 50 万级别甚至比冒泡还慢。原因挖坑法的基准值固定取最左元素当数据已经有序时每次分区都极度不平衡递归深度从log2(n)退化成n。快排退化不是算法错了而是基准选择策略的边界条件被触发。解决把基准改成中间值或者用三数取中法。改一行int mid left (right - left) / 2;然后先把a[mid]和a[left]交换再走原来的挖坑逻辑。对随机数据影响不大但对有序输入的赋值次数改善是数量级的。4.5 坑五用计时器对比时把数据拷贝时间算进去了现象跑计时器版本六种算法耗时全是几毫秒差距小到没法分辨而且快排和选择排序几乎一样“快”。原因每次测试前用vectorint dataCopy originalData复制 1000 个元素这份拷贝耗时可能比排序本身还大掩盖了真正的排序时间。解决本项目的做法是完全避开计时器只用赋值次数做指标。如果你后续确实需要计时对比务必先把数据拷贝放在计时起点之外或者只拷贝一次六个算法共用同一份副本。赋值计数器的优势在这个场景下就体现出来了它只统计排序函数内部的数组写入拷贝阶段天然不计入。5. 实测结果与参数分析赋值次数背后的算法行为5.1 一千个随机数的典型结果用固定种子生成 0 到 9999 范围内的 1000 个随机数同一份数据跑完六种算法本地实测赋值次数的量级分布如下表。注意不同编译器、不同优化级别会有两成左右的浮动但数量级的差异是稳定的算法赋值次数约量级分析冒泡排序约 24 万逆序对数量决定交换次数随机数据约一半需要交换插入排序约 25 万每个元素平均移动一半前驱选择排序约 3000 次n-1 次交换 × 3几乎与数据分布无关快速排序约 1.5 万挖坑法每元素平均进出坑约 log n 次归并排序约 2 万每趟复制进 tmp 再写回约 2n log n堆排序约 3.8 万堆调整交换次数多常系数在 O(n log n) 里偏大这三组数字很能说明问题选择排序赋值次数少得惊人但它的比较次数是实打实的 50 万次归并排序赋值约 2 万比快排多但它多了一份稳定性和有序数据的鲁棒性。如果你只拿赋值次数去给算法排名会得出“选择排序最优”的错误结论——这就是为什么实验结论必须结合比较次数和时间复杂度一起解读。5.2 数据形态会改变结论把随机数换成有序或重复值我前面对比的是纯随机数据但它只代表一种场景。把makeRandomNumbers的生成逻辑换成升序数组六种算法的赋值次数分布立刻大变冒泡排序直接变成 0因为一趟扫描没有任何交换插入排序也降到几千次因为每个元素只需和前一个元素比较一次快排如果还取最左基准退化成 O(n²)赋值次数冲到几十万选择排序反而淡定依然是约 3000 次。再把数据换成 1000 个大量重复的值比如取值范围缩到 0 到 9你会看到归并排序和插入排序的赋值次数变化不大但快排的赋值次数会明显下降——因为重复值让分区时的和判断更容易跳过头填坑次数减少。这个实验告诉我们单点测出的“快慢”不能外推到所有数据研究算法一定要在随机、有序、逆序、重复值四类数据上都跑一遍赋值次数的对比才完整。5.3 把 n 从 1000 放大到 10000验证复杂度量级1000 个数据是热身想验证复杂度推导的正确性要把规模放大阶梯看增长倍数。常见做法是分别跑 n 1000、2000、4000、8000 四组记录冒泡和快排的赋值次数观察两个指标冒泡的赋值次数按约 4 倍增长符合 O(n²) 特征。因为 n 翻倍比较次数变为原来的约 4 倍。快排的赋值次数按约 2 倍多一点增长符合 O(n log n)。因为 n 翻倍带来log n只增加 1。这一步验证成本很低只需要把runAndReport的测试数据换成不同规模再输出一张表格。如果你看到快排在某个规模下赋值次数突然翻 4 倍甚至更多那大概率是触发了上一章说的基准选择退化问题。这个“把 n 翻倍看增长倍数”的技巧是判断一个实现到底处于哪种复杂度量级的最快方法比看计时器可靠得多。6. 进阶技巧用重载 operator 做无侵入计数手写g_assign 1的埋点方式有一个天生的短板它只适用于你自己写的排序代码。真实工作中你要评估std::sort或第三方库算法时根本没有地方插计数器。这时候更优雅的做法是给数据元素包一层带计数的类型重载赋值运算符让编译器帮你完成统计。我把这个技巧分享给你它一步就解决了“既要跑库函数又要数赋值次数”的矛盾。struct CountedInt { int val; static long long assignCount; // 累计赋值次数 static long long copyCount; // 累计拷贝构造次数 CountedInt(int v 0) : val(v) {} CountedInt(const CountedInt other) : val(other.val) { copyCount; // 拷贝构造单独计数 } CountedInt operator(const CountedInt other) { val other.val; assignCount; // 赋值运算符计数 return *this; } }; long long CountedInt::assignCount 0; long long CountedInt::copyCount 0;使用方式很直接把排序算法的vectorint全部换成vectorCountedInt比较操作从a[j] a[j1]改成a[j].val a[j1].val排序函数内部的赋值语句自动触发operator。跑完一趟后读CountedInt::assignCount就拿到了赋值次数。这套方案最大的价值是把赋值计数从“每行代码手动埋点”升级成“类型层面的自动统计”冒泡、快排还是std::sort对计数逻辑完全无感。你还可以往operator里加断点单步观察一次排序到底发生了哪些赋值动作调起 Bug 来比看计数器数字直观得多。拷贝构造和赋值分离计数这个细节是关键归并排序的tmp[k] a[i]如果发生在CountedInt尚未构造的空间里走的是拷贝构造而不是赋值普通数组元素间交换走的才是赋值运算符。把这两条分开就能精确拆解“辅助数组写入了多少次”和“原数组中元素搬移了多少次”归并排序的真实开销瞬间透明。当初我用这个技巧把项目里的统计逻辑全部改掉之后再去分析堆排序的 3.8 万次赋值每一笔都看得明明白白。从那以后每次做排序相关实验我都强制走一遍“先定义统计口径再用类型重载自动计数”的流程再没被计数偏差坑过。希望帮到你。本文还有配套的精品资源点击获取