排序算法性能实验

数据结构与算法课程(大二上)大作业:八种经典排序算法的 C++ 实现与同规模数据下的性能对比实测。

任务背景

(以下依据实验报告与源码整理)

• 目标:在同一份随机数据上实测多种经典排序算法在不同规模下的耗时,验证时间复杂度与实际性能的对应关系。
• 算法:冒泡、直接插入、折半插入、树形选择、归并、快速、堆排序,代码中另有选择排序,共 8 种。
• 数据生成:C++11 random_device 作种子,mt19937 加 uniform_int_distribution 在 1~1e8 范围等概率生成随机整数,7 个数组填入同一份数据,保证各算法输入一致。
• 计时方法:<ctime> 的 clock(),取排序前后差值除以 CLOCKS_PER_SEC 得到秒数。
• 测试方案:规模取 1e4、1e5、1e6、1e7、5e7(原计划到 1e8,受静态 int 数组内存限制未跑满),每档重复 10 轮取平均;单轮超 100 秒记为”超时”,日志中对应位置输出 0s(该算法在该档被跳过)。
• 实验环境:Linux 服务器(x86,GOLD 6338),g++ 11.4.0,-O3 单线程编译运行。
• 结论:O(nlogn) 类(快排最优,归并、堆排、树形选择次之)在 1e6 以上规模全面胜出,O(n²) 类(冒泡、插入类)在 1e6~1e7 档相继超时。

内容结构

路径	说明
排序集.cpp	主程序(367 行):8 种排序实现 + 计时框架,本地调试版,n=7e7、repeats=1,当前启用插入与折半插入两组计时
linux/a.cpp	Linux 服务器跑分版(318 行):同一套算法,输出 Scale: n,n=5e7、repeats=10,当前启用树形选择、归并、快排、堆排计时
testresult.log	实测输出:1e4/1e5/1e6/1e7/5e7 五档 × 10 轮的平均耗时(nohup 后台运行产生)
.gitignore	忽略编译产物与压缩包

说明:两份 .cpp 是同一程序在不同调参阶段的快照,跑不同档位时改动源码顶部的 n 与 repeats 再重新编译。未入库:实验报告(.doc)、作图数据(.xlsx)、运行截图(.png)、提交压缩包、编译产物(排序集.exe、a.out)。

运行方法

依赖:任意支持 C++11 的 g++/clang++,无第三方库。

# 编译并运行(Linux/macOS)
g++ -O3 -o sortbench linux/a.cpp
./sortbench

# Windows(MinGW-w64/g++)
g++ -O3 -o sortbench.exe 排序集.cpp
./sortbench.exe

• 修改规模:改源码中 #define n 50000000;修改轮数:改全局变量 repeats,随后重新编译。
• 需要测哪几种排序,就注释/取消注释 main 里对应的计时代码块。
• 内存提示:7 个长度 n 的 int 静态数组,n=5e7 时约需 1.4 GB 内存,n=7e7 约 2 GB;O(n²) 算法在 1e6 以上规模单轮可达百秒级,建议先小规模验证。

来源声明

• 8 种排序算法的实现、计时与随机数据框架、全部实测数据为本人独立完成,用于课程大作业提交。
• 算法原理与实现思路参考《数据结构与算法》课程讲义,未指明具体教材版本。
• 本仓库只收录代码与实测日志;实验报告、图表等文档不入库。