排序效率比较.docx

《排序效率比较.docx》由会员分享，可在线阅读，更多相关《排序效率比较.docx（13页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、石河子大学信息科学与技术学院信息管理与信息系统专业08级 排序效率比较专 业： 班 级： 姓 名： 指导教师： 二OO九年 八月 二十七 日- 1 -编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第11页 共13页目 录1.课程设计目的12.课程设计题目描述和要求13.课程设计报告内容14.课程设计总结7参考书目8源代码9课程设计的内容如下：1.课程设计目的用C+编一程序对排序方法进行比较，用选定的排序方法进行排序，输出每种方法数据比较或交换的次数，最后输出所花费的时间。2.课程设计题目描述和要求问题描述对排序法进行比较，比较其运行效率。基本要求至少对三种排序方法进行比较，

2、比较方法是生成一组数据(400)。 （1）用三种方法对四百个数字进行排序；（2）用time函数分别测试三种排序方法就同一组数据排序所消耗的时间；（3）分别测试三种排序方法就同一组数据排序所交换的次数；3.课程设计报告内容3.1 结构图（1）功能结构图排序效率 比较测试选择排序所需时间测试冒泡排序所需时间测试插入排序所需时间（2）数据流程图主函数main测试选择 排序测试冒泡 排序测试插入 排序调用Time函数调用选择排序函数调用Time函数调用冒泡排序函数调用Time函数调用插入排序函数开始3.2 主要函数功能描述（1）Time() long beginTime =clock();/获得开始时

3、间，单位为毫秒 * * * * * * * * * * * * * * * * * * /程序 long endTime=clock();/获得结束时间 coutbeginTime:beginTimeendlendTime:endTimeendl endTime-beginTime:endTime-beginTimeendl; 作用：测试任意程序运行所用时间，单位为毫秒。（2）void T1 (int *a)作用：测试选择排序所用时间，先调用Time函数记录开始时间，再调用选择排序函数（比较相邻两个数，大的放在后面，然后最大的数沉底，最后从小到大排列），最后记录交换次数和结束时间；（3）voi

4、d T2 (int *a)作用：测试选择冒泡所用时间，先调用Time函数记录开始时间，再调用冒泡排序函数（比较相邻两个数，小的放在前面，然后最小的数上浮，最后从小到大排列），最后记录交换次数和结束时间；（4）void T1 (int *a)作用：测试插入排序所用时间，先调用Time函数记录开始时间，再调用插入排序函数（先两个数比较大小，大的在后，然后插入一个数分别与左右比较，小数在前，大数在后，最后从小到大排列，最后从小到大排列），最后记录交换次数和结束时间；3.3 测试结果与分析（1）增加模块（2）分析：用实际数据分别说明三种排序的运行效率4.课程设计总结通过一年对数据结构程序设计的学习，我

5、已经能够进行简单的程序设计，这次课程设计对自己所学知识起到了检测和提高的作用。虽然已经完成，但是还有很多不足之处，程序的设计中遇到不少问题，例如如何进行排序算法的边写，Time函数的应用等等，通过和同学的讨论与交流，解决了不少问题。程序的调试过程中也有不少问题，例如标点、菜单的界面设计等。课程设计完成后，感觉上最大的收获就是在设计之前要有一个清晰的思路和完整的设计提纲，对各功能函数的作用做详细考虑。细心在这次课程设计中起到很关键的作用，一个标点、一个字母、一个符号都可能导致程序的不能运行，因此要有耐心认真完成。当然知识是不可缺少的，只有对这学期所学得知识能够真正掌握并能加以运用，才能顺利完成这

6、次的课程设计。如果把磁盘文件学的精通一点，就可以用磁盘文件读取数据。参考书目：谭浩强，C+程序设计，北京，清华大学出版社，2006年.源代码：#include /头文件#includeusing namespace std;int t1,t2,t3;void T1 (int *a)long beginTime =clock();/获得开始时间，单位为毫秒 int i,j,k,t,n1=0;for(i=0;i399;i+)k=i;for(j=i+1;j400;j+)if(ajak)k=j;t=ai;ai=ak;ak=t;n1+; /选择排序for(i=0;i400;i+)coutait;long

7、 endTime=clock();/获得结束时间 coutbeginTime:beginTimeendl;coutendTime:endTimeendl; coutendTime-beginTime:endTime-beginTimeendl;coutn1=n1endl; /n1为选择排序交换的次数 t1=endTime-beginTime;coutt1=t1endl; /t1为选择排序所用时间void T2 (int *a)long beginTime =clock(); /获得开始时间，单位为毫秒 int i,j,k,t,n2=0;for(i=0;i399;i+)k=i;for(j=i+1

8、;j400;j+)if(ajak)k=j;t=ai;ai=ak;ak=t;n2+; /起泡排序for(i=0;i400;i+)coutait; long endTime=clock(); /获得结束时间 coutbeginTime:beginTimeendl;coutendTime:endTimeendl; coutendTime-beginTime:endTime-beginTimeendl;coutn2=n2endl; /n2为起泡排序交换的次数 t2=endTime-beginTime;coutt2=t2endl; /t2为起泡排序所用时间void T3(int *a) long beg

9、inTime =clock(); /获得开始时间，单位为毫秒 int i,j,n=400,n3=0,b;for(i=2;i=400;i+)b=ai;for(j=i-1;baj;j-)aj+1=aj;aj+1=b;n3+; /插入排序for(i=1;i=n;i+)coutait;coutendl; long endTime=clock(); /获得结束时间 coutbeginTime:beginTimeendl;coutendTime:endTimeendl; coutendTime-beginTime:endTime-beginTimeendl;coutn3=n3endl; /n3为插入排序交换的次数 t3=endTime-beginTime;coutt3=t3endl; /t2为插入排序所用时间void main()int a401; for(int i=0;i401;i+)ai=(401-i); T1(a); /分别调用函数T2(a);T3(a); 第 11 页 共 13 页