内部排序算法的性能分析
15 / 36
5 系统实现及数据分析
5.1系统实现
? 主界面如图所示
图11 主界面
? 性能对比示例如图所示
图12 性能对比图
5.2数据分析
1） 数据制表
对多组测试结果进行统计得出如下三个表，分别见表4，表5，表6，其中实
15
验中数据全部为随机生成的整数;时间消耗为5次测试平均值,单位为毫秒(ms)。
内部排序算法的性能分析
16 / 36
表4 时间对比结果（单位：毫秒）
排序长度 插入排序 起泡排序 选择排序 希尔排序 快速排序 堆排序 2000 5000 8000 10000 20000 30000 40000 50000 60000 70000 80000 9 67 134 259 848 1925 3516 5570 7879 10730 14560 17 110 258 479 1768 3958 7145 11356 16381 22209 34022 9 55 113 230 692 1604 2849 4479 6608 8807 11393
表5 比较次数
排序长度 插入排序 起泡排序 选择排序 希尔排序 快速排序 100 500 1000 2000 3000 5243 136140 507533 2022071 4518507 4922 124047 498905 1997047 4495799 4950 124750 499500 1999000 4498500
表6 移动次数
排序长度 插入排序 起泡排序 选择排序 希尔排序 快速排序 100 500 1000 2000 2713 68560 254755 1013024 7575 202722 758313 3027120 294 1479 2970 5876 462 2844 6000 12998 462 2844 6000 12998 堆排序 405 2004 4020 4131 5054 111973 420326 1681275 3902350 907 6621 14710 33101 52383 堆排序 205 1020 2045 4131 6093 6 52 99 196 634 1374 2605 3998 5623 7958 10169 0 1 2 2 5 8 11 14 17 25 26 0 0 0 1 1 2 2 3 4 4 5 16
内部排序算法的性能分析
17 / 36
3000 2262239 6768777 8973 20432 20432 11919 2） 数据分析
从 以上表格可以得出以下信息
? 时间消耗上，基本上呈现“起泡排序>插入排序>选择排序>希尔排序>快
速排序>堆排序”现象
? 比较次数上，基本上呈现“插入排序>选择排序>起泡排序>希尔排序>快
速排序>堆排序”现象
? 移动次数上，基本上呈现“起泡排序>插入排序>希尔排序=快速排序>堆
排序>选择排序”现象
3） 得出结论
a) 各种算法执行时间是待排序长度n的函数,并且问题规模越大,时间消耗
越多；
b) 待排序长度n相同情况下,冒泡排序算法消耗时间最多,堆排序和快速排
序消耗时间最少,即快速排序和堆排序性能最优,而冒泡排序性能最差,其他算法的时间性能介于他们之间[7]；
c) 排序算法的性能分析和选择是一个复杂而又实际的问题,文中讨论的仅
仅是这6种排序算法的平均时间性能.在实际应用中,应根据经验和实际情况合理选择算法.例如,从平均时间性能而言,快速排序是相当快的,其所需时间最省,但快速排序在最坏情况下的时间性能却不如堆排序和归并排序.又比如,在插入排序、冒泡排序和选择排序中,以直接插入排序为最简单,当序列中的记录/基本有序0或问题规模n较小时,它是最佳的排序方法.因此常将它和其他的排序方法,诸如快速排序、归并排序等结合在一起使用[3]；
d) 建立在插入排序基础上的希尔排序和建立在起泡排序基础上的快速排序
的性能表现均比两者中前者强。
e) 综上，当排序长度较大时（上千条），且不考虑稳定性的时候，选用快速
排序或堆排序占用的系统资源较少。
17
内部排序算法的性能分析
18 / 36
6 结束语
通过此次课程设计的实践，感触较深。不仅使我加深了对书本知识的理解，
而且锻炼了我编写程序、调试程序能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯。同时，课程设计也充分弥补课堂教学及普通实验中知识的缺陷。 这次课程设计由于时间有限，对有些地方考虑的还不够周到，例如有些算法还可以优化，例如冒泡排序，在排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。
在设计的时候，一开始总想到把各种功能都实现，所有的好的东西都去尝试
一遍，后面发现这样子花费的时间实在是太多了（事实上我完成现在的课程设计花费的时间比起其他的同学来说也算是花费了很多时间了）苦逼的我连续四天日夜奋战只能看到晚上的月亮——早上起来的时候看到的是月亮搞了一天课程设计出来的时候还是月亮，元旦美好时间在程序猿眼里变得是那么不值得一提了。
编程的时候，我尽量把代码写得尽善尽美，写代码犹如写文章，读代码犹如
读文章，我发现我开始把代码当成是一篇篇美文一首首绝妙的音乐了，是写出优美动人的文章呢，还是堆砌枯燥乏味的文字，美感就开始在你的代码下面开始显现出来了，尽管对于这个小程序，无论是标识符的命名，还是宏定义的实现，我都感觉还很糟糕（或许是这半年来看Openssl,Gnutls工程里边代码写得太漂亮了吧），其实一开始，我真不想在程序里面写起满满的注释，注释写着写着，感觉自己有点白痴了。有些功能我的标识符实在是说得相当清楚了，迫于老师的硬性要求中文注释不少于50%，我还是硬着头皮写了满满的注释，可能是老师跟我认为的不一样觉得写满注释好看些吧。
以前真没有什么概念各种排序算法会在性能上有很大的差距，一想到排序马
上就敲起泡算法了，结果自己的程序告诉我什么起泡冒泡的性能上真是弱爆了。今后要学点高级点的排序算法，至少起泡算法，我现在是不是很想再用下去了。
18
内部排序算法的性能分析
19 / 36
参考文献
[1] 殷人昆,陶永雷,盛绚华,等.数据结构(用面向对象方法与C++描述)[M].北京:清华大学出版社,1999.301.
[2] 严蔚敏,吴伟民.数据结构(C语言版) [M].北京:清华大学出版社.2012.5～48.
[3] 方 斌,邓丽霞.六种排序算法时间性能的实验分析[J]. 郧阳师范高等专科学校学报.2005，23（4）：23～24
[5] 王 莉,各种内部排序算法的比较.科技信息.2012,10（5）：90
[6] 蒋晓玲,吴瑞红,李相俭,张环冲.常见内部排序算法综述.计算机与网络.2011,20(2)：220
[7]申雪琴,内部排序算法的性能分析与探讨[J]. 河西学院学报.2011，27（5）：50～54
19