内部排序

数据结构实习报告题目：内部排序算法比较班级：1403011姓名：刘瑗学号：14030110011一、需求分析1.问题描述：在课本中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶数或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。2.基本要求：（1）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序。（2）待排序表的表长不小于100；其中的数据要用伪随机数函数产生；比较的指标为有关键字参加的比较次数和关键字的移动次数（其中关键字交换计为3次移动）。（3）最后要对结果做出简单分析，包括对各组数据得出结果波动大小的解释。3.测试数据：由随机数产生函数生成。二、概要设计1.本程序的主要模块有主程序模块和基本操作模块（1）．主程序模块Intmian（）{打印表头；While(1){接受命令；生成随机数；执行命令；}退出；}（2）.基本操作模块随机数排序：至少重复执行5次取平均三、详细设计#includestdio.h#includestdlib.h#includetime.h#defineMAXNUM1000//定义随机数最大为1000#defineN150//定义数组最大为150#definet3//定义希尔排序次数intqmt;//快速排序的移动次数intqct;//快速排序的比较次数intd[t]={4,3,1};//定义希尔排序比较量voidoutput(intn,inta[],intct,intmt)//内部排序中调用的输出函数{inti;printf(\n排序结果:);for(i=0;in;i++)printf(%d,a[i]);//输出各排序完成的数组printf(\n\n比较次数:%d移动次数:%d\n,ct,mt);}voidbubble_sort(intn,intA[])//冒泡排序{intmt=0;//移动次数mt=movetimeintct=0;//比较次数ct=cmdtimeinti,j,temp;inta[N];for(i=0;in;i++)a[i]=A[i];for(i=0;in-1;i++){for(j=0;jn-1-i;j++,ct++){if(a[j+1]a[j])//前后比较temp=a[j],a[j]=a[j+1],a[j+1]=temp,mt+=3;//关键字交换计为3次移动}}printf(\n冒泡排序);output(n,a,ct,mt);}voidselection_sort(intn,intA[])//选择排序{intmt=0;//移动次数movetimeintct=0;//比较次数cmdtimeinti,j,temp,k;inta[N];for(i=0;in;i++)a[i]=A[i];for(i=0;in-1;i++){k=i;for(j=i+1;jn;j++,ct++)if(a[k]a[j])k=j;temp=a[i],a[i]=a[k],a[k]=temp,mt+=3;//关键字交换计为3次移动}printf(\n选择排序);output(n,a,ct,mt);}voidquick(inta[],intlow,intup)//快速排序递归算法{inti,j,temp;if(lowup){i=low;j=up;temp=a[low],qmt++;while(i!=j){qct++;while(ij&&a[j]temp)j--,qct++;if(ij)a[i++]=a[j],qct++;qmt++;while(ij&&a[i]=temp)i++,qct++;if(ij)a[j--]=a[i],qct++,qmt++;}a[i]=temp,qmt++;quick(a,low,j-1);quick(a,i+1,up);}}voidquick_sort(intn,intA[])//快速排序(通过调用快速排序递归算法完成){inti;inta[N];qct=0;qmt=0;for(i=0;in;i++)a[i]=A[i];quick(a,0,n-1);//调用快速排序递归算法printf(\n快速排序);output(n,a,qct,qmt);}voidinsertion_sort(intn,intA[])//插入排序{intmt=0;//移动次数movetimeintct=0;//比较次数cmdtimeinti,j,temp;inta[N];for(i=0;in;i++)a[i]=A[i];for(i=1;in;i++){temp=a[i],mt++;for(j=i-1;j=0&&tempa[j];j--,ct++)a[j+1]=a[j],mt++;a[j+1]=temp,mt++;}printf(\n插入排序);output(n,a,ct,mt);}voidshell_sort(intn,intA[])//希尔排序{intmt=0;//移动次数movetimeintct=0;//比较次数cmdtimeinti,j,k,h,y;inta[N];for(i=0;in;i++)a[i]=A[i];for(i=0;it;i++){h=d[i];for(j=h;jn;j++){y=a[j],mt++;for(k=j-h,ct++,mt++;k=0&&ya[k];k-=h)a[k+h]=a[k];a[k+h]=y;}}printf(\n希尔排序);output(n,a,ct,mt);}intmain(){intn=N;inti,j=0,choice=0;intA[N];//B[N],C[N],D[N],E[N],srand((unsigned)time(NULL));printf(\n*******************内部排序算法比较*******************);while(choice!=7){printf(\n菜单:);printf(\n1.生成随机数序列);printf(\n2.冒泡排序);printf(\n3.选择排序);printf(\n4.快速排序);printf(\n5.插入排序);printf(\n6.希尔排序);printf(\n7.退出\n请选择:);scanf(%d,&choice);switch(choice){case1:j++;printf(\n*******************第%d组随机数*******************\n数组序列：,j);for(i=0;iN;i++){A[i]=rand()%MAXNUM;}for(i=0;iN;i++){printf(%d,A[i]);}printf(\n\n);break;case2:bubble_sort(n,A);//冒泡排序break;case3:selection_sort(n,A);//选择排序break;case4:quick_sort(n,A);//快速排序break;case5:insertion_sort(n,A);//插入排序break;case6:shell_sort(n,A);//希尔排序break;case7:printf(\t\t\t再见!\n);break;default:printf(输入错误，请重新选择\n);break;}}return0;}四、用户手册1.本程序的运行环绕为WINDOWS环境下的仿真DOS系统，执行文件compare.exe。2.进入演示程序后即显示文本方式的用户界面。3.根据提示输入相应的命令。4.接受命令后即执行相应运算和显示相应结果。六、测试结果理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示：排序方法平均情况最好情况最坏情况辅助空间直接插入排序O(n2)O(n)O(n2)O(1)起泡排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)~O(n)简单选择排序O(n2)O(n2)O(n2)O(1)希尔排序O（n1..3）O（1）从结果中可看出：对于一般的排序，比较次数多，而交换次数相对较少；而快速排序比较次数和交换次数都较少，两者相差不如前者大。其中冒泡排序比较和交换次数都很大。正序、逆序等典型数据对结果影响较大。七、附录源程序文件名清单内部排序.c//程序代码文件