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

1、1、方案設(shè)計： 我這次實驗通過隨機生成30000個隨機數(shù)，把隨機數(shù)存到數(shù)組中，用這同一組隨機數(shù)據(jù)分別進行四種排序，直接插入排序、直接選擇排序、冒泡排序和快速排序。還通過了調(diào)用txt文件把運算所需時間導(dǎo)出，分別輸出各個算法所需用時并對用時時長再進行冒泡排序算出用時最短的算法。2、程序代碼：#include <stdio.h>#include <conio.h>#include <stdlib.h>#include <windows.h>#include <time.h>#define N 30000void 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-) /比較,找出本趟最小關(guān)

4、鍵字的記錄 if (aj<aj-1) temp=aj; /進行交換,將最小關(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)/計算直接插入排序算法用時 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用直接插入排序法用的時間為%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

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用直接選擇排序法用的時間為%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)/計算冒泡排序算

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

15、n"); printf("(5)快速排序n"); printf("(6)時間效率比較n"); printf("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

16、(p=0) printf("謝謝使用!n"); getchar(); break; double TIMES5,TIMES15;/時間數(shù)組 switch(p) case 1: Disp(a); FILE *fp; fp=fopen("隨機數(shù).txt","w"); for(i=0; i<N; i+)fprintf(fp,"%d ",ai); fclose(fp); getchar(); printf("n請按任意鍵繼續(xù)!"); getchar(); break; case 2: TInser

17、tSort(a,p); printf("n請按任意鍵繼續(xù)!"); getchar(); break; case 3: TSelectSort(a,p); printf("n請按任意鍵繼續(xù)!"); getchar(); break; case 4: TBubbleSort(a,p); printf("n請按任意鍵繼續(xù)!"); getchar(); break; case 5: Tquicksort(a,N,p); printf("n請按任意鍵繼續(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