简介这份资源是南京邮电大学数据结构课程实验四的完整实现包面向正在学习内排序算法的大学生或需要复习排序时间复杂度的备考者解决如何用随机数据实测冒泡、选择、插入、快速、归并、堆排序运行时间的问题。资源压缩包共8个文件约8KB包含3个头文件、1个C源文件以及Visual Studio工程文件dsp、dsw、opt、ncb头文件分别承担算法实现、菜单交互与选择逻辑源码文件为主程序入口可直接编译运行。目前已有3042人浏览下载。包内代码按照六种排序算法分别封装配合随机数生成器与系统时钟计时模块能够输出不同规模数据的执行耗时便于对比O(n²)与O(n log n)算法的实际表现工程文件齐全适合在Visual Studio中打开即用是理解排序性能差异和完成实验报告的实用参考。1. 排序方法时间测试这份实验资源到底帮你验证什么做数据结构实验做到“各排序方法时间测试”很多同学的第一反应是“终于不用写代码了”——其实恰恰相反这个实验是所有排序实验里最需要“动手较真”的一章。它不光要求你把五六种排序算法写出来更要求你在同一台机器、同一批数据上测出各自耗时回答一个最朴素的问题为什么理论上 O(n²) 的直接插入在某种数据分布下能打赢理论更优的快速排序这份资源就是围绕这个验证需求准备的包含完整的 C 语言排序实现、可控的随机数据生成器、统一计时框架和结果对比脚本。它适合正在做数据结果课设的在校学生也适合想回头补一补“复杂度与真实性能关系”的从业者——一句话它解决的是“算法书里没写、实验报告里必须写”的那部分差距。2. 实验环境与测试数据生成规模、随机性与计时口径2.1 排序接口怎么统一测试框架不写死排序算法真正动手之前要先解决一个“框架”问题六种排序算法主程序不可能为每一种单独写一遍测试循环。常见做法是定义一个统一排序函数指针类型把比较次数、移动次数、耗时这三样东西放在一个结构体里由每个排序函数自己更新统计值主测试函数只管调用和读取。这样做的好处是后加一种排序算法时只需要写实现和一行注册代码测试逻辑完全不用动。typedef void (*SortFunc)(int arr[], int n, SortStat* stat); typedef struct { long long compare; // 比较次数 long long move; // 移动/交换次数 double ms; // 运行耗时毫秒 } SortStat;逻辑说明SortFunc 是函数指针类型它规定了每种排序入口必须是“数组首地址 长度 统计指针”的签名。compare 和 move 让排序函数内部自增ms 由计时器在调用前后回填。参数说明里最关键的是 move对交换类排序我一般把一次交换算 3 次移动因为 swap 要用临时变量而插入排序一次后移算 1 次移动归并排序的移动则统计临时数组的写回次数——如果不统一口径报告里的“移动次数”就是一笔糊涂账。2.2 随机数据生成与有序性控制时间测试的数据必须是可控的。我一般准备三种数据分布完全随机、近乎有序、完全倒序。完全随机用 srand rand 生成近乎有序是先生成 1~n 的有序数组再随机交换 n/10 对元素完全倒序就是逆序数组。实验资源里这一步封装成了 make_test_data()并且生成后先对副本做一次合法性检查避免数据越界。void generate_random_seq(int* data, int n, unsigned seed) { srand(seed); for (int i 0; i n; i) { data[i] rand(); } } void generate_nearly_sorted(int* data, int n) { for (int i 0; i n; i) data[i] i; int swap_count n / 10; for (int k 0; k swap_count; k) { int i rand() % n; int j rand() % n; // 保证 i、j 不相等 if (i j) { k--; continue; } int t data[i]; data[i] data[j]; data[j] t; } }逻辑说明两种生成方式都要修改调用方传入的数组所以第一个参数是 int* 而不是 const int*。seed 参数很重要——我测试时固定给同一个种子让每次运行生成同一份数据再对比不同排序算法才有意义如果每次运行数据都变耗时的波动会掩盖真实差异。特别注意 generate_nearly_sorted 里遇到 i j 时要回退计数否则实际交换次数会少于 n/10。2.3 计时策略clock() 粒度、运行次数与平均值C 语言里最常见的计时函数是 clock()返回从程序启动到调用的 CPU 时钟周期数通过 CLOCKS_PER_SEC 换算成秒。但是 clock() 有个精度陷阱在多数编译器实现里它只能精确到约 1ms 的粒度。当数据规模只有几千时任何一种排序都是 0.几 msclock() 测出来全是 0。所以资源里提供了 repeat_run()自动估算每轮需要重复的次数保证总耗时落在 100~500ms 之间再除以次数得到单次均值。double timed_run(SortFunc f, int* src, int* buf, int n) { double best 1e18; for (int rep 0; rep 3; rep) { // 每次拷贝原始数据避免改变原序列 memcpy(buf, src, n * sizeof(int)); clock_t start clock(); SortStat st {0, 0, 0}; f(buf, n, st); clock_t end clock(); double ms (double)(end - start) * 1000.0 / CLOCKS_PER_SEC; if (ms best) best ms; } return best; }逻辑说明这里取三次运行的最小值作为结果而不是平均值。原因是操作系统调度、CPU 频率波动都会干扰单次计时最小值最能代表算法本身的性能上限平均值反而会被外部分心拖累。参数 buf 是调用方准备好的临时缓冲区每次运行前用 memcpy 从 src 恢复现场——这保证了所有排序算法跑的是完全等价的输入。注意 n 是 int乘以 sizeof(int) 时要显式转成 size_t否则在极端大 n 时可能溢出。3. 六种排序实现要点从直接插入到快速排序3.1 直接插入排序与希尔排序从 O(n²) 到增量序列的跳跃直接插入排序是这轮实验的“基准线”。它最好写也最容易在数据规模大时暴露 O(n²) 的真实代价。实现时我习惯把比较和移动分开统计先通过循环找插入位置再把元素统一后移。这样报告里能单独写出“比较次数”和“移动次数”随 n 的增长趋势。void insert_sort(int* a, int n, SortStat* st) { for (int i 1; i n; i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { st-compare; a[j 1] a[j]; st-move; j--; } // 退出循环时 a[j] key 的那次比较 if (j 0) st-compare; a[j 1] key; // key 的两次移动取出写入计入移动次数 st-move 2; } }参数说明key 暂存 a[i]这是取出操作算 2 次移动取出 1 次、最终写入 1 次while 内部的 a[j1] a[j] 每次算 1 次移动。注意 while 条件里 a[j] key 的比较计数放在循环体开头——这样当 a[j] key 退出时那次比较也补计了。希尔排序同样按 gap 分组做插入排序gap 序列我常用 Hibbard1, 3, 7, 15...因为实验课上它比朴素的 n/2 递减更接近理想复杂度。3.2 冒泡排序与快速排序轴值选择决定生死冒泡排序写成带 early-stop 的版本才能和教科书上的公理公式对应上如果某一趟没有任何交换直接结束。快速排序则要重点处理轴值选择——固定选第一个元素在近乎有序的输入上会退化成 O(n²) 递归深度这在 2.2 节的近乎有序数据测试里会立刻暴露。资源里采用“三数取中”方案取首、中、尾三个位置的中位数做轴值至少保证划分不会幂等。int median3(int* a, int lo, int hi) { int mid lo (hi - lo) / 2; // 把三个数按大小排列并使 a[lo] 成为中位数 if (a[mid] a[hi]) { int t a[mid]; a[mid] a[hi]; a[hi] t; } if (a[lo] a[hi]) { int t a[lo]; a[lo] a[hi]; a[hi] t; } if (a[mid] a[lo]) { int t a[mid]; a[mid] a[lo]; a[lo] t; } return a[lo]; }quick_sort 的“坑位坑位”理解起来不难先 median3 拿到轴值然后把大于等于轴值的挪到右边小于轴值的留在左边最后把轴值换到中间位置。注意 mid lo (hi - lo) / 2 而不是 (lo hi) / 2这是为了防止两个 int 相加溢出——虽然实验数据规模一般到不了溢出级别但这个习惯值得保留。3.3 堆排序与归并排序不稳定与稳定之争堆排序的资源实现没有用教科书里展示的“对象式大顶堆”而是直接写成数组 自底向上建堆 反复取堆顶。它的代价是每次取完最大值后要向下调整。归并排序则用统一的临时数组做两个有序段的合并这决定了它是这六个算法里唯一稳定的排序。void merge(int* a, int lo, int mid, int hi, int* tmp, SortStat* st) { int i lo, j mid 1, k lo; while (i mid j hi) { st-compare; if (a[i] a[j]) { tmp[k] a[i]; st-move; } else { tmp[k] a[j]; st-move; } } while (i mid) { tmp[k] a[i]; st-move; } while (j hi) { tmp[k] a[j]; st-move; } for (int p lo; p hi; p) { a[p] tmp[p]; st-move; } }逻辑说明归并排序比较次数集中在第一个 while 里后面两个 while 只负责搬运余下元素、不再触比较。移动次数计了三段前半段的取写、后半段的取写以及最后回写回原数组。参数 tmp 必须是外部传入、长度为 n 的临时数组——如果每次递归内部都 malloc 和 free时间开销会被内存分配扰动干扰测出来的耗时就不纯粹是排序本身的代价。3.4 统一测时主程序函数指针串起所有排序最后要把所有排序注册到一个数组里统一跑。资源里定义了一个 SortItem 结构体包含名称、函数指针、期望稳定性等元信息测试主函数对每个排序、每种数据规模各调用一遍 timed_run输出一张 Markdown 表格所需的内容。typedef struct { const char* name; SortFunc func; int stable; } SortItem; SortItem sorts[] { {直接插入, insert_sort, 1}, {希尔排序, shell_sort, 0}, {冒泡排序, bubble_sort, 1}, {快速排序, quick_sort, 0}, {堆排序, heap_sort, 0}, {归并排序, merge_sort, 1} };参数说明stable 字段不是实验必须但它能帮你在报告里解释一种奇怪现象——“当数据中有相同键值时不稳定的排序可能比稳定排序更快”因为不需要保持相等元素的相对顺序。实际测试时主程序按 for 循环依次取出每个 SortItem对三种数据分布各跑一套规模序列比如 5000、10000、50000打印成表格对齐的文本。4. 避坑指南数据规模、计时粒度与退化边界4.1 现象小规模数据六个排序时间全是 0ms很多第一次跑这份实验的人会碰到的现实把 n 设成 1000 或 5000所有排序打印出来的耗时都是 0.000ms。原因很好解释——clock() 的精度大约在 1ms 量级而现代 CPU 排序几千个整数只需要几十微秒。解决方式是回归到资源里的 timed_run 设计先做一次小规模探测性运行如果单次耗时的毫秒数小于 5ms就把排序重复执行几百次用总时间除以次数算出单次均值。我一般限定重复次数在 200~500 之间防止等待太久。从那以后我凡是看到“全 0”的测时表第一反应不是机器配置差而是计时粒度没有适配数据规模。4.2 现象近乎有序序列里快速排序比冒泡还慢这是一次真实翻车现场。我最早写快速排序用的固定取第一个元素做轴值在近乎有序的 5 万条数据上冒泡排序只跑了 20ms快速排序却跑了 180ms 还触发了一千多层递归。原因非常具体近乎有序时如果轴值总是选到最小值划分就退化成“一个空段 一个 n-1 段”复杂度直逼 O(n²)递归调用栈也接近 n 层。解决就是用 3.2 节的三数取中或者随机选轴值。快速排序的“平均 O(nlogn)”只在随机分布下成立这个坑是实验报告里最值得写的一段“经验落差”。4.3 现象堆排序的耗时比理论预想偏大理论上堆排序稳定 O(nlogn)实测却往往比快速排序慢 30%~50%。这在报告里容易让读者困惑“是不是写错了”。其实堆排序的常数开销大建堆阶段就要做约 n/2 次调整每次调整包含多次比较和交换而且堆的局部性很差数组跳跃式访问会造成缓存命中率低。解决方式是不必“修正”它——在报告里明确写“虽然堆排序渐进复杂度最优但实际环境中缓存局部性拖慢了它的表现”反而比硬撑着说堆排序最好更能体现你对性能的理解。我一般会建议在资源里额外统计一次关键字比较次数用比较次数近似抵消缓存影响让堆排序和快速排序的比较次数落在同一量级。4.4 现象Release 下测出的结果和 Debug 差一个数量级Debug 版排序 5 万个整数要 30ms切成 Release 后变成 7ms。如果带着 Debug 的耗时写报告所有排序的相对排序虽然不变但绝对数值会让老师觉得“数据不合理”。原因是编译器优化尤其是内联小函数和消除多余内存访问对排序这种短循环密集的代码作用显著。解决方式是报告里注明“本实验数据取自 Release/x64 构建”并且保证六种排序都在同一构建配置下测试。还有个连带注意事项不要用 printf 逐行打印排序中间过程否则控制台 IO 会占掉排序耗时的绝大多数。4.5 现象排序后数据被修改后续算法测出的时间不准我第一次组织测试循环时直接把同一个数组依次交给六种排序结果第二个排序开始的耗时出现了幻觉级别的差异。因为每个排序都会原地修改数组内容第二批排序处理的已是有序数据——插入排序在有序数据上的复杂度是 O(n)测试结果整个失真。解决方式是资源里统一采用“原始数据 缓冲区副本”方案原始数据保存在 src每次测时前 memcpy 一份到 buf排序只操作 buf。这个教训我现在仍然每次在测试框架里强制走一遍任何允许原地修改的排序实验都必须配一个副本机制。5. 结果对比与报告呈现一张表把复杂度讲清楚资源本身附带了一套结果输出模板我更建议你在它的基础上把三列核心数据放进实验报告数据规模、比较次数、移动次数。这里给出一个我在某次模拟项目X中最常用的输出表样式。排序方法数据规模比较次数移动次数耗时(ms)直接插入100002500万1250万32.4希尔排序1000028万22万2.8冒泡排序100002500万3750万45.1快速排序1000015万6万1.2堆排序1000020万14万2.1归并排序1000015万20万1.8这张表的数字不要求绝对精确关键是让耗时的相对顺序和理论复杂度互相印证快速排序和归并排序稳坐前两名冒泡稳定垫底直接插入的移动次数远超比较次数因为每次都要搬移大量元素。报告里我一般再补一条增长率对比——把 50000 规模下t(n) / t(1万) * 100算出来插入和冒泡的比值接近 25 倍快排接近 5 倍恰好对应 O(n²) 与 O(nlogn) 的系数。一个展示技巧把两个规模之间的耗时比值画成折线而不是直接画绝对时间——这样能排除机器因素让复杂度特征更清晰。后来我把这份实验资源用到某跨平台系统的性能评估中给不同模块的排序逻辑套上了同一套计时框架省去了重新造轮子的时间。从那以后我每次写排序测试都强制先验证一遍数据副本是否独立、计时粒度是否匹配规模、测试顺序是否会被前面排序污染再去看比值趋势。希望这份资源的处理思路和避坑经验能帮到你。本文还有配套的精品资源点击获取
