C语言四种排序算法时间复杂度比较
1、方案设计：我这次实验通过随机生成30000个随机数， 把随机数存到数组中， 用这同一组随机数据分别进行四种排序， 直接插入排序、 直接选择排序、 冒泡排序和快速排序。 还通过了调用 txt 文件把运算所需时间导出， 分别输出各个算法所需用时并对用时时长再进行冒泡排序算出用时最短的算法。2、程序代码：#define N 30000void 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",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>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<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&&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;QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart= 0;QueryPerformanceCounter(&m_liPerfStart);InsertSort(b,p);LARGE_INTEGER liPerfNow= 0;QueryPerformanceCounter(&liPerfNow);if(p!=6)Disp(b); getchar();用直接插入排序法用的时间为f秒；",time); printf("nFILE *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;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);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;QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart= 0;QueryPerformanceCounter(&m_liPerfStart);BubbleSort(b,p);LARGE_INTEGER liPerfNow= 0;QueryPerformanceCounter(&liPerfNow);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 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(&liPerfNow);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);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) printf("(2) printf("(3) printf("(4) printf("(5) printf("(6) printf("n显示随机数n");直接插入排序直接选择排序冒泡排序n");快速排序n");时间效率比较n");n");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(p=0)谢谢使用 !n");printf("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: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:s
