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

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

2、t;n语法错误，请重新输入！n");getchar();voidDisp(inta)/清屏inti;system("cls");for(i=0;i<N;i+)if(i-1)%10=9)printf("n");printf("%-7d”,ai);voidInsertSort(inta,intp)/直接插入排序算法inti,j,temp;for(i=1;i<N;i+)temp=ai;for(j=i;j>0&&aj-1>temp;j-)aj=aj-1;aj=temp;voidSelectSort(in

3、ta,intp)/选择排序算法(inti,j,k;for(i=0;i<N-1;i+)(k=i;for(j=i+1;j<N;j+)if(a亦ak)k=j;if(k!=i)(inttemp;temp=ak;ak=ai;ai=temp;voidBubbleSort(inta,intp)/冒泡排序算法(inti,j,temp;for(i=0;i<N-1;i+)(for(j=N-1;j>i;j-)/比较,找出本趟最小关键字的记录if(aj<aj-1)(temp=aj;/进行交换，将最小关键字记录前移aj=aj-1;aj-1=temp;voidquicksort(inta,i

4、ntn,intp)快速排序算法(inti,j,low,high,temp,top=-1;structnode(intlow,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=alow;while(i!=j)(while(i<j&&aj>temp)j-;if(i<j)(ai=aj;i+;while(i<j&&ai<temp)i+;if

5、(i<j)(aj=ai;j-;ai=temp;top+;sttop.low=low;sttop.high=i-1;top+;sttop.low=i+1;sttop.high=high;doubleTInsertSort(inta,intp)/计算直接插入排序算法用时(inti;intbN;for(i=0;i<N;i+)bi=ai;LARGE_INTEGERm_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGERm_liPerfStart=0;QueryPerformanceCounter(&a

6、mp;m_liPerfStart);InsertSort(b,p);LARGE_INTEGERliPerfNow=0;QueryPerformanceCounter(&liPerfNow);doubletime=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&l

7、t;N;i+)fprintf(fp,"%d",bi);fclose(fp);return(time);doubleTSelectSort(inta,intp)/计算选择排序用时inti;intbN;for(i=0;i<N;i+)bi=ai;LARGE_INTEGERm_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGERm_liPerfStart=0;QueryPerformanceCounter(&m_liPerfStart);SelectSort(b,p);if(p!

8、=6)Disp(b);getchar();LARGE_INTEGERliPerfNow=0;QueryPerformanceCounter(&liPerfNow);doubletime=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);fc

9、lose(fp);return(time);doubleTBubbleSort(inta,intp)/计算冒泡排序算法用时inti;intbN;for(i=0;i<N;i+)bi=ai;LARGE_INTEGERm_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGERm_liPerfStart=0;QueryPerformanceCounter(&m_liPerfStart);BubbleSort(b,p);LARGE_INTEGERliPerfNow=0;QueryPerformanceC

10、ounter(&liPerfNow);doubletime=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(time);doubleTquickso

11、rt(inta,intn,intp)/计算快速排序算法用时inti;intbN;for(i=0;i<N;i+)bi=ai;LARGE_INTEGERm_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGERm_liPerfStart=0;QueryPerformanceCounter(&m_liPerfStart);quicksort(b,N,p);LARGE_INTEGERliPerfNow=0;QueryPerformanceCounter(&liPerfNow);doubleti

12、me=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(time);voidBubleSort(doublea)/时间数组的冒泡排序inti,j;d

13、oubletemp;for(i=1;i<6;i+)for(j=4;j>=i;j-)if(aj+1<aj)temp=aj+1;aj+1=aj;aj=temp;voidmenu()(printf("*nn");printf("(1)显示随机数n");printf("(2)直接插入排序n");printf("(3)直接选择排序n");printf("(4)冒泡排序n");printf("(5)快速排序n");printf("(6)时间效率比较n"

14、;);printf("n请在上述序号中选择一个并输入：n");printf("*n");voidmain()(inti,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(p=0)(printf(-谢谢使用！n");getchar();break;doubleTIMES5,TIMES15;/时间数组switch(p)(case1：D

15、isp(a);FILE*fp;fp=fopen("随机数.txt”,"w”);for(i=0;i<N;i+)fprintf(fp,"%d",ai);fclose(fp);getchar();printf(-n请按任意键继续！")；getchar();break;case2:TInsertSort(a,p);printf(-n请按任意键继续！")；getchar();break;case3:TSelectSort(a,p);printf(-n请按任意键继续！")；getchar();break;case4:TBubble

16、Sort(a,p);printf(-n请按任意键继续！")；getchar();break;case5:Tquicksort(a,N,p);printf(-n请按任意键继续！")；getchar();break;case6:system("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

17、);printf("nn");(printf("排序这组数据较快的排序法是：n");if(TIMES1=TIMES11)printf("直接插入排序:%f秒!n”,TIMES1);if(TIMES1=TIMES12)printf("直接选择排序:%f秒!n”,TIMES1);if(TIMES1=TIMES13)printf("冒泡排序:%f秒!n”,TIMES1);if(TIMES1=TIMES14)printf("快速排序:%f秒!n”,TIMES1);if(TIMES1!=TIMES2)(if(TIMES2=T

18、IMES11)printf("直接插入排序：f秒!n”,TIMES2);if(TIMES2=TIMES12)printf("直接选择排序%f秒!n”,TIMES2);if(TIMES2=TIMES13)printf("冒泡排序%f秒!n”,TIMES2);if(TIMES2=TIMES14)printf("快速排序%f秒!n”,TIMES2);printf(-n请按任意键继续!");srand(int)time(NULL);for(i=0;i<N;i+)ai=rand()%30000+1;getchar();break;default:Wrong();printf(-n请按任意键继