排序算法设计和比较.doc

实验五排序算法设计和比较一、【实验内容与要求】问题描述：利用直接插入排序、冒泡排序、快速排序对数列进行排序。基本要求：（1） 能随机生成30个值为0到100的数。（2） 用于排序的输入数列可以是要求（1）中随机生成的，也可以是键盘输入。（3） 输出结果为利用三种方法排序后的结果，并能显示三种算法时间、空间性能参数值。【测试数据】由随机自行生成若干个数，进行排序。二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）1） 符号说明： m1，m2，m3 代表三种排序法的循环次数 a,b,c 分别用来存储三次排序的数据 temp 中间变量 n 参与排序的数字个数 maopao（a，n） 冒泡程序排序 zhicha（b，n） 直接插入排序 quick(a,h,l) 快速排序法 h 分块排序的上限 l 分块排序的下限2） 程序说明（结构，输入输出）这个程序整个流程比较自然，一脉相传，即先输入要排序的个数，然后选择要输入的方式，将产生的数传到数组中，然后依次地用冒泡子程序，直接插入的程序，快速排序的方法，依次排序，并将排好的数输出，以及算法的时间复杂率。K=2K=1 调用随机数函数，由随机产生n个数选择输入方式k？调用键盘输入函数，由键盘输入要比较的数（n个数）START初始化函数，根据提示语句，输入要参加数字个数n同时将得到的数同步传到数组b,c;为下面各种排序做准备调用冒泡排序的子程序，传输参数，排序从大到小，并计算循环的次数，将结果输出调用直接插入子程序重复上面操作，输出结果。调用快速排序子程序，重复操作，输出结果。END3）程序流程图三、源程序及注释：#includestdio.h#includetime.hint m1=0;全局变量定义冒泡法循环的次数int m2=0; 全局变量定义直接插入法循环的次数int m3=0; 全局变量定义快速法循环的次数 int suiji(int a,int n) ；随机生成目的数函数 int i,j,temp; srand(unsigned)time(NULL); srand播下一个种子 for(i=0;in;i+) ai=rand()%100; rand得到的数为0到100，依次传到a中 printf( %d,ai); jianpan(int a,int n) 键盘输入目的数函数 int i,j,k,l; for(i=0;in;i+) 依次输入目的数 printf(input %dnumber:,i+1); scanf(%d,&ai); maopao(int a,int n) 冒泡法排序程序 int i,j,temp; for(i=0;in-1;i+) for(j=1;jaj-1) temp=aj; aj=aj-1; aj-1=temp; m1+; 计算循环次数 printf( Bubba the sorted nember:n); for(i=0;in;i+) printf( %d,ai); 将排好的数依次显示 if(i+1)%5=0) printf(n); 每输出5个数换行 printf(time effective:%d,m1); 输出冒泡法的时间效率m1 zhicha(int b,int n) 直接插入排序子程序 int i,j,temp; printf(nDirect :n); for(i=1;i0&tempbj-1;-j) 具体排序过程bj=bj-1;m2+;bj=temp; for(i=0;in;i+) printf( %d,bi); 将排好的数显示出来 if(i+1)%5=0) printf(n); printf(time effective:%dn,m2);输出时间效率 quick(int c,int l,int h) 快速排序法 int temp; int i,j,k; i=l;j=h; if(lh) temp=cl; while(ij) while(ij&cjtemp)；具体排序过程 j-; m3+; if(ij) ci+=cj; while(itemp) i+; m3+; if(ij) cj-=ci; ci=temp; quick(c,l,i-1);递归调用排序 quick(c,i+1,h);递归调用排序 main() int i,j,k,n; int a100,b100,c100; 定义三个数组来存放三种方法的数字 clrscr(); 清屏函数 printf(input number:); scanf(%d,&n); 输入要参与排序的数目printf(choose input way(1.suiji2.jianpan): ); scanf(%d,&k); 选择输入的方式 if(k=1) k=1 则调用随机函数调用 suiji(a,n); if(k=2) k=2 则调用键盘输入函数 jianpan(a,n); for(i=0;in;i+) bi=ai;ci=ai; maopao(a,n); 调用冒泡法程序 zhicha(b,n); 调用直接插入排序 printf(Quick sort:n); quick(c,0,n-1); 调用快速排序法 for(i=0;in;i+) printf( %d,ci); if(i+1)%5=0) printf(n); printf(time effective:%d,m3); getchar(); getchar();四、运行输出结果：五、调试和运行程序过程中产生的问题及采取的措施： 在写程序的过程思路比较清晰，遇到的困难主要是编程软件的不兼容，或是某些c语言规则在一些软件上为非法的，早先我用的一直用地是devC+，但是在用随机生成数子函数，一直提示有错误，改正不了，最后只好用最原始的turbo C问题解决了，发现最好用的还是tc啊，以后只用突出（我电脑一直装不了vc+，不知道怎么回事），在具体编程中需要考虑的是函数形参和实参的格式，一定要一致。六、对算法的程序的讨论、分析，改进设想，其它经验教训： 这次程序中主要用三种排序方法：a。冒泡排序b直接插入排序c。快速排序。其中冒泡排序的时间复杂度：O(n2) 空间复杂度：O(1)直接插入排序时间复杂度：O(n2) 空间复杂度：O(1)序法 最差时间分析平均时间复杂度 稳定度 空间复杂