南华大学计算机科学与技术学院 实验报告南华大学计算机科学与技术学院实 验 报 告 （2011年度 第 1 学期 ）课程名称算法设计与分析实验名称比较冒泡排序与快速排序的性能姓名彭赐缘学号20094360131专业网络工程班级091地点8教实验室教师刘立1.掌握冒泡排序方法，快速排序方法，并掌握用高级语言实现排序算法的方法；2.深刻理解冒泡排序和快速排序的定义和特点，并能加以灵活应用；3.两种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂性和稳定性的分析方法。时间，效率，性能分析和比较得出优劣，由此了解到在不同条件下冒泡法与快速排序算法的选择（软件硬件及条件）硬件：台式组装电脑，软件：windows ， （1）算法流程图冒泡排序： 快速排序： （2）程序代码#includeiostream.h#includestdio.h#includestdlib.h#includetime.h long Bubblesort(long R,long n) int flag=1; long BC=0; for(long i=1;i=i;j-) if(RjRj-1) long t=Rj; Rj=Rj-1; Rj-1=t; flag=1; BC+; return BC;long Bubblesortcompare(long R,long n) int flag=1; long BC=0; for(long i=1;i=i;j-) if(Rj=Rj-1) BC+; return BC;long quicksort(long R,long left,long right) static long QC=0; long i=left,j=right; long temp=Ri; while(itemp)&(ji) QC+; j=j-1; if(ji) Ri=Rj; i=i+1; QC+; while(Rii) QC+; i=i+1; if(ij) Rj=Ri; j=j-1; QC+; /二次划分得到基准值的正确位置 Ri=temp; if(lefti-1) quicksort(R,left,i-1); /递归调用左子区间 if(i+1right) quicksort(R,i+1,right); /递归调用右子区间 return QC;long quicksortcompare(long R,long left,long right) static long QC=0;long i=left,j=right; long temp=Ri; while(itemp)&(ji) QC+; j=j-1; if(ji) Ri=Rj; i=i+1; while(Rii) QC+; i=i+1; if(ij) Rj=Ri; j=j-1; /二次划分得到基准值的正确位置 Ri=temp; if(lefti-1) quicksort(R,left,i-1); /递归调用左子区间 if(i+1right) quicksort(R,i+1,right); /递归调用右子区间 return QC;void operate1(long a,long n) long*R=new longn; time_t start,end; double dif; long degree,compare; int i; for(i=0;in;i+) Ri=ai; time(&start); degree=Bubblesort(R,n); time(&end); dif=difftime(end,start); cout冒泡排序交换次数：tdegreen; for(i=0;in;i+) Ri=ai; compare=Bubblesortcompare(R,n); cout冒泡排序比较次数：tcomparen; void operate2(long a,long n) long*R=new longn; time_t start,end; double dif; long degree,compare; int i; for(i=0;in;i+) Ri=ai; time(&start); degree=quicksort(R,0,n-1); time(&end); dif=difftime(end,start); cout快速排序交换次数：tdegreen; for(i=0;in;i+) Ri=ai; compare=quicksortcompare(R,0,n-1); cout快速排序比较次数：tcomparen; coutn; void main(int argc, char* argv) clock_t start_0, finish,start_1,finish_1; double duration; long n; char check;coutn* 排序算法比较 *endl; cout=endl; while(1) coutn; coutendl; long*a=new longn; srand(unsigned long)time(NULL); for(long i=0;in;i+) ai=rand()%n; start_0 = clock(); operate1(a,n);finish = clock(); coutn; duration = (double)(finish - start_0) / CLOCKS_PER_SEC; cout程序运行花费时间: duration秒nnn;start_1 = clock(); operate2(a,n);finish_1 = clock(); coutn; duration = (double)(finish_1 - start_1) / CLOCKS_PER_SEC; cout程序运行花费时间: duration秒nnn;coutcheck; if(check=y|check=Y) continue; if(check=n|check=N) break; （1）实验结果截图（2）实验结果统计表方法规模N50300100020003000400050007000100003000050000100000冒泡排序交换次数6282168224990499894822424283970061629613712143335249373042241483846243233721798170008比较次数185266532749404299794867409281196806118793637366398357493230467413338418742983721093187304运行花费时间(ms)001531781722548410008953