《算法设计实验报告一》由会员分享，可在线阅读，更多相关《算法设计实验报告一（6页珍藏版）》请在装配图网上搜索。
1、计算机算法设计与分析实 验 报 告实验名称：排序算法效率比较实验地点：所使用的开发工具及环境：一、 实验目的：比较至少4种排序算法的执行效率。已学过的算法：起泡排序、选择排序、插入排序、shell排序,归并排序、快速排序等。二、实验内容：1、从中选择至少4中排序算法,写成独立的函数进行调用。2、参与排序的数据不少于10000个,要求用数据文件存储随机产生的数据。3、要求在main函数中调用以上函数,并输出各排序算法所用时间。三、 基本思想、原理和算法描述：本次实验要求写出四种算法,来比较它们运行的时间。冒泡排序：总的时间复杂度为O.基本思想：首先将第一个记录的关键字和第二个记录的关键字进行比较
2、,若为逆序,则将两个记录交换,然后比较第二个记录和第三个记录的关键字。依此类推,直到第n-1和第n个的关键字进行比较为止。算法描述：void BubbleSort /冒泡排序int i,j,temp;for0;j-fori=0;iifri+1temp=ri;ri=ri+1;ri+1=temp; 简单选择排序：总的时间复杂度为O基本思想：通过n-i次关键字的比较,从n-i+1个记录中选取出关键字最小的记录并和第i个记录交换。算法描述：void SelectSort /简单选择排序int i,j,k;int x; for i=1;ik=i;forj=i+1;jifrjk=j;ifx= ri;ri=
3、rk;rk=x;插入排序：总的时间复杂度为：O算法描述：void InsertSort /插入排序int i,j;for i=0;ir0=ri;j=i-1;whiler0rj+1=rj;j=j-1;rj+1=r0;快速排序：总的时间复杂度为O基本思想：通过一趟排序将待排记录分割成独立的两部分,其中一部分的关键字均比另一部分的关键字小,则可分别对这两部分的记录继续进行排序,直到整个序列有序。算法描述：void QuickSort/快速排序iflowint high = Partition; QuickSort;QuickSort;四、 源程序清单：#include#include#include
4、#include#define MAX 10000void BubbleSort /冒泡排序int i,j,temp;for0;j-fori=0;iifri+1temp=ri;ri=ri+1;ri+1=temp; void SelectSort /简单选择排序int i,j,k;int x;for i=1;ik=i;forj=i+1;jifrjk=j;ifx= ri;ri=rk;rk=x; void InsertSort /插入排序int i,j;for i=0;ir0=ri;j=i-1;whiler0rj+1=rj;j=j-1;rj+1=r0;int Partitionint i,j,x,t
5、;x = Ahigh;i = low-1;for j = low;jifAj i+;t = Aj;Aj = Ai;Ai = t; Ahigh = Ai+1;Ai+1 = x; return i+1;void QuickSort/快速排序iflowint high = Partition; QuickSort;QuickSort;void mainlong iStart,iStop,runtime;int numMAX, aMAX;int i,j;iStart=GetTickCount;srandtime;fori=0;inumi=rand;iStop=GetTickCount;runtime=
6、iStop-iStart;printf;printf;fori=0;iai=numi;iStart=GetTickCount;BubbleSort;iStop=GetTickCount;runtime=iStop-iStart;printf;fori=0;iai=numi;iStart=GetTickCount;SelectSort;iStop=GetTickCount;runtime=iStop-iStart;printf;fori=0;iai=numi;iStart=GetTickCount;InsertSort;iStop=GetTickCount;runtime=iStop-iStar
7、t;printf;fori=0;iai=numi;iStart=GetTickCount;QuickSort;iStop=GetTickCount;runtime=iStop-iStart;printf; 五、 程序运行结果包括上机调试的情况、调试所遇到的问题是如何解决的,并对调试过程中的问题进行分析,对执行结果进行分析。：最主要的就是怎样产生不同的随机数,并且还要记录下排序前后的时间。最后就是在快速排序的时候有点问题。不过经过查资料和多次调试,问题基本得到解决六、实验总结：在本次实验中要求在六种算法中选择四种出来,然后进行时间的比较。在实验中前前后后还是遇到了不少问题。最先是怎样产生随机数,然后是在网上查了一个函数可以进行时间的记录,可以快速的求出整个算法的运行时间。其余的就是一点小问题,经过查找资料已经得到解决。本次实验的收获是知道了几种算法的效率的快慢。 指导教师签名： 2014 年 月 日6 / 6
算法设计实验报告一
