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

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

4、<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 nodeint 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=alow;while(i!=j)while(i<j&am

5、p;&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=ai;LARGE_INTEGER m_liPerfFreq= 0;QueryPerforma

6、nceFrequency(&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();

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

8、rmanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart= 0;QueryPerformanceCounter(&m_liPerfStart);SelectSort(b,p);if(p!=6)4 / 10Disp(b);getchar();LARGE_INTEGER liPerfNow= 0;QueryPerformanceCounter(&liPerfNow);double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart;time/=m_liPerfFreq.

9、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)/ 计算冒泡排序算法用时int i;int bN;for(i=0; i<N; i+)bi=ai;LARGE_INTEGER m_liPerfFreq= 0

10、;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

11、(b);getchar();printf("n 用冒泡排序法用的时间为%f 秒； ",time);FILE *fp;fp=fopen(" 冒泡排序 .txt","w");fprintf(fp,"%d ",bi);fclose(fp);return(time);double Tquicksort(int a,int n,int p)/ 计算快速排序算法用时int i;int bN;for(i=0; i<N; i+)bi=ai;LARGE_INTEGER m_liPerfFreq= 0;QueryPerforma

12、nceFrequency(&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()

13、;printf("n 用快速排序法用的时间为 %f 秒； ",time);FILE *fp;fp=fopen(" 快速排序 .txt","w");for(i=0; i<N; i+)fprintf(fp,"%d ",bi);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(aj+1<aj)temp=aj+1;1

14、1 / 10aj+1=aj;aj=temp;void menu()printf("*nn");printf("(1) 显示随机数n");printf("(2) 直接插入排序printf("(3) 直接选择排序printf("(4) 冒泡排序n");printf("(5) 快速排序n");printf("(6) 时间效率比较n");n");n");printf("n 请在上述序号中选择一个并输入printf("*n");:n&q

15、uot;);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(p=0)/ 随机种子printf(" 谢谢使用 !n");getchar();break;double TIMES5,TIMES15;/ 时间数组switch(p) case 1:Disp(a);FILE *fp;fp=fopen(" 随机数 .txt&

16、quot;,"w");for(i=0; i<N; i+)fprintf(fp,"%d ",ai);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

17、(a,p);printf("n 请按任意键继续!");getchar();break;case 5:Tquicksort(a,N,p);printf("n 请按任意键继续!");getchar();break;case 6:system("cls");TIMES11=TIMES1=TInsertSort(a,p);TIMES12=TIMES2=TSelectSort(a,p);TIMES13=TIMES3=TBubbleSort(a,p);TIMES14=TIMES4=Tquicksort(a,N,p);getchar();Buble

18、Sort(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",TIMES1);if(TIMES1=TIMES14) printf("快速排序：f 秒!n",TIMES1);if(TIMES1!=TIMES2)if(TIMES2=TIMES11) printf("直接插入排序:%f 秒!n",TIMES2);if(TIMES2=TIMES12) prin