排序效率比较

石河子大学信息科学与技术学院信息管理与信息系统专业08级《排序效率比较》专业：班级：姓名：指导教师：二OO九年八月二十七日石河子大学信息科学与技术学院信息管理与信息系统专业08级目录1.课程设计目的.......................................................................................12.课程设计题目描述和要求....................................................................13.课程设计报告内容...............................................................................14.课程设计总结.......................................................................................7参考书目.................................................................................................8源代码.....................................................................................................9石河子大学信息科学与技术学院信息管理与信息系统专业08级-1-课程设计的内容如下：1.课程设计目的用C++编一程序对排序方法进行比较，用选定的排序方法进行排序，输出每种方法数据比较或交换的次数，最后输出所花费的时间。2.课程设计题目描述和要求[问题描述]对排序法进行比较，比较其运行效率。[基本要求]至少对三种排序方法进行比较，比较方法是生成一组数据(≥400)。（1）用三种方法对四百个数字进行排序；（2）用time函数分别测试三种排序方法就同一组数据排序所消耗的时间；（3）分别测试三种排序方法就同一组数据排序所交换的次数；3.课程设计报告内容3.1结构图（1）功能结构图石河子大学信息科学与技术学院信息管理与信息系统专业08级-2-（2）数据流程图3.2主要函数功能描述（1）Time()排序效率比较测试选择排序所需时间测试冒泡排序所需时间测试插入排序所需时间主函数main测试选择排序测试冒泡排序测试插入排序调用Time函数调用选择排序函数调用Time函数调用冒泡排序函数调用Time函数调用插入排序函数开始石河子大学信息科学与技术学院信息管理与信息系统专业08级-3-{longbeginTime=clock();//获得开始时间，单位为毫秒******************//程序longendTime=clock();//获得结束时间coutbeginTime:beginTimeendlendTime:endTimeendlendTime-beginTime:endTime-beginTimeendl;}作用：测试任意程序运行所用时间，单位为毫秒。（2）voidT1(int*a)作用：测试选择排序所用时间，先调用Time函数记录开始时间，再调用选择排序函数（比较相邻两个数，大的放在后面，然后最大的数沉底，最后从小到大排列），最后记录交换次数和结束时间；（3）voidT2(int*a)作用：测试选择冒泡所用时间，先调用Time函数记录开始时间，再调用冒泡排序函数（比较相邻两个数，小的放在前面，然后最小的数上浮，最后从小到大排列），最后记录交换次数和结束时间；（4）voidT1(int*a)作用：测试插入排序所用时间，先调用Time函数记录开始时间，再调用插入排序函数（先两个数比较大小，大的在后，然后插入一个数分别与左右比较，小数在前，大数在后，最后从小到大排列，最后从小到大排列），最后记录交换次数和结束时间；；3.3测试结果与分析（1）增加模块石河子大学信息科学与技术学院信息管理与信息系统专业08级-4-石河子大学信息科学与技术学院信息管理与信息系统专业08级-5-石河子大学信息科学与技术学院信息管理与信息系统专业08级-6-（2）分析：用实际数据分别说明三种排序的运行效率石河子大学信息科学与技术学院信息管理与信息系统专业08级-7-4.课程设计总结通过一年对数据结构程序设计的学习，我已经能够进行简单的程序设计，这次课程设计对自己所学知识起到了检测和提高的作用。虽然已经完成，但是还有很多不足之处，程序的设计中遇到不少问题，例如如何进行排序算法的边写，Time函数的应用等等，通过和同学的讨论与交流，解决了不少问题。程序的调试过程中也有不少问题，例如标点、菜单的界面设计等。课程设计完成后，感觉上最大的收获就是在设计之前要有一个清晰的思路和完整的设计提纲，对各功能函数的作用做详细考虑。细心在这次课程设计中起到很关键的作用，一个标点、一个字母、一个符号都可能导致程序的不能运行，因此要有耐心认真完成。当然知识是不可缺少的，只有对这学期所学得知识能够真正掌握并能加以运用，才能顺利完成这次的课程设计。如果把磁盘文件学的精通一点，就可以用磁盘文件读取数据。石河子大学信息科学与技术学院信息管理与信息系统专业08级-8-参考书目：谭浩强，《C++程序设计》，北京，清华大学出版社，2006年.石河子大学信息科学与技术学院信息管理与信息系统专业08级-9-源代码：#includeiostream//头文件#includetime.husingnamespacestd;intt1,t2,t3;voidT1(int*a){longbeginTime=clock();//获得开始时间，单位为毫秒inti,j,k,t,n1=0;for(i=0;i399;i++){k=i;for(j=i+1;j400;j++)if(a[j]a[k]){k=j;t=a[i];a[i]=a[k];a[k]=t;n1++;}//选择排序}for(i=0;i400;i++)couta[i]'\t';longendTime=clock();//获得结束时间coutbeginTime:beginTimeendl;coutendTime:endTimeendl;coutendTime-beginTime:endTime-beginTimeendl;coutn1=n1endl;//n1为选择排序交换的次数t1=endTime-beginTime;coutt1=t1endl;//t1为选择排序所用时间}voidT2(int*a){longbeginTime=clock();//获得开始时间，单位为毫秒inti,j,k,t,n2=0;for(i=0;i399;i++){k=i;for(j=i+1;j400;j++)if(a[j]a[k])k=j;t=a[i];石河子大学信息科学与技术学院信息管理与信息系统专业08级-10-a[i]=a[k];a[k]=t;{n2++;}}//起泡排序for(i=0;i400;i++)couta[i]'\t';longendTime=clock();//获得结束时间coutbeginTime:beginTimeendl;coutendTime:endTimeendl;coutendTime-beginTime:endTime-beginTimeendl;coutn2=n2endl;//n2为起泡排序交换的次数t2=endTime-beginTime;coutt2=t2endl;//t2为起泡排序所用时间}voidT3(int*a){longbeginTime=clock();//获得开始时间，单位为毫秒inti,j,n=400,n3=0,b;for(i=2;i=400;i++){b=a[i];for(j=i-1;ba[j];j--)a[j+1]=a[j];a[j+1]=b;{n3++;}//插入排序}for(i=1;i=n;i++)couta[i]'\t';coutendl;longendTime=clock();//获得结束时间coutbeginTime:beginTimeendl;coutendTime:endTimeendl;coutendTime-beginTime:endTime-beginTimeendl;coutn3=n3endl;//n3为插入排序交换的次数t3=endTime-beginTime;coutt3=t3endl;//t2为插入排序所用时间}voidmain(){inta[401];for(inti=0;i401;i++)a[i]=(401-i);T1(a);//分别调用函数T2(a);T3(a);}