C语言四种排序算法时间复杂度比较.doc

资源描述

. 1、方案设计：我这次实验通过随机生成30000个随机数，把随机数存到数组中，用这同一组随机数据分别进行四种排序，直接插入排序、直接选择排序、冒泡排序和快速排序。还通过了调用txt文件把运算所需时间导出，分别输出各个算法所需用时并对用时时长再进行冒泡排序算出用时最短的算法。 2、程序代码： #include <stdio.h> #include <conio.h> #include <stdlib.h> #include <windows.h> #include <time.h> #define N 30000 void Wrong() //输入错误 { printf("\n语法错误，请重新输入！\n"); getchar(); } void Disp(int a[]) //清屏 { int i; system("cls"); for(i=0; i<N; i++) { if((i-1)%10==9) printf("\n"); printf("%-7d",a[i]); } } void InsertSort(int a[],int p) //直接插入排序算法 { int i,j,temp; for(i=1; i<N; i++) { temp=a[i]; for(j=i; j>0&&a[j-1]>temp; j--) a[j]=a[j-1]; a[j]=temp; } } void SelectSort(int a[],int p) //选择排序算法 { int i,j,k; for(i=0; i<N-1; i++) { k=i; for(j=i+1; j<N; j++) if(a[j]<a[k]) k=j; if(k!=i) { int temp; temp=a[k]; a[k]=a[i]; a[i]=temp; } } } void BubbleSort(int a[],int p) //冒泡排序算法 { int i,j,temp; for (i=0; i<N-1; i++) { for (j=N-1; j>i; j--) //比较,找出本趟最小关键字的记录 if (a[j]<a[j-1]) { temp=a[j]; //进行交换,将最小关键字记录前移 a[j]=a[j-1]; a[j-1]=temp; } } } void quicksort(int a[],int n,int p) //快速排序算法 { int i,j,low,high,temp,top=-1; struct node { int low,high; } st[N]; top++; st[top].low=0; st[top].high=n-1; while(top>-1) { low=st[top].low; high=st[top].high; top--; i=low; j=high; if(low<high) { temp=a[low]; while(i!=j) { while(i<j&&a[j]>temp)j--; if(i<j) { a[i]=a[j]; i++; } while(i<j&&a[i]<temp)i++; if(i<j) { a[j]=a[i]; j--; } } a[i]=temp; top++; st[top].low=low; st[top].high=i-1; top++; st[top].low=i+1; st[top].high=high; } } } double TInsertSort(int a[],int p)//计算直接插入排序算法用时 { int i; int b[N]; for(i=0; i<N; i++) b[i]=a[i]; LARGE_INTEGER m_liPerfFreq= {0}; QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart= {0}; QueryPerformanceCounter(&m_liPerfStart); InsertSort(b,p); LARGE_INTEGER liPerfNow= {0}; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart; if(p!=6) { Disp(b); getchar(); } printf("\n用直接插入排序法用的时间为%f秒；",time); FILE *fp; fp=fopen("直接插入排序.txt","w"); for(i=0; i<N; i++) fprintf(fp,"%d ",b[i]); fclose(fp); return(time); } double TSelectSort(int a[],int p)//计算选择排序用时 { int i; int b[N]; for(i=0; i<N; i++) b[i]=a[i]; LARGE_INTEGER m_liPerfFreq= {0}; QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart= {0}; QueryPerformanceCounter(&m_liPerfStart); SelectSort(b,p); if(p!=6) { Disp(b); getchar(); } LARGE_INTEGER liPerfNow= {0}; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart; printf("\n用直接选择排序法用的时间为%f秒；",time); FILE *fp; fp=fopen("直接选择排序.txt","w"); for(i=0; i<N; i++) fprintf(fp,"%d ",b[i]); fclose(fp); return(time); } double TBubbleSort(int a[],int p)//计算冒泡排序算法用时 { int i; int b[N]; for(i=0; i<N; i++) b[i]=a[i]; LARGE_INTEGER m_liPerfFreq= {0}; QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart= {0}; QueryPerformanceCounter(&m_liPerfStart); BubbleSort(b,p); LARGE_INTEGER liPerfNow= {0}; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart; if(p!=6) { Disp(b); getchar(); } printf("\n用冒泡排序法用的时间为%f秒；",time); FILE *fp; fp=fopen("冒泡排序.txt","w"); for(i=0; i<N; i++) fprintf(fp,"%d ",b[i]); fclose(fp); return(time); } double Tquicksort(int a[],int n,int p)//计算快速排序算法用时 { int i; int b[N]; for(i=0; i<N; i++) b[i]=a[i]; LARGE_INTEGER m_liPerfFreq= {0}; QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart= {0}; QueryPerformanceCounter(&m_liPerfStart); quicksort(b,N,p); LARGE_INTEGER liPerfNow= {0}; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart; if(p!=6) { Disp(b); getchar(); } printf("\n用快速排序法用的时间为%f秒；",time); FILE *fp; fp=fopen("快速排序.txt","w"); for(i=0; i<N; i++) fprintf(fp,"%d ",b[i]); fclose(fp); return(time); } void BubleSort(double a[]) //时间数组的冒泡排序 { int i,j; double temp; for(i=1; i<6; i++) { for(j=4; j>=i; j--) if(a[j+1]<a[j]) { temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; } } } void menu() { printf("*********************************\n\n"); printf("(1)显示随机数\n"); printf("(2)直接插入排序\n"); printf("(3)直接选择排序\n"); printf("(4)冒泡排序\n"); printf("(5)快速排序\n"); printf("(6)时间效率比较\n"); printf("\n请在上述序号中选择一个并输入:\n"); printf("*********************************\n"); } void main() { int i,p,a[N]; srand((int)time(NULL)); //随机种子 for(i=0; i<N; i++) a[i]=rand()%50000+1; while(1) { system("cls"); menu(); scanf("%d",&p); if(p==0) { printf("谢谢使用!\n"); getchar(); break; } double TIMES[5],TIMES1[5];//时间数组 switch(p) { case 1: Disp(a); FILE *fp; fp=fopen("随机数.txt","w"); for(i=0; i<N; i++)fprintf(fp,"%d ",a[i]); fclose(fp); getchar(); printf("\n请按任意键继续!"); getchar(); break; case 2: TInsertSort(a,p); printf("\n请按任意键继续!"); getchar(); break; case 3: TSelectSort(a,p); printf("\n请按任意键继续!"); getchar(); break; case 4: TBubbleSort(a,p); printf("\n请按任意键继续!"); getchar(); break; case 5: Tquicksort(a,N,p); printf("\n请按任意键继续!"); getchar(); break; case 6: system("cls"); TIMES1[1]=TIMES[1]=TInsertSort(a,p); TIMES1[2]=TIMES[2]=TSelectSort(a,p); TIMES1[3]=TIMES[3]=TBubbleSort(a,p); TIMES1[4]=TIMES[4]=Tquicksort(a,N,p); getchar(); BubleSort(TIMES); printf("\n\n"); { printf("排序这组数据较快的排序法是：\n"); if(TIMES[1]==TIMES1[1]) printf("直接插入排序:%f秒!\n",TIMES[1]); if(TIMES[1]==TIMES1[2]) printf("直接选择排序:%f秒!\n",TIMES[1]); if(TIMES[1]==TIMES1[3]) printf("冒泡排序:%f秒!\n",TIMES[1]); if(TIMES[1]==TIMES1[4]) printf("快速排序:%f秒!\n",TIMES[1]); if(TIMES[1]!=TIMES[2]) { if(TIMES[2]==TIMES1[1]) printf("直接插入排序:%f秒!\n",TIMES[2]); if(TIMES[2]==TIMES1[2]) printf("直接选择排序%f秒!\n",TIMES[2]); if(TIMES[2]==TIMES1[3]) printf("冒泡排序%f秒!\n",TIMES[2]); if(TIMES[2]==TIMES1[4]) printf("快速排序%f秒!\n",TIMES[2]); } } printf("\n请按任意键继续!"); srand((int)time(NULL)); for(i=0; i<N; i++) { a[i]=rand()%30000+1; } getchar(); break; default: Wrong(); printf("\n请按任意键继续!"); getchar(); break; } } } 3、运行结果与分析：通过多次运行程序，均显示快速排序算法最快，时间复杂度最低，通过所学的知识来计算，快速排序平均时间复杂度是0(nlog2n)，最好情况0(nlog2n)，最坏情况0(n2)，相对来说，这次实验符合理论规律。 .页脚.

展开阅读全文