#include<stdio.h>#include<math.h>#include<stdlib.h>#include<time.h>#define M 30001random(int a[30001]){int i;for(i=1;i<30001;i++)a[i]=rand()%30001;}//随机生成30000个数函数int change1(char a[81]){int b=0,n,i;for(i=0;a[i]!=0;i++);n=i-1;for(;i>1;i--)b+=((int)pow(10,n+1-i))*(a[i-1]-48);if(a[0]=='-')b=b*(-1);elseb+=((int)pow(10,n))*(a[0]-48);return b;}//字符转化成整型insort(int a[30001]){int i,j,temp,temp1,n;int count=0;n=30001;for(i=1;i<n;i++){temp=a[i];//for(j=i-1;j>=0;j--)/* 每次循环完毕数组的0到i-1项为一个有序的序列*/{count=0;/*这里count是标记位，可以减少比较次数*/if(a[j]>temp){temp1=a[j+1];a[j+1]=a[j];a[j]=temp1;count++;}//满足条件，前移if(count==0)break;//位置恰当，退出}}}//insort插入排序函数selsort(int a[30001]){int i,j,temp;for(i=1;i<30000;i++)for(j=i+1;j<30001;j++)if(a[i]>a[j]){temp=a[j];a[j]=a[i];a[i]=temp;}}//选择排序bubsort(int a[30001]){int i,j,temp;for(i=1;i<30001;i++)for(j=30000;j>i;j--){if(a[j-1]>a[j]){temp=a[j-1];a[j-1]=a[j];a[j]=temp;}}}//冒泡排序int partition(int a[30001],int low,int high){int pr;a[0]=a[low];pr=a[low];while(low<high){while(low<high&&a[high]>=pr) --high;a[low]=a[high];while(low<high&&a[low]<=pr) ++low;a[high]=a[low];}a[low]=a[0];return low;}//partionqsort(int a[30001],int low,int high) {int pr;if(low<high){pr=partition(a,low,high);qsort(a,low,pr-1);qsort(a,pr+1,high);}}//qsortquicksort(int a[30001]){//快速排序qsort(a,1,30000);}//quicksortvoid heapadjust(int a[M],int s,int m) {//建立堆函数int rc,j;rc=a[s];for(j=2*s;j<=m;j*=2){if(j<m&&a[j]<a[j+1])++j;if(rc>=a[j])break;a[s]=a[j];s=j;}a[s]=rc;}//heapadjust建立堆函数void heapsort(int a[30001]){int i,temp;for(i=M/2;i>0;--i)heapadjust(a,i,M);//建初始大顶堆for(i=M;i>1;--i){temp=a[i];a[i]=a[1];a[1]=temp;//交换，把最后一个记录和堆顶记录交换，最值移到最后heapadjust(a,1,i-1);//建立顶堆}}//heapadjust堆排序merge(int array[],int p,int q,int r){int i,k=0,begin1=p,end1=q,begin2=q+1,end2=r,*temp;temp=(int *)malloc((r-p+1)*sizeof(int));while((begin1<=end1)&&(begin2<=end2)){if(array[begin1]<array[begin2]){temp[k] = array[begin1]; begin1++;}else{temp[k] = array[begin2]; begin2++;}k++;}while(begin1<=end1){temp[k++] = array[begin1++];}while(begin2<=end2){temp[k++] = array[begin2++];}for (i = 0; i < (r - p +1); i++)array[p+i] = temp[i];free(temp);}//mergevoid mergesort(int array[], unsigned int first, unsigned int last) {int mid = 0;if(first<last){mid = (first+last)/2;mergesort(array, first, mid);mergesort(array, mid+1,last);merge(array,first,mid,last);}}//mergesort归并排序work1(char timep[2][30]){int A,a,B,b,margin;char newmin[3],newsec[3],oldmin[3],oldsec[3];newmin[0]=timep[0][14];newmin[1]=timep[0][15];newsec[0]=timep[0][17];newsec[1]=timep[0][18];oldmin[0]=timep[1][14];oldmin[1]=timep[1][15];oldsec[0]=timep[1][17];oldsec[1]=timep[1][18];newmin[2]=0;newsec[2]=0;oldmin[2]=0;oldsec[2]=0;A=change1(newmin);a=change1(newsec);B=change1(oldmin);b=change1(oldsec);margin=(B-A)*60+b-a;return margin;}//计算时间差void mark(char timep[30]){time_t timep1;int i;time(&timep1);for(i=0;ctime(&timep1)[i]!=0;i++)timep[i]=ctime(&timep1)[i];timep[i]=0;//起始时间记录}//起始时刻记录main(){int a[30001],num,i,margin,n;float t;char timep[2][30];time_t timep2;printf("1:插入排序\n\n");printf("2:选择排序\n\n");printf("3:冒泡排序\n\n");printf("4:快速排序\n\n");printf("5:堆排序\n\n");printf("6:归并排序\n\n");loop:printf("请选择排序方法,输入序号\n");scanf("%d",&num);switch(num){case 1:mark(timep[0]);random(a);n=1;insort(a);break;//插入排序函数case 2:mark(timep[0]);random(a);n=1;selsort(a);break;//选择排序函数case 3:mark(timep[0]);;random(a);n=1;bubsort(a);break;//冒泡排序函数case 4:mark(timep[0]);n=99;for(i=0;i<n;i++){random(a);quicksort(a);}break;//快速排序函数case 5:mark(timep[0]);n=99;for(i=0;i<n;i++){random(a);heapsort(a);}break;//堆排序函数case 6:mark(timep[0]);n=9;for(i=0;i<n;i++){random(a);mergesort(a,1,30001);}break;//归并排序函数default:{printf("ERROR,重新输入");goto loop;}}time(&timep2);for(i=0;ctime(&timep2)[i]!=0;i++)timep[1][i]=ctime(&timep2)[i];timep[1][i]=0;//运行末时刻记录margin=work1(timep);//计算时间差for(i=1;i<30001;i++)printf("%d ",a[i]);printf("\n\n\n所需时间为%.3f秒",((float)margin)/n);}。