排序算法设计和比较

1、实验五排序算法设计和比较-、【实验内容与要求】问题描述：利用直接插入排序、冒泡排序、快速排序对数列进行排序。基本要求：（1）能随机生成30个值为0至到100的数。（2）用于排序的输入数列可以是要求（1）中随机生成的，也可以是键盘输入。（3）输出结果为利用三种方法排序后的结果，并能显示三种算法时间、空间性能参数值。【测试数据】由随机自行生成若干个数，进行排序。二、程序设计的基本思想，原理和算法描述:（包括程序的结构，数据结构，输入/输出设计，符号名说明等）1）符号说明:ml,m2,a,b,ctempnm3代表三种排序法的循环次数分别用来存储三次排序的数据中间变量参与排序的数字个数maopao（a

2、，n）zhicha（b，n）quick（a,h,l）hl冒泡程序排序直接插入排序快速排序法分块排序的上限分块排序的下限2）程序说明（结构，输入输出）这个程序整个流程比较自然，一脉相传，即先输入要排序的个数，然后选择要输入的方式，将产生的数传到数组中，然后依次地用冒泡子程序，直接插入的程序，快速排序的方法，依次排序，并将排好的数输出，以及算法的时间复杂率。3）程序流程图START初始化函数，根据提示语句，输入要参加数字个数n同时将得到的数同步传到数组b,c;为下面各种排序做准备调用冒泡排序的子;大到小，并计算循:程序，传输参数，排序从环的次数，将结果输出1F调用直接插入子程序重复上面操作，输出结

3、果。1r调用快速排序子程丿序,重复操作，输出结果。三、源程序及注释:#includestdio.h#includetime.hintm1=0;全局变量定义冒泡法循环的次数intm2=0;全局变量定义直接插入法循环的次数intm3=0;全局变量定义快速法循环的次数intsuiji(inta,intn);随机生成目的数函数intij,temp;srand(unsigned)time(NULL);srand播下一个种子for(i=0;ivn;i+)ai=rand()%100;rand得到的数为0到100，依次传到a中printf(%d,ai);jianpan(inta,intn)键盘输入目的数函数i

4、ntij,k,l;for(i=0;ivn;i+)依次输入目的数printf(input%dnumber:,i+1);scanf(%d,&ai);maopao(inta,intn)冒泡法排序程序intij,temp;for(i=0;ivn-1;i+)for(j=1jv(n-i);j+);具体的排序过程if(ajaj-1)temp=aj;aj=aj-1;aj-1=temp;m1+;计算循环次数printf(Bubbathesortednember:n);for(i=0;ivn;i+)printf(%d,ai);将排好的数依次显示if(i+1)%5=0)printf(n);每输出5个数换行print

5、f(timeeffective:%d,m1);输出冒泡法的时间效率mlzhicha(intb,intn)直接插入排序子程序intij,temp;printf(nDirect:n);for(i=1;ivn;i+)temp=bi;for(j=i;j0&tempbj-1;-j)具体排序过程bj=bj-1;m2+;bj=temp;for(i=0;ivn;i+)printf(%d,bi);将排好的数显示出来if(i+1)%5=0)printf(n);printf(timeeffective:%dn,m2);输出时间效率quick(intc,intl,inth)快速排序法inttemp;intij,k;i

6、=lj=h;if(lh)temp=cl;whiie(ij)whiie(ij&cjvtemp);具体排序过程j-;m3+;if(ij)ci+=cj;whiie(itemp)i+;m3+;if(ij)cj-=ci;ci=temp;quick(cj,i-1);递归调用排序quick(cj+1,h);递归调用排序main()intij,k,n;inta100,b100,c1OO;定义三个数组来存放三种方法的数字cirscr();清屏函数printf(inputnumber:);scanf(%d,&n);输入要参与排序的数目printf(chooseinputway(1.suiji2.jianpan):

7、);scanf(%d,&k);选择输入的方式if(k=1)k=1则调用随机函数调用suiji(a,n);if(k=2)k=2则调用键盘输入函数jianpan(a,n);for(i=0;ivn;i+)bi=ai;ci=ai;maopao(a,n);调用冒泡法程序zhicha(b,n);调用直接插入排序printf(Quicksort:n);quick(c,0,n-1);调用快速排序法for(i=0;ivn;i+)printf(%d,ci);if(i+1)%5=0)printf(n);printf(timeeffective:%d,m3);getchar();getchar();A四、运行输出结果

8、：e9844sa7642O7bO2b2587eu9:?4l?iy8da4e733w17536erut3o8937iU5s7541tpcnC9242ei7h7642f1tfe733775367018937187541:7eu9242i97642t:7cter:9844fo97642fs7Cteke2587ec2P9742mi9iiu3353629374541:eu2421642tce844f642fe587e742mrl4-J48J6a2P914:24459:-恥6334378五、调试和运行程序过程中产生的问题及采取的措施：在写程序的过程思路比较清晰，遇到的困难主要是编程软件的不兼容，或是某些c语言规则在一些软件上为非法的，早先我用的一直用地是devC+,但是在用随机生成数子函数,一直提示有错误，改正不了，最后只好用最原始的turboC问题解决了，发现最好用的还是tc啊，以后只用突出（我电脑一直装不了vc+,不知道怎么回事），在具体编程中需要考虑的是函数形参和实参的格式，一定要一致。六、对算法的程序的讨论、分析，改进设想，其它经验教训:这次程序中主要用三种排序方法：a。冒泡排序b直接插入排序c。快速排序。其中冒泡排序的时间复杂度：O(n2)空间复杂度：0(1)直接插入排序时间复杂度：0(说)空间复杂度：0(1)序法最差