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

1、1、方案设计：我这次实验通过随机生成 30000 个随机数，把随机数存到数组中， 用这同一 组随机数据分别进行四种排序， 直接插入排序、 直接选择排序、 冒泡排序和快速 排序。还通过了调用 txt 文件把运算所需时间导出，分别输出各个算法所需用时 并对用时时长再进行冒泡排序算出用时最短的算法。2、程序代码：#include #include #include #include #include #define N 30000void Wrong()/ 输入错误printf(n 语法错误，请重新输入！ n);getchar();void Disp(int a) / 清屏int i;system(

2、cls);for(i=0; iN; i+)if(i-1)%10=9)printf(n);printf(%-7d,ai);void InsertSort(int a,int p) / 直接插入排序算法int i,j,temp;for(i=1; i0&aj-1temp; j-)aj=aj-1;aj=temp;void SelectSort(int a,int p) / 选择排序算法 int i,j,k;for(i=0; iN-1; i+)k=i;for(j=i+1; jN; j+) if(ajak) k=j;if(k!=i)int temp; temp=ak; ak=ai; ai=temp;voi

3、d BubbleSort(int a,int p) / 冒泡排序算法int i,j,temp;for (i=0; ii; j-) / 比拟 ,找出本趟最小关键字的记录 if (aj-1)low=sttop.low; high=sttop.high; top-;i=low; j=high; if(lowhigh) temp=alow;while(i!=j)while(itemp)j-; if(ij) ai=aj; i+;while(ij&aitemp)i+; if(ij)aj=ai;j-;ai=temp; top+; sttop.low=low; sttop.high=i-1; top+;stt

4、op.low=i+1; sttop.high=high;double TInsertSort(int a,int p)/ 计算直接插入排序算法用时 int i;int bN;for(i=0; iN; 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; Q

5、ueryPerformanceCounter(&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; iN; i+) fprintf(fp,%d ,bi);fclose(fp);return(time);double TSelectSort(int

6、 a,int p)/ 计算选择排序用时int i;int bN;for(i=0; iN; 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(&liPe

7、rfNow);double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;printf(n 用直接选择排序法用的时间为 %f 秒； ,time);FILE *fp;fp=fopen( 直接选择排序 .txt,w);for(i=0; iN; i+) fprintf(fp,%d ,bi);fclose(fp); return(time);double TBubbleSort(int a,int p)/ 计算冒泡排序算法用时int i;int bN;for(i=0; iN; i+) bi=a

8、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_liPerfFre

9、q.QuadPart;if(p!=6) Disp(b); getchar();printf(n用冒泡排序法用的时间为%f秒；,time);FILE *fp;fp=fopen( 冒泡排序 .txt,w);for(i=0; iN; i+) fprintf(fp,%d ,bi);fclose(fp); return(time);double Tquicksort(int a,int n,int p)/ 计算快速排序算法用时 int i;int bN;for(i=0; iN; i+)bi=ai;LARGE_INTEGER m_liPerfFreq= 0; QueryPerformanceFrequen

10、cy(&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 用快速排序

11、法用的时间为 %f 秒； ,time); FILE *fp;fp=fopen( 快速排序 .txt,w);for(i=0; iN; i+)fprintf(fp,%d ,bi); fclose(fp); return(time);void BubleSort(double a) / 时间数组的冒泡排序int i,j;double temp;for(i=1; i=i; j-) if(aj+1aj) temp=aj+1;aj+1=aj; aj=temp;void menu()printf(*nn);printf(1) 显示随机数 n);printf(2) 直接插入排序 n);printf(3) 直接

12、选择排序 n);printf(4) 冒泡排序 n);printf(5) 快速排序 n);printf(6) 时间效率比拟 n);:n);printf(n 请在上述序号中选择一个并输入printf(*void main()int i,p,aN;srand(int)time(NULL);/ 随机种子for(i=0; iN; i+)ai=rand()%50000+1;while(1) system(cls); menu();scanf(%d,&p); if(p=0)printf( 谢谢使用 !n); getchar();break;double TIMES5,TIMES15;/ 时间数组switch

13、(p)case 1:Disp(a);FILE *fp;fp=fopen( 随机数 .txt,w);for(i=0; iN; 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 请按任意键继

14、续 !);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();BubleSort(TIMES);printf(nn);printf( 排序这组数据较快的排序法是： n);if(T

15、IMES1=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) printf(直接选择排序 %f 秒!n,TIMES2);if(TIMES2=TIMES13) printf(冒泡排序 %f 秒 !n,TIMES2);if(TIMES2=TIMES14) printf(快速排序 %f 秒 !n,TIMES2);printf(n请按任意键继续