算法設(shè)計實(shí)驗(yàn)報告一

1、計算機(jī)算法設(shè)計與分析實(shí) 驗(yàn) 報 告實(shí)驗(yàn)名稱：排序算法效率比較實(shí)驗(yàn)地點(diǎn)：所使用的開發(fā)工具及環(huán)境：1、 實(shí)驗(yàn)?zāi)康模罕容^至少4種排序算法的執(zhí)行效率。已學(xué)過的算法：起泡排序、選擇排序、插入排序、shell排序，歸并排序、快速排序等。二、實(shí)驗(yàn)內(nèi)容：1、從中選擇至少4中排序算法，寫成獨(dú)立的函數(shù)進(jìn)行調(diào)用。2、參與排序的數(shù)據(jù)不少于10000個，要求用數(shù)據(jù)文件存儲隨機(jī)產(chǎn)生的數(shù)據(jù)。3、要求在main()函數(shù)中調(diào)用以上函數(shù)，并輸出各排序算法所用時間。3、 基本思想、原理和算法描述： 本次實(shí)驗(yàn)要求寫出四種算法，來比較它們運(yùn)行的時間。冒泡排序：總的時間復(fù)雜度為O(n).基本思想：首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)

2、鍵字進(jìn)行比較，若為逆序，則將兩個記錄交換，然后比較第二個記錄和第三個記錄的關(guān)鍵字。依此類推，直到第n-1和第n個的關(guān)鍵字進(jìn)行比較為止。算法描述：void BubbleSort(int r,int length) /冒泡排序int i,j,temp;for(j=length;j>0;j-)for(i=0;i<j-1;i+)if(ri>ri+1)temp=ri;ri=ri+1;ri+1=temp; 簡單選擇排序：總的時間復(fù)雜度為O(n2)基本思想：通過n-i次關(guān)鍵字的比較，從n-i+1個記錄中選取出關(guān)鍵字最小的記錄并和第i個記錄交換。算法描述：void SelectSort(in

3、t r,int length) /簡單選擇排序int i,j,k;int x; for (i=1;i<=length-1;+i)k=i;for(j=i+1;j<=length;+j)if(rj<rk)k=j;if( k!=i)x= ri;ri=rk;rk=x;插入排序：總的時間復(fù)雜度為：O(n2)算法描述：void InsertSort(int r,int length) /插入排序int i,j;for (i=0;i<=length;i+)r0=ri;j=i-1;while(r0<rj)rj+1=rj;j=j-1;rj+1=r0;快速排序：總的時間復(fù)雜度為O(n

4、log2n)基本思想：通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分的記錄繼續(xù)進(jìn)行排序，直到整個序列有序。算法描述：void QuickSort(int A,int low,int r)/快速排序if(low<r)int high = Partition(A,low,r); QuickSort(A,low,high-1);QuickSort(A,high+1,r);4、 源程序清單：#include<stdio.h>#include<stdlib.h>#include<time.h>#includ

5、e<windows.h>#define MAX 10000void BubbleSort(int r,int length) /冒泡排序int i,j,temp;for(j=length;j>0;j-)for(i=0;i<j-1;i+)if(ri>ri+1)temp=ri;ri=ri+1;ri+1=temp; void SelectSort(int r,int length) /簡單選擇排序int i,j,k;int x;for (i=1;i<=length-1;+i)k=i;for(j=i+1;j<=length;+j)if(rj<rk)k=j

6、;if( k!=i)x= ri;ri=rk;rk=x; void InsertSort(int r,int length) /插入排序int i,j;for (i=0;i<=length;i+)r0=ri;j=i-1;while(r0<rj)rj+1=rj;j=j-1;rj+1=r0;int Partition(int A,int low,int high)int i,j,x,t;x = Ahigh;i = low-1;for (j = low;j<=high;j+)if(Aj < x)i+;t = Aj;Aj = Ai;Ai = t; Ahigh = Ai+1;Ai+

7、1 = x; return i+1;void QuickSort(int A,int low,int r)/快速排序if(low<r)int high = Partition(A,low,r); QuickSort(A,low,high-1);QuickSort(A,high+1,r);void main()long iStart,iStop,runtime;int numMAX, aMAX;int i,j;iStart=GetTickCount();srand(unsigned)time(NULL);for(i=0;i<MAX;i+)numi=rand();iStop=GetTi

8、ckCount();runtime=iStop-iStart;printf("生成%d個隨機(jī)數(shù)用了%ldmsn",MAX, runtime);printf("-n");for(i=0;i<MAX;i+)ai=numi;iStart=GetTickCount();BubbleSort(a,MAX);iStop=GetTickCount();runtime=iStop-iStart;printf("使用冒泡排序用了%ldmsn",runtime);for(i=0;i<MAX;i+)ai=numi;iStart=GetTickC

9、ount();SelectSort(a,MAX);iStop=GetTickCount();runtime=iStop-iStart;printf("使用簡單選擇排序用了%ldmsn",runtime);for(i=0;i<MAX;i+)ai=numi;iStart=GetTickCount();InsertSort(a,MAX);iStop=GetTickCount();runtime=iStop-iStart;printf("使用插入排序用了%ldmsn",runtime);for(i=0;i<MAX;i+)ai=numi;iStart=GetTickCount();QuickSort(a,1,MAX);iStop=GetTickCount();runtime=iStop-iStart;printf("使用快速排序用了%ldmsn",runtime); 5、 程序運(yùn)行結(jié)果（包括上機(jī)調(diào)試的情況、調(diào)試所遇到的問題是如何解決的，并對調(diào)試過程中的問題進(jìn)行分析，對執(zhí)行結(jié)果進(jìn)行分析。）： 最主要的就是怎樣產(chǎn)生不同的隨機(jī)數(shù)，并且還要記錄下排序前后的時間。最后就是在快速排序的時候有點(diǎn)問題。不過經(jīng)過查資料和多次調(diào)試，問題基本得到解決六、實(shí)驗(yàn)總結(jié)： 在本次實(shí)驗(yàn)中要求