排序算法的实现与对比.docVIP

软件技术基础实验报告 班级： 姓名： 学号： 实验三 排序算法的实现与对比 实验目的： 掌握常用的排序方法，并用c语言实现排序算法； 理解排序的定义和各种排序的特点； 了解排序过程以及依据的原则，并了解各种排序方法的时间复杂度分析，掌握一种计时方法。 实验内容： 分别编写函数进行冒泡排序、简单插入排序、简单选择排序、快速排序 编制一个应用程序，它将随机产生N个整数插入到一个顺序表中，然后分别用上述排序算法对这个顺序表进行排序：记录并显示各种方法的运行时间； 以N=5000和N=50000运行这个程序，对算法运行的时间作比较分析。 实验步骤： 首先，对几种排序的方法进行函数的编译，同时进行主函数调用的编译，完成后，进行程序语法错误的修改，而后，屏蔽其他排序方法，进行第一个排序程序的调试，完成后进行第二个程序的调试，就这样一一进行调试，调试中的，经常遇到最后一个随机数不排序的情况，通过多产生一个随机数，少输出最后一个随机数的方法解决的。完成这个后，就可以往程序中添加计时函数，而后就完成试验了。 程序如下： #include stdlib.h #include conio.h #include dos.h #include stdio.h #include time.h void maopao(int R[],int n); void charu(int R[],int n); void xuanze(int R[],int n); void kuaisu(int R[],int low,int high); int qpass(int R[],int low,int high); void main() { int i,R[100000],n,flag=1; char j; printf(请输入产生的随机数个数n：); scanf(%d,n); for(i=1;i=n+1;i++) R[i]=rand(); for(i=1;i=n;i++) printf( %d ,R[i]); printf( \n); clock_t start,end; double duration; while(flag) { for(i=1;i=n+1;i++) R[i]=rand(); printf(请选择：\n); printf(1.冒泡排序\n); printf(2.简单插入排序\n); printf(3.简单选择排序\n); printf(4.快速排序\n); scanf( %c,j); switch(j) { case1: { start=clock(); maopao(R,n-1); for(i=1;i=n;i++) printf(%d ,R[i]); end=clock(); duration=(double)(end-start); printf(\n); printf(1.冒泡排序的时间： ); printf(%f\n,duration);break; } case2: { start=clock(); charu(R,n-1); for(i=1;i=n;i++) printf(%d ,R[i]); end=clock(); duration=(double)(end-start); printf(\n); printf(2.简单插入排序的时间： ); printf(%f\n,duration);break; } case3: { start=clock(); xuanze(R,n