排序实验_2012年11月.docVIP

排序算法综合实验 1．实现基本排序方法：直接插入、希尔、直接选择、冒泡、快速、堆、二路归并； 2．每种基本排序方法尽量给出多种实现（包括改进）； 3．给出实验结果： （1）随机生成若干个随机数进行排序（如n＝104，2＊104，105，…等） （3）给出实验结果、原因分析、结论等（如改进效果明显或不明显的原因？算法的实际时间增长速度如何？复杂性相当的算法之间快慢如何？等等） （4）所有实验结果汇集成一张表，参考格式如下： 　 CPU Athl AMD on(tm) 7750 姓名 　 内存 kingston DDR2 2.70GHz,2.00G 学号 　 主板 华硕 M3N78 SE 班级 　 操作系统 Microsoft Windows XP Professional (sp3) 电话 　 编译软件 C-free 4.0 email 　 　 　 10^3 2*10^3 10^4 2*10^4 10^5 2*10^5 10^6 2*10^6 10^7 10^5 正序 逆序 直接插入 (带监视哨） C t(时间) 5min 直接插入 (无监视哨） C 　 t 5min 改进 C 　 t 5min 。。。 C t 堆排序 (非递归) C t 堆排序 (递归) C t 改进 C t 4．注意事项： （1）使用标准C或C++语言，不要采用开发工具； （2）独立完成，不要互相抄袭，否则记0分。 （3）伪造实验数据者，记0分。 （4）算法的各种实现尽量多些（可分析效率低的原因、存在的问题等有针对性地改进，比如直接选择排序当初始序列已经有序时仍要执行n-1趟，是没有必要的）。 （5）汇总表中规模n的大小不一定取104~108，可根据自己的计算机情况调整和增加，以使排序时间不要太小或太大。若有的算法时间太长(如大于5分钟)，可中途终止，并在汇总表中注明。 （6）作业集中后上交，程序部分压缩到一个文件（并自留备份），压缩文件名格式为：班级+学号+姓名，如“07电信(1)200****673张三”。 （7）作业上交形式：纸质文档＋压缩文件。其中，文档部分不是程序的使用说明书，也不是程序的简单打印，要比较详细地讲明算法原理和方法，程序部分要有必要的注释。压缩文件上要有所有的程序和纸质文档的电子原文（如word文件）。 （8）文档可以双面打印，字号和行距不要太大，如5号字和单行间距就可。 （9）汇总表作为文档的首页。 CPU 英特尔 Pentium(奔腾) 双核 T4400 @ 2.20GHz 姓名 史铿圳 内存 2 GB ( 海力士 DDR3 1067MHz ) 学号 201030580323 主板 联想 2842ENC (英特尔 4 Series - ICH9M 笔记本芯片组) 班级 10电信3班 操作系统 Windows 7 旗舰版 32位 SP1 ( DirectX 11 ) 电话 编译软件 C-free 4.0Mircosoft Visual C++ 2010 email 949639772@ 10^3 2*10^3 10^4 2*10^4 10^5 2*10^5 10^6 2*10^6 10^7 10^4 正序 逆序 直接插入 (带监视哨） C 0.24964 0.98838 24.9629 100.158 2506.14 10025.2 0.0099 50.005 M 0.25063 0.99037 24.9729 100.178 2506.24 10025.4 0 50.015 t(时间) 0.002 0.042 0.253 0.823 22.172 91.601 5min 5min 5min 0 0.392 直接插入 (无监视哨） C 0.24964 0.98838 24.9629 100.158 2506.14 10025.2 0.0099 49.995 M 0.25063 0.99037 24.9729 100.178 2506.24 10025.4 0 50.015 t 0.003 0.009 0.266 0.897 25.201 95.625 5min 5min 5min 0 0.424 改进(二分插入) C 0.0085