三种排序及其比较报告

1、三种排序及其比较实验报告(1) 、实验题目通过快速排序，折半排序，希尔排序三种方法进行排序数据，并统计每一种排序在过程中 对整数的比较次数和移动次数，并输出结果。(2) 实验项目组成该程序由主函数 main()和子函数 quicksort ()， shellsort ()， binSort()组成。(3 )实验项目的程序结构：结束(4 )函数的功能描述quicksort nt a,i nt l,i nt r,i nt *u1,i nt *v1)快速排序算法shellsort(i nt a,i nt n) shellbinSort(int a,int n) 2(5)实验数据与实验结果 测试数据：

2、在main ()排序算法分插入排序算法函数里面可以事先给定要排序的整数，这里给的是11,3,28,52,46,32,66,88 等 8 个非顺序数据实验结果见下图：(6)算法描述:#i nclude "stdio.h"快速排序*/#in clude "coni o.h"quicksort(int a,int l,int r,int *u1,int *v1)/*int i,j,temp,k=O,u,v;i=l; j=r;temp=ai;if(l>=r) return;while(i!=j)while(aj>=temp&&i<

3、;j) j-;*u1=*u1+1;if(i<j) ai=aj; *v 1=*v1+1; i+; while(ai<temp&&<j) i+;*u1=*u1+1;if(i<j) aj=ai;*v 1=*v1+1;j-;ai=temp;quicksort(a,l,i-1,u1,v1);quicksort(a,i+1,r,u1,v1);void shellsort(int a,int n) /*希尔排序 */int d,i,j,x,y , temp,v;x=0; y=0 ;for(d=n/2;d>0;d=d/2) for(i=d;i<n;i+)te

4、mp=ai;j=i-d;while(j>=0 && temp<aj)aj+d=aj;y+;j=j-d;x+ ;aj+d=temp;printf("n the number of compare x=%d ",x); printf("n the number of move y=%dn ",y);for(v=0;v<=7;v+) printf("%5d",av);printf("n");void binSort(int a,int n) /* 折半插入排序 */ int i,j,lo

5、w,hight,mid,m=0,k =0 ;int v;int temp;for(i=1;i<n;i+)temp=ai;low=0; hight=i-1;while(low<=hight)mid=(low+hight)/2;if (temp<amid)hight=mid-1;else low=mid+1;m+;for(j=i-1;j>=low;j-)aj+1=aj; k+;if(low!=i) k+;alow=temp;printf("the number of compare m=%dn",m);printf("the number of

6、 move k=%dn",k);for(v=0;v<=7;v+) printf("%8d",av); void main()int i,j,k,v;int *u1=2,*v1 =0;int a8=11,3,28,52,46,32,66,88;int b8=11,3,28,52,46,32,66,88;int c8=11,3,28,52,46,32,66,88;printf("binSortn");printf("n");binSort(a,8);printf("n");printf("shellSortn");shellsort(b,8);printf("n");printf("quickSortn");printf("n");quicksort(c,0,8,u1,v1);for(v=0;v<=7;v+) printf("%5d",av);printf("