数据结构 排序算法设计和比较

1、数据结构实验报告五专业： 自动化 班级： 0710 学号： 0901071002 姓名： 日期： 2009. 12.15 程序：排序算法设计比较 实验五排序算法设计和比较【实验内容与要求】问题描述：利用直接插入排序、冒泡排序、快速排序对数列进行排序。基本要求：（1） 能随机生成30个值为0到100的数。（2） 用于排序的输入数列可以是要求（1）中随机生成的，也可以是键盘输入。（3） 输出结果为利用三种方法排序后的结果，并能显示三种算法时间、空间性能参数值。【测试数据】由随机自行生成若干个数，进行排序。二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明

2、等）1） 符号说明： m1，m2，m3 代表三种排序法的循环次数 a,b,c 分别用来存储三次排序的数据 temp 中间变量 n 参与排序的数字个数 maopao（a，n） 冒泡程序排序 zhicha（b，n） 直接插入排序 quick(a,h,l) 快速排序法 h 分块排序的上限 l 分块排序的下限2） 程序说明（结构，输入输出）这个程序整个流程比较自然，一脉相传，即先输入要排序的个数，然后选择要输入的方式，将产生的数传到数组中，然后依次地用冒泡子程序，直接插入的程序，快速排序的方法，依次排序，并将排好的数输出，以及算法的时间复杂率。三、源程序及注释：#include"stdio.

3、h"#include"time.h"int 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;i<n;i+) ai=rand()%100; rand得到的数为0到100，依次传到a中 printf(" %d",ai); jianpan(int a,int n) 键

4、盘输入目的数函数 int i,j,k,l; for(i=0;i<n;i+) 依次输入目的数 printf("input %dnumber:",i+1); scanf("%d",&ai); maopao(int a,int n) 冒泡法排序程序 int i,j,temp; for(i=0;i<n-1;i+) for(j=1;j<(n-i);j+) ；具体的排序过程 if(aj>aj-1) temp=aj; aj=aj-1; aj-1=temp; m1+; 计算循环次数 printf(" Bubba the sort

5、ed nember:n"); for(i=0;i<n;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;i<n;i+) temp=bi; for(j=i;j>0&

6、&temp>bj-1;-j) 具体排序过程bj=bj-1;m2+;bj=temp; for(i=0;i<n;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(l<h) temp=cl; while(i<j) while(i<j&a

7、mp;&cj<temp)；具体排序过程 j-; m3+; if(i<j) ci+=cj; while(i<j&&ci>temp) i+; m3+; if(i<j) 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",&a

8、mp;n); 输入要参与排序的数目 "); scanf("%d",&k); 选择输入的方式 if(k=1) k=1 则调用随机函数调用 suiji(a,n); if(k=2) k=2 则调用键盘输入函数 jianpan(a,n); for(i=0;i<n;i+) bi=ai;ci=ai; maopao(a,n); 调用冒泡法程序 zhicha(b,n); 调用直接插入排序 printf("Quick sort:n"); quick(c,0,n-1); 调用快速排序法 for(i=0;i<n;i+) printf("

9、 %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)序法 最差时间分析平均时间