实验六

实验六、内部排序算法效率比较平台的设计与实现。【实验学时】4学时【实验目的】掌握多种排序方法的基本思想，如直接插入、起泡、简单选择、快速、堆、希尔排序等排序方法，并能够用高级语言实现。【问题描述】各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受【基本要求】（1）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。（2）待排序的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。（3）最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。【测试数据】由随机数产生器生成。【实现提示】主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如，正序、逆序和不同程度的乱序。注意采用分块调试的方法。【选作内容】（1）增加折半插入排序、二路插入排序、归并排序、基数排序等。（2）对不同的输入表长作实验，观察检查两个指标相对于表长的变化关系。还可以对稳定性作验证。代码：#includestdio.h#includestdlib.h#includetime.h#defineMAXNUM1000//定义随机数最大为1000#defineN100//定义数组最大为100#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;//移动次数intct=0;//比较次数inti,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;//移动次数intct=0;//比较次数inti,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;//移动次数intct=0;//比较次数inti,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;//移动次数intct=0;//比较次数inti,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;intA[N];srand((unsigned)time(NULL));while(choice!=0){printf(\n菜单:);printf(\n1.生成随机数序列);printf(\n2.冒泡排序);printf(\n3.插入排序);printf(\n4.选择排序);printf(\n5.快速排序);printf(\n6.希尔排序);printf(\n0.退出\n);printf(请选择要实现的功能：);scanf(%d,&choice);switch(choice){case1:j++;printf(\n*******************第%d组随机数*******************\n数组序列：\n,j);for(i=0;iN;i++){A[i]=rand()%MAXNUM;}for(i=0;iN;i++){printf(%d,A[i]);}printf(\n);break;case2:bubble_sort(n,A);//冒泡排序break;case3:insertion_sort(n,A);//插入排序break;case4:selection_sort(n,A);//选择排序break;case5:quick_sort(n,A);//快速排序break;case6:shell_sort(n,A);//希尔排序break;case0:printf(\t\t\t退出程序!\n);break;default:printf(输入错误，请重新选择\n);break;}}return0;}运行截图：1.生成随机数：2.冒泡排序；3.选择排序：4.快速排序5.插入排序