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

1、1、方案设计： 我这次实验通过随机生成30000个随机数，把随机数存到数组中，用这同一组随机数据分别进行四种排序，直接插入排序、直接选择排序、冒泡排序和快速排序。还通过了调用txt文件把运算所需时间导出，分别输出各个算法所需用时并对用时时长再进行冒泡排序算出用时最短的算法。2、程序代码：#include <stdio.h>#include <conio.h>#include <stdlib.h>#include <windows.h>#include <time.h>#define N 30000void Wrong() /输入错误

2、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",ai); void InsertSort(int a,int p) /直接插入排序算法 int i,j,temp; for(i=1; i<N; i+) temp=ai; for(j=i; j>0&&aj-1>

3、;temp; j-) aj=aj-1; aj=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(aj<ak) k=j; if(k!=i) int temp; temp=ak; ak=ai; ai=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-) /比较,找出本趟最小关

4、键字的记录 if (aj<aj-1) temp=aj; /进行交换,将最小关键字记录前移 aj=aj-1; aj-1=temp; void quicksort(int a,int n,int p) /快速排序算法 int i,j,low,high,temp,top=-1; struct node int low,high; stN; top+; sttop.low=0; sttop.high=n-1; while(top>-1) low=sttop.low; high=sttop.high; top-; i=low; j=high; if(low<high) temp=alo

5、w; while(i!=j) while(i<j&&aj>temp)j-; if(i<j) ai=aj; i+; while(i<j&&ai<temp)i+; if(i<j) aj=ai; j-; ai=temp; top+; sttop.low=low; sttop.high=i-1; top+; sttop.low=i+1; sttop.high=high; double TInsertSort(int a,int p)/计算直接插入排序算法用时 int i; int bN; for(i=0; i<N; i+) bi

6、=ai; 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

7、; 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 ",bi); fclose(fp); return(time);double TSelectSort(int a,int p)/计算选择排序用时 int i; int bN; for

8、(i=0; i<N; i+) bi=ai; 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

9、 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 ",bi); fclose(fp); return(time);double TBubbleSort(int a,int p)/计算冒泡排序算

10、法用时 int i; int bN; for(i=0; i<N; i+) bi=ai; 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=l

11、iPerfNow.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 ",bi); fclose(fp); return(time);double Tquicksort(int

12、 a,int n,int p)/计算快速排序算法用时 int i; int bN; for(i=0; i<N; i+) bi=ai; 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(&l

13、iPerfNow); 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 ",bi); fclose(fp); return(tim

14、e);void BubleSort(double a) /时间数组的冒泡排序 int i,j; double temp; for(i=1; i<6; i+) for(j=4; j>=i; j-) if(aj+1<aj) temp=aj+1; aj+1=aj; aj=temp; void menu() printf("*nn"); printf("(1)显示随机数n"); printf("(2)直接插入排序n"); printf("(3)直接选择排序n"); printf("(4)冒泡排序

15、n"); printf("(5)快速排序n"); printf("(6)时间效率比较n"); printf("n请在上述序号中选择一个并输入:n"); printf("*n");void main() int i,p,aN; srand(int)time(NULL); /随机种子 for(i=0; i<N; i+) ai=rand()%50000+1; while(1) system("cls"); menu(); scanf("%d",&p); if

16、(p=0) printf("谢谢使用!n"); getchar(); break; double TIMES5,TIMES15;/时间数组 switch(p) case 1: Disp(a); FILE *fp; fp=fopen("随机数.txt","w"); for(i=0; i<N; i+)fprintf(fp,"%d ",ai); fclose(fp); getchar(); printf("n请按任意键继续!"); getchar(); break; case 2: TInser

17、tSort(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: syste

18、m("cls"); TIMES11=TIMES1=TInsertSort(a,p); TIMES12=TIMES2=TSelectSort(a,p); TIMES13=TIMES3=TBubbleSort(a,p); TIMES14=TIMES4=Tquicksort(a,N,p); getchar(); BubleSort(TIMES); printf("nn"); printf("排序这组数据较快的排序法是：n"); if(TIMES1=TIMES11) printf("直接插入排序:%f秒!n",TIMES1); if(TIMES1=TIMES12) printf("直接选择排序:%f秒!n",TIMES1); if(TIMES1=TIMES13) printf("冒泡排序:%f秒!n&quo