C語(yǔ)言四種排序算法時(shí)間復(fù)雜度比較

1、1、方案設(shè)計(jì)： 我這次實(shí)驗(yàn)通過(guò)隨機(jī)生成30000個(gè)隨機(jī)數(shù)，把隨機(jī)數(shù)存到數(shù)組中，用這同一組隨機(jī)數(shù)據(jù)分別進(jìn)行四種排序，直接插入排序、直接選擇排序、冒泡排序和快速排序。還通過(guò)了調(diào)用txt文件把運(yùn)算所需時(shí)間導(dǎo)出，分別輸出各個(gè)算法所需用時(shí)并對(duì)用時(shí)時(shí)長(zhǎng)再進(jìn)行冒泡排序算出用時(shí)最短的算法。2、程序代碼：#include <stdio.h>#include <conio.h>#include <stdlib.h>#include <windows.h>#include <time.h>#define N 30000void Wrong() /輸入錯(cuò)誤

2、printf("n語(yǔ)法錯(cuò)誤，請(qǐng)重新輸入！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-) /比較,找出本趟最小關(guān)

4、鍵字的記錄 if (aj<aj-1) temp=aj; /進(jìn)行交換,將最小關(guān)鍵字記錄前移 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)/計(jì)算直接插入排序算法用時(shí) 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用直接插入排序法用的時(shí)間為%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)/計(jì)算選擇排序用時(shí) 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用直接選擇排序法用的時(shí)間為%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)/計(jì)算冒泡排序算

10、法用時(shí) 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用冒泡排序法用的時(shí)間為%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)/計(jì)算快速排序算法用時(shí) 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用快速排序法用的時(shí)間為%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) /時(shí)間數(shù)組的冒泡排序 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)顯示隨機(jī)數(shù)n"); printf("(2)直接插入排序n"); printf("(3)直接選擇排序n"); printf("(4)冒泡排序

15、n"); printf("(5)快速排序n"); printf("(6)時(shí)間效率比較n"); printf("n請(qǐng)?jiān)谏鲜鲂蛱?hào)中選擇一個(gè)并輸入:n"); printf("*n");void main() int i,p,aN; srand(int)time(NULL); /隨機(jī)種子 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;/時(shí)間數(shù)組 switch(p) case 1: Disp(a); FILE *fp; fp=fopen("隨機(jī)數(shù).txt","w"); for(i=0; i<N; i+)fprintf(fp,"%d ",ai); fclose(fp); getchar(); printf("n請(qǐng)按任意鍵繼續(xù)!"); getchar(); break; case 2: TInser

17、tSort(a,p); printf("n請(qǐng)按任意鍵繼續(xù)!"); getchar(); break; case 3: TSelectSort(a,p); printf("n請(qǐng)按任意鍵繼續(xù)!"); getchar(); break; case 4: TBubbleSort(a,p); printf("n請(qǐng)按任意鍵繼續(xù)!"); getchar(); break; case 5: Tquicksort(a,N,p); printf("n請(qǐng)按任意鍵繼續(xù)!"); 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("排序這組數(shù)據(jù)較快的排序法是：n"); if(TIMES1=TIMES11) printf("直接插入排序:%f秒!n",TIMES1); if(TIMES1=TIMES12) printf("直接選擇排序:%f秒!n",TIMES1); if(TIMES1=TIMES13) printf("冒泡排序:%f秒!n&quo