数据结构 课程设计 排序算法的比较

#include<stdio.h> #include<time.h> #include<stdlib.h> #include<math.h> #include<conio.h> #define MAX 10000 //long Max; long dlta[10000]; int a[MAX+1]; int store[MAX+1]; long int com0=0,mov0; long int com1=0,mov1=0; long int com2=0,mov2=0; long int com3=0,mov3=0; long int com4=0,mov4=0; long int com5=0,mov5=0; double t0,t1,t2,t3,t4,t5; void randomizeNum(int n) {//N表示要产生的随机数的数目 long i; for(i=0;i<n;i++) { a[i]=rand()%20000; store[i]=a[i]; //printf("%5d",store[i]); } printf("\n"); } void restore(long n)//将随机产生的数据存储在数组中 { long i; for(i=0;i<n;i++) { a[i]=store[i]; } } //起泡排序 void bubblesort(int r[],long n) { long i,j; long w; //long int com0=0,mov0=0; for(i=0;i<=n-1;i++) for(j=n-1;j>=i+1;j--) { if(r[j]<r[j-1]) { w=r[j]; r[j]=r[j-1]; r[j-1]=w; mov0=mov0+3; } com0++; } printf("\n起泡排序　比较次数等于　 %ld,移动次数等于　　 %ld\n",com0,mov0); } //直接插入排序 void insertsort(int r[],long n) { long i,j; int watch; //long int com1=0,mov1=0; for(i=1;i<n;i++) { com1++; if(r[i]<r[i-1]) { watch=r[i]; r[i]=r[i-1]; mov1++; for (j=i-2;watch<r[j];--j) { r[j+1]=r[j]; com1++; } r[j+1]=watch; mov1++; } } printf("\ninsertsort compare= %ld,move= %ld\n",com1,mov1); } //简单选择排序 void selectsort(int r[],long n) { int i,j,k,temp; for(i=0;i<n;i++ ) { k=i; for (j=i+1;j<n;j++ ) { com2++; if(r[j]<r[k]) k=j; } temp=r[i]; r[i]=r[k]; r[k]=temp; mov2=mov2+3; } printf("\nSelectSort compare= %ld,move= %ld\n",com2,mov2); } //快速排序 int Partition(int R[],int n, int low,int high) { int pivotkey; pivotkey=R[low]; mov4++; while(low<high) { while( (low<high)&&(R[high]>=pivotkey)) { --high; com4++; } R[low]=R[high]; mov4++; while( (low<high)&&(R[low]<=pivotkey)) { ++low; com4++; } R[high]=R[low]; mov4++; } R[low]=pivotkey; mov4++; return low; } void QSort(int R[],int n, int low,int high) { int pivotloc; if (low<high) { pivotloc=Partition(R,n,low,high); QSort(R,n,low, pivotloc-1); QSort(R,n, pivotloc+1,high); } } void QuickSort(int R[],int n) { QSort(R,n,0,n-1); printf("\nQuickSort compare=%ld,move=%ld\n",com1,mov1); } //堆排序 void Sift(int R[], int s, int m) {//筛选算法 int temp,j; temp=R[s];mov5++; for(j=2*s;j<=m;j*=2) { if ((j<m)&&(R[j]<R[j+1])) { j++; com5++; } com5++; if (temp>=R[j]) break; R[s]=R[j]; mov5++; s=j; } R[s]=temp; mov5++; } void HeapSort(int R[],long n) { int i,temp; for (i=n/2;i>=0;i--)//初始建堆 Sift(R,i,n); for (i=n-1;i>=0;i--) { temp=R[0]; R[0]=R[i]; R[i]=temp; mov4=mov5+3; Sift(R,0,i-1); } printf("\nHeapSort compare=%ld,move=%ld\n",com4,mov4); } //希尔排序 void ShellInsert(long n,long dk ,int r[]) { int watch; long i,j; for(i=dk;i<n;i++) { com3++; if(r[i]<r[i-dk]) { watch=r[i]; mov3++; for(j=i-dk;j>=0 && (watch<r[j]);j-=dk) { r[j+dk]=r[j]; mov3++; } r[j+dk]=watch; mov3++; } } } int CalculateT(long n,long dlta[]) {//用于计算希尔排序中的dlta[k]=2^(t-k+1) long i,t,k,j; long sum=1; for(i=1;i;i++) { sum=sum*2; if(sum>n) break; } t=i-1; for(k=1,j=0;k<=t;k++,j++) { dlta[j]=(long)pow(2,t-k+1)-1; } printf("\n"); return t; } void ShellSort(long n,long dlta[],long t,int r[]) { long k; for(k=0;k<t;k++) ShellInsert(n,dlta[k],r); printf("\nShellSort compare=%ld,move=%ld\n",com3,mov3); } //显示排序结果 void print(int a,int num[]) { int i; int k=0; printf("\n\t\t########################################\n"); printf("\t\t# #\n"); printf("\t\t# 本组数据排序方法比较表 #\n"); printf("\t\t# #\n"); printf("\t\t########################################\n"); printf("\n\t|排序方法 |关键字比较次数 |关键字移动次数 |所需时间\n"); for(i=0;i<a;i++) { switch(num[i]) { case 0 :printf("\t|起泡排序 %ld %ld %f ",com0,mov0,t0); break; case 1 :printf("\t |插入排序 %ld %ld %f ",com1,mov1,t1); break; case 2 :printf("\n\t|选择排序 %ld %ld %f ",com2,mov2,t2); break; case 3 :printf("\n\t|希尔排序 %ld %ld %f ",com3,mov3,t3); break; case 4 :printf("\n\t|快速排序 %ld %ld %f ",com4,mov4,t4); break; case 5 :printf("\n\t|堆排序 %ld %ld %f ",com5,mov5,t5); break; } } } //显示提示信息 void Enter_main() { printf("\t\t\t 欢迎使用 ! ! !\n"); printf("\t\t\t***********************\n"); printf("\t\t\t |--| |--| \n"); printf("\t\t\t!__| |_|_|_|_|_| |__!\n"); printf("\t\t\t| |\n"); printf("\t\t\t| ＾ ＾ |\n"); printf("\t\t\t| ○ ○ |\n"); printf("\t\t\t| ● ＠＠ ● |\n"); printf("\t\t\t| |\n"); printf("\t\t\t| ● |\n"); printf("\t\t\t|_____________________|\n"); printf("\t\t\t***********************\n"); printf("请按任意键继续……"); } void main() { int i,j,m; char c='y'; int n=7; int num[6]; clock_t start,end; srand(time(NULL)); randomizeNum(MAX); Enter_main(); getch(); printf("\n\n\n\n\t\t##############################################\n"); printf("\t\t 各种排序的实现与效率分析 \n"); printf("\t\t(1)对起泡排序、直接排序、简单选择排序、快速排 \n"); printf("\t\t 序、希尔排序、堆排序算法进行比较； \n"); printf("\t\t(2)数组中的数据是随机产生的，可用多组数据作不 \n"); printf("\t\t 同数据作比较，比较指标有：关键字参加比较次 \n"); printf("\t\t 数和关键字的移动次数和每种算法所需要的时间; \n"); printf("\t\t(3)输出比较结果。 \n"); printf("\t\t##############################################\n"); printf("请按任意键继续……"); getch(); while(1) { i=0; while(1) { while(1) { printf("\n\t\t请选择要排序的方法(0-5)\n"); printf("\t\t_________________\n"); printf("\t\t| 0.起泡排序 |\n"); printf("\t\t| 1.插入排序 |\n"); printf("\t\t| 2.选择排序 |\n"); printf("\t\t| 3.希尔排序 |\n"); printf("\t\t| 4.快速排序 |\n"); printf("\t\t| 5.堆排序 |\n"); printf("\t\t_________________\n"); printf("您的选择:"); scanf("%d",&j); while(1) { if(j>=0&&j<6) break; printf("你输入有误,请从新输入:"); scanf("%d",&j); } if (j!=n) { switch(j) { case 0 : { restore(MAX); start=clock(); bubblesort(a,MAX); end=clock(); t0=(double)(end-start)/CLOCKS_PER_SEC; printf("\n起泡排序所需要的时间为：%f\n",t0); }break; case 1 : { restore(MAX); start=clock(); insertsort(a,MAX); end=clock(); t1=(double)(end-start)/CLOCKS_PER_SEC; printf("\n插入排序所需要的时间为：%f\n",t1); }break; case 2 : { restore(MAX); start=clock();