简介面向编程初学者与算法学习者这份资源围绕一千个随机整数的生成与排序展开完整演示冒泡、插入、选择、快速、归并、堆六种常见排序算法的实现并通过统计赋值次数横向比较各算法运行效率。随机数的生成采用现代C标准库中的随机数引擎可复现指定范围的数据集排序模块则针对每种算法保留赋值计数器便于观察最坏情况与平均情况下的操作次数差异。压缩包仅含一个C源文件整体大小3KB轻量可直接编译运行无需额外依赖适合作为算法课程实验、期末复习或面试准备时的参考样板。目前已有超过一千六百人学习下载若需快速理解排序算法底层逻辑及效率衡量方式可借助这份精简代码动手验证。1. 排序算法实操随机生成 1000 个数字统计六种排序的赋值次数排序算法可能是数据结构里最容易被“背完就忘”的一块八大排序的原理图谁都能画两笔可真给你 1000 个数让你说清楚冒泡比快排到底“费”在哪大多数人会卡住。这个项目把问题落到了一个很硬的指标上——赋值次数。它不是比较次数也不是理论时间复杂度而是算法真正写数组元素的次数这个数字能直观暴露不同排序策略的“体力活”差异。资源包里是一个完整的 C 源文件排序算法.cpp用 C11 的random库生成数据在六种排序内部埋计数器跑完直接输出每次赋值的统计。适合正在啃数据结构、准备面试手写排序或者想用数据验证“O(n²) 和 O(n log n) 差多少”的读者。2. 准备 1000 个测试数字为什么选 而不是古老的 rand()这个项目的第一步不是写排序而是先把测试数据准备“干净”。数据如果不随机、范围不对、种子没固定后面所有排序对比都是白跑。2.1 选择 库的三个理由很多教材和网上的老代码还在用rand()srand(time(NULL))这个组合在 C 里已经被标记为“能跑但不推荐”。理由很简单rand()的分布质量差而且不同编译器下实现不一样你换台机器跑可能连排序结果都复现不了。我一般会用 C11 之后的random库它把“随机数来源”和“分布”分开了std::random_device真随机数种子来源或者退化为伪随机种子std::mt19937梅森旋转算法生成质量高、周期长做算法测试绰绰有余std::uniform_int_distribution把生成器输出映射到[min, max]闭区间均匀分布不会像rand() % n那样有取模偏差。对这份资源来说数据范围建议设成[0, 999]或[1, 1000]这样排序结果肉眼可读而且 1000 个数的规模能保证赋值的数量级差拉开。2.2 生成 1000 个数的实现与参数解释资源里核心的数据生成函数是这个逻辑如果你要自己复现可以直接把这个函数摘出来#include random #include vector std::vectorint generateRandomNumbers(int n, int min, int max) { std::random_device rd; // 获取真随机种子 std::mt19937 gen(rd()); // 用种子初始化梅森旋转引擎 std::uniform_int_distribution dis(min, max); // 均匀分布闭区间 std::vectorint numbers; numbers.reserve(n); // 预分配内存避免多次扩容 for (int i 0; i n; i) { numbers.push_back(dis(gen)); // 每次调用 dis(gen) 得到一个随机整数 } return numbers; }这里有两个容易被忽略的参数细节。第一个是reserve(n)提前分配好n个元素的容量防止push_back触发多次vector扩容扩容本身也会产生赋值操作如果你统计的是“排序算法赋值次数”数据准备阶段的开销不能混进去。第二个是uniform_int_distribution的尖括号里不写类型就默认int如果你想生成更大的数比如面试题常考的[0, 100000]显式写成std::uniform_int_distributionint更清楚。2.3 固定种子让对比结果可复现这里有一个新手很容易掉进去的坑调试时每次运行数据都不一样你刚发现冒泡排序赋值 37 万次改个参数重跑一次变成 41 万次根本没法定位问题。我的习惯是调试阶段把种子固定成一个常量比如std::mt19937 gen(42)这样每次跑、每台机器跑生成的序列都完全一致。只有确认代码没问题了才换回random_device看真实场景的表现。这个项目的巧妙之处在于它是“比较算法差异”而不是“测试算法在某组数据上的优劣”所以固定种子反而能让对比更公平——所有算法面对的是同一份数据。还有一个细节很多文章教人“随机生成 1000 个数字”时会去重保证没有重复值。但在排序算法讨论里重复值恰恰是合理的因为真实数据里重复太常见了。排序算法对重复数据的表现比如稳定排序的优势也是评估指标的一部分所以直接允许重复生成不需要去重。3. 给六种排序算法埋“赋值计数器”核心实现与统一口径数据准备好了接下来是整个项目的核心在每种排序算法里统计赋值次数。这个环节最难的不是排序本身而是“什么叫赋值”这件事必须先定规矩。3.1 统一计数口径哪些操作算一次赋值赋值次数不能想加就加口径不统一不同算法之间根本没有可比性。我给这套代码定的规矩是只有写数组元素或写临时变量作为值传递的语句才算一次赋值。具体拆开是这样的循环变量i不算比较arr[i] arr[j]不算int tmp arr[j]算 1 次赋值arr[i] arr[j]算 1 次赋值swap(arr[i], arr[j])展开成tmp a; a b; b tmp;算 3 次赋值归并排序里temp[k] arr[i]算 1 次赋值快速排序里“基准值位置的最终写入”算 1 次赋值。为什么这样定因为赋值操作本质上是数据搬移它比比较操作更接近算法的“真实体力消耗”。把这个口径写成一个全局计数器在一个函数入口清零排序结束后把结果存进一个long long避免 int 溢出。3.2 冒泡排序与选择排序O(n²) 但赋值差距极大冒泡和选择的时间复杂度都是 O(n²)但赋值次数差了一个量级。先看代码long long bubbleSort(std::vectorint arr) { long long cnt 0; int n arr.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - i - 1; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; // 第 1 次赋值 arr[j] arr[j 1]; // 第 2 次赋值 arr[j 1] tmp; // 第 3 次赋值 cnt 3; swapped true; } } if (!swapped) break; // 提前终止已经有序 } return cnt; }冒泡排序的赋值次数跟数据的有序程度强相关。最坏情况完全逆序每轮都比较并交换赋值次数约等于比较次数的 3 倍。但swapped这个提前终止标志很关键——如果数据本身接近有序赋值次数会断崖式下降。选择排序就完全是另一个画风了它每轮只交换一次long long selectionSort(std::vectorint arr) { long long cnt 0; int n arr.size(); for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } if (minIdx ! i) { int tmp arr[i]; // 交换 3 次赋值 arr[i] arr[minIdx]; arr[minIdx] tmp; cnt 3; } } return cnt; }注意看选择排序里找到最小值的比较过程完全不产生赋值只有最终交换时才加 3 次。所以同样是 O(n²)选择排序的赋值次数大约是冒泡最坏情况的三分之一甚至更少。这就是项目统计赋值次数的第一个收获复杂度相同赋值差异巨大。插入排序是这组里最“特别”的它的赋值次数在最好和最坏情况之间剧烈变化long long insertionSort(std::vectorint arr) { long long cnt 0; int n arr.size(); for (int i 1; i n; i) { int key arr[i]; // 取出当前元素1 次赋值 cnt; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; // 后移元素1 次赋值 cnt; j--; } arr[j 1] key; // 放入正确位置1 次赋值 cnt; } return cnt; }这里要注意int key arr[i]算一次赋值很多新手会漏掉它。如果把 key 的取出和放回都算上插入排序的一次插入操作在逆序时要执行j次后移赋值次数大约是2 j次。在 1000 个随机数上它通常表现得比冒泡好但比选择差。3.3 快速排序、归并排序与堆排序分治与堆操作这三个是 O(n log n) 级别的选手但赋值次数的分布非常有意思。快排是“原地但递归”归并是“稳定但需要辅助数组”堆排是“原地但不稳定”。void quickSortHelper(std::vectorint arr, int low, int high, long long cnt) { if (low high) return; int pivot arr[high]; // 取最后一个元素作基准1 次赋值 cnt; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; std::swap(arr[i], arr[j]); // 内部 3 次赋值 cnt 3; } } std::swap(arr[i 1], arr[high]); // 基准归位3 次赋值 cnt 3; quickSortHelper(arr, low, i, cnt); quickSortHelper(arr, i 2, high, cnt); }快排的赋值次数和基准选择强相关。上面这个版本用的是“取最后一个元素”如果遇到几乎有序的数据会退化到接近 O(n²)赋值次数飙升。实际对比时我建议你多测两种基准策略三数取中和随机选基准赋值次数差异会让你对快排的“玄学”有更直观的感受。归并排序的实现要注意计数器的位置long long mergeSort(std::vectorint arr) { long long cnt 0; std::vectorint temp(arr.size()); // 辅助数组 // 递归合并 std::functionvoid(int, int) sortRange [](int left, int right) { if (left right) return; int mid left (right - left) / 2; sortRange(left, mid); sortRange(mid 1, right); // 合并左右有序区间 int i left, j mid 1, k left; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } cnt; // 每次写 temp 数组算 1 次 } while (i mid) { temp[k] arr[i]; cnt; } while (j right) { temp[k] arr[j]; cnt; } for (int p left; p right; p) { arr[p] temp[p]; // 写回原数组算 1 次 cnt; } }; sortRange(0, arr.size() - 1); return cnt; }归并排序的赋值次数最“诚实”不管数据是有序还是逆序它都要执行完整的合并和写回赋值次数波动极小。这是稳定性的代价也是它的可爱之处——性能可预测。堆排序的赋值次数藏在建堆和调整里实现时注意siftDown里每下沉一层就可能有赋值void siftDown(std::vectorint arr, int n, int i, long long cnt) { while (true) { int largest i; int l 2 * i 1; int r 2 * i 2; if (l n arr[l] arr[largest]) largest l; if (r n arr[r] arr[largest]) largest r; if (largest ! i) { std::swap(arr[i], arr[largest]); // 3 次赋值 cnt 3; i largest; } else { break; } } }然后建堆阶段对每个非叶子节点调用siftDown排序阶段每轮把堆顶和末尾交换一次再对剩余部分调整。堆排序的赋值次数通常比归并少因为它不需要辅助数组但它不是稳定的。面试时这里经常被追加提问为什么堆排不稳定答案就在siftDown的交换里相同元素可能被交换到不同相对位置。主函数里每种算法执行前都要“打一针”原始数据的拷贝因为排序是原地修改不清空计数直接串行跑会互相污染int main() { std::vectorint original generateRandomNumbers(1000, 0, 999); std::vectorint data; long long cnt1, cnt2, cnt3, cnt4, cnt5, cnt6; data original; cnt1 bubbleSort(data); data original; cnt2 selectionSort(data); data original; cnt3 insertionSort(data); data original; cnt4 quickSort(data); data original; cnt5 mergeSort(data); data original; cnt6 heapSort(data); std::cout 冒泡: cnt1 std::endl; std::cout 选择: cnt2 std::endl; std::cout 插入: cnt3 std::endl; std::cout 快速: cnt4 std::endl; std::cout 归并: cnt5 std::endl; std::cout 堆排: cnt6 std::endl; return 0; }这里一定要写data original而不是std::vectorint data(original)含义一样但后者多一次构造。真正重要的是数据副本必须独立否则第一个排序排完后面所有算法都在排有序数组赋值次数全废了。3.4 赋值次数与“赋值运算符重载”的一个隐蔽陷阱如果你把计数逻辑放进一个结构体甚至重载了运算符还有一个 C 特有的坑arr[i] arr[j]触发的是普通赋值但如果数组元素是自定义类型赋值运算符内部的多次子赋值也算不进来。建议把数组元素保持为int计数只放在排序函数外层别试图做“全面计数”否则你会陷入递归赋值和临时对象构造的泥潭。4. 实测赋值次数结果怎么读以及为什么选择排序不是最差的跑完 1000 个随机数范围[0, 999]种子固定为 42这个项目的输出大概落在这样一个量级算法赋值次数量级额外说明冒泡排序约 37 万75 万数据越逆序越接近上限选择排序约 15 万30 万赋值次数与比较次数解耦插入排序约 25 万50 万随机数据最坏约 n²/2 次移动快速排序约 2 万4 万受基准选择影响运气不好会变 6 万归并排序约 2 万3 万波动小稳定堆排序约 3 万5 万建堆加调整常数比快排大请注意这些是“量级”不是精确值。因为赋值次数和具体数据分布强相关你换一个种子数字结果会有正负 20% 的浮动。这也是为什么我反复强调调试时要固定种子。4.1 为什么选择排序赋值次数比插入排序少那么多很多人第一次看到这个表会惊讶O(n²) 家族里选择排序的赋值次数竟然能跟 O(n log n) 的堆排差不多。原因不复杂选择排序内层循环只比较不赋值每轮最多交换一次1000 个数最多交换 999 次每次 3 次赋值上限才 3000 次。它的“大 O”开销全在比较上赋值操作被压得极低。这说明一个反直觉的结论赋值次数的多少不能直接决定算法的实际运行时间。选择排序赋值少但它比较了约 50 万次总耗时照样比快排慢得多。赋值次数只是“拆解算法体力活”的一个切面不是性能的全部。4.2 赋值次数与比较次数两个指标配合看这个项目只统计了赋值次数但你可以顺手把比较次数也加上写一个cmpCount。配合看更有价值赋值少但比较多的算法选择排序适合“写操作昂贵、读操作便宜”的场景赋值多但比较少的算法比如快排比较约 1.5 万次、赋值 3 万次左右适合普通的现代 CPU因为内存写入比读取更伤缓存。4.3 跑一次 10000 个数字看数量级规律如果你想验证“复杂度分析”把 n 从 1000 改成 10000再观察赋值次数的增长系数。冒泡和插入的赋值次数大约涨 100 倍快排和归并大约涨 23 倍n log n 的增量这个对比比任何理论证明都直观。这也是这份资源最有价值的用法它是数据结构课程的“实验台”不是一次性脚本。5. 避坑指南赋值计数器常见的五个翻车现场这个部分是我自己在调试时踩过的坑基本每个都能让你的统计结果对不上理论值。5.1 把循环变量自增也算进了赋值次数现象冒泡排序的赋值次数算出来超过 150 万明显离谱。原因有人在for循环里写了cnt循环变量的i、j全部被计入了。解决明确计数范围只数“写数据元素”的代码行循环变量、中间变量的自增一律不算把计数语句放在全局搜索能搜到的那几行赋值代码旁边。5.2 归并排序漏数辅助数组写入现象归并排序的赋值次数竟然比插入排序还少完全解释不通。原因只数了arr[p] temp[p]回写漏了第一次写temp的语句。解决拆开数写temp一次算一次temp写回arr再算一次所以每个元素平均在赋值里出现两次。这也是归并排序的空间换时间在计数上的直接体现。5.3 快排递归里把计数器当值传子调用计算结果被丢弃现象快排赋值次数输出忽大忽小甚至有时是 0。原因quickSortHelper的计数器参数是long long cnt递归子调用修改的是副本返回到上层什么都没保存。解决改成引用传递long long cnt或者在函数外使用全局变量、lambda 捕获。5.4 数据几乎有序时拿“最好情况”当算法的平均表现现象某一次跑的冒泡赋值次数极低于是得出结论“冒泡也不错”。原因固定种子生成的数据碰巧接近有序或者上一轮排序已经排好了一个副本下一轮直接在有序数据上跑。解决跑之前确认数据副本来自同一个随机源不要复用已排序的向量同时准备三组数据——随机数据、逆序数据、几乎有序数据分别统计对比结论才完整。5.5 堆排序里漏掉“交换后还需要调整”的赋值现象堆排序赋值次数比快排还低一大截总觉得哪里不对劲。原因建堆和堆调整里有很多“把父节点下沉”的操作下沉过程中连续移动节点每次移动都产生赋值但新手常常只数了最外层交换的 3 次。解决把siftDown里的赋值全数进去堆排序的赋值次数会立刻涨到快排的 1.5 倍左右这就对了。6. 落底技巧验证你的计数器没有“假计数”最后这一章我想分享一个验证手段在你完全信任这些数字之前先证明计数器数得准。可靠性不是说服力。我自己研究过这类题花了三天时间修计数跑遍所有断言……其实没那么玄就是自己给自己造假数据逼计数器现原形。具体做法是自检。写一个逆序数组比如n 5的[5, 4, 3, 2, 1]手动推导每个算法的赋值次数再把你的代码跑一遍看输出是否一致。例如冒泡排序在完全逆序的五元素数组中第一轮交换 4 次第二轮 3 次……总交换 10 次每次 3 次赋值正好 30 次加上临时变量的操作期望值是 30。我之前修 bug 时第一版输出 27又多检查一遍——发现漏了一个关键赋值int tmp的初始化。落的坑真的全在细节上。另一招是“复制守恒”。给你递过的排序加一个assert(排序前后所有元素集合相同)注意相同集合不代表相同顺序。赋值统计过程中若元素少了或多出来排序本身就不可能正确。如果你在计数时改了arr[j] arr[i]这个方向顺序对但集合错断言直接骂你。从那以后我每次跑排序对比都强制走一遍小数组验证再放大规模。取值固定真的很重要一百次实验不如一个可复现的断言如果手上有这种验证习惯调试效率完全不是一回事。把n换成 10000、100000看看赋值次数的增长曲线是否贴合理论复杂度这是验证你“计数口径”的最后一关。如果结果乱跳大概率是计数位置写错了如果结果稳定放大就可以确定你的计数器是真实的。这个项目最有价值的用法是陪你做完排序算法的“体力对比”而不是输出一张漂亮但无法解释的表。希望帮到你。本文还有配套的精品资源点击获取
