数据结构综合实验

1# 大 中 小 发表于 2004-11-24 14:50 只看该作者 同路人—同济鹊桥 | 同渡重洋—海外生活 | 同济大学新闻 真·同济，尽在投票统计
求助高手：数据结构大作业--排序算法改进综合实验。麻烦大家帮忙，小弟感激不尽！！ ※ 来源: 同济网论坛 BBS.TONGJI.NET

1．实现基本排序方法：直接插入、希尔、直接选择、冒泡、快速、堆、二路归并；
2．对每种基本排序方法尽量给出改进算法；
3．给出改进前后的实验结果：
（1）随机生成若干个随机数进行排序（如n＝10的3次方，2＊1010的3次方，10的4次方，…等），记录每个排序的时间耗费。
（2）分别给出正序和反序的初始序列进行排序（如n＝104），检验算法对初始序列的敏感程度。
（3）给出实验结果、原因分析、结论等（如改进效果明显或不明显的原因？算法的实际时间增长速度如何？复杂性相当的算法之间快慢如何？等等）
排序算法实验比较(单位：秒)
（4）所有实验结果汇集成一张表，参考格式如下：
计算条件：
CPU：＊＊＊（如AMD XP2000+,P4 2.0A等，不要超频）
内存：＊＊＊（如HY DDR333 512M等，不要超频）
主板：＊＊＊（如＊＊牌＊＊型号）
操作系统：＊＊＊（如Windows 98,Windows XP等）
编译软件：＊＊＊（如VC＋＋6.0等）
其它：＊＊＊(对计算结果有影响的需要说明的软、硬件情况)

4．注意事项：
（1）使用标准C或C++语言，不要采用开发工具；
（2）伪造实验数据者，记0分。
（3）各种算法的改进要尽量有、尽量多些（可分析效率低的原因、存在的问题等有针对性地改进，比如直接选择排序当初始序列已经有序时仍要执行n-1趟，是没有必要的），如果只有基本算法，而几乎没有改进算法，则做得再好，也没有高分。
（4）汇总表中规模n的大小不一定取103~105，可根据自己的计算机情况调整和增加，以使排序时间不要太小或太大。若有的算法时间太长(如大于10分钟)，可中途终止，并在汇总表中注明。
（5）作业上交形式：纸质文档＋盘。其中，文档部分不是程序的使用说明书，也不是程序的简单打印，要比较详细地讲明算法原理和方法，程序部分要有必要的注释。盘上要有所有的程序和纸质文档的电子原文（如word文件）。

附录：参考知识
1．排序时间：由clock()函数得到时钟数，排序前后的时钟数之差／每秒的时钟数，即得时间（秒）
#include
…
InsertSort(R,n);
t2=clock();
cout<<"时间："<2．随机数的生成
#include
…
for(i=1;i<=n;i++)
R.key= rand();//生成0-RAND_MAX之间的随机数
但rand()只生成0-RAND_MAX（一般为65535）之间的随机数。当问题规模n较大时，将生成很多重复的随机数。比较合适的方法是生成0－n之间的随机数，这要用random(int num)函数。它可生成0－任意数num之间的随机数。但该函数在VC＋＋中没有定义，可自己定义如下：
int random(int num) { return rand()*num/(RAND_MAX+1);}
…
for(i=1;i<=n;i++)
R.key=random(n);//生成0-n之间的随机数
3．各个算法单独运行会很繁，可分别调通后编一个菜单程序集中起来