【C++/数据结构】求各种排序算法的绝对执行时间

(2019-2020学年第一学期「数据结构」课程设计)

废话不多述,直接上正文。(碎碎念在最后)
代码:https://github.com/StargazerSylpha/Sorting_Time_Comparison


一、背景:

随着互联网的发展和大数据的深入应用,庞大的数据伴随着巨大的管理压力和各种需求的提出,对后端程序的设计水平和工程师的技术提出了新的挑战。本程序以日常工作中最基本的整型数据的正序排序为基准点切入,提出8种常用的排序方法,代入不同量级、不同大小的数据,测试这8种排序方法的效率,以直观的数字和图表进行展示,以便在以后的工作中,针对不同的排序场景,使用更具效率的算法,减少后台负载,提升项目整体的效率。
8种常用的排序方法:冒泡排序、快速排序、直接插入排序、简单选择排序、折半(二分)插入排序、希尔排序、堆排序、二路归并排序。


总览图


二、Feature:

①支持自定义排序数据大小和数据数量:

#define MAXSIZE 10001      //允许的数组大小最大值,由于内存原因目前最大可以到10w,再往上报错
#define NUMLIM 99       //自动生成数据最大值,可以尝试万级别,但相应的排序时间会成倍增加

其中:自定义数组大小(数据数量)功能,在一般普通高校机房(指win7下使用vc++6.0)下经测试最大支持1w,再增加数量就会不输出结果直接结束程序;在我的电脑上(Visual Studio Code for macOS 1.41.0 with C/C++ 0.26.2 and Code Runner 0.9.15)经测试最大支持10w,再增加数量会直接报错,经查询是内存类型的原因(堆内存/栈内存)。由于时间紧迫,没有再深入优化。

②支持结果输出开关:

#define ARROUT 1        //数组输出控制 1开启,0关闭

开发时因为所有排序算法写在一个cpp文件内,故设置这样一个功能,开启后快速定位哪个排序方法有bug(即就算排序结果错误,输出错误后错误的排序序列也会一并输出)。然而如果数据量过大,你最好关上,不然就会出现满屏数字的地 狱 绘 图…(这也算feature?)

③支持自行输入数据进行排序:

做的时候因为验收顺序靠后,听见前面的组被老师问有没有这个功能,为了以防万一又花了几分钟加的功能。如果输入的个数不够自己设定的n个,那么其他置0;超过n个,则只取前n个;输入字母直接被忽略。


三、数据图表:

折线图展现了不同测序方法在不同数据量级下所需的时间,其中横轴为数据量级,纵轴为所需时间(单位为秒)。可以看出一万量级(包括一万)的数据各排序方法所需时间并没有明显的差别,但增长到五万量级后,差距便很明显地展示了出来;十万量级,差距进一步被拉大。冒泡排序最慢,简单选择排序其次,直接插入排序和折半(二分)插入排序紧跟其后;其他方法不分伯仲。


四、后记:


开发环境(机房),头一次感觉像是有了专属于自己的工位一样(笑)

开发是选在复习周的其中一个周末,分组,2天时间蹲在机房,类似编程马拉松似的方式在2天之内完成开发、测试以及文档的撰写和答辩(不过正规的比赛都是吃喝都在电脑前,我们好歹条件还好点…),故时间并不充裕,也没有进行优化。源代码里其中几段密密麻麻的注释是给组员应付答辩用的,以及被老师建议做一下桶排序相关的测试。

参考资料:数据结构教程(第5版)上机实验指导,李春葆主编,清华大学出版社(P251)
就这样吧。