五種排序算法分析

1、深 圳 大 學 實 驗 報 告 課程名稱： 算法分析與復雜性理論 實驗項目名稱： 實驗一 排序算法性能分析 學院： 計算機與軟件學院 專業(yè)： 軟件工程 指導教師： 楊烜 報告人：賴輝 學號： 班級： 軟工學術型 實驗時間： 2015-10-15 實驗報告提交時間： 2015-11-24 教務部制一實驗目的1. 掌握選擇排序、冒泡排序、合并排序、快速排序、插入排序算法原理2. 掌握不同排序算法時間效率的經驗分析方法，驗證理論分析與經驗分析的一致性。二實驗步驟與結果實驗總體思路：根據(jù)實驗要求，需要用while循環(huán)控制用戶選擇相應算法(選擇通過switch實現(xiàn))或者選擇輸入0跳出while循環(huán)，退出

2、程序。Switch中選擇相應的算法后需要通過一個for(int j=0;j<5;j+)循環(huán)更改數(shù)組大小MAX的值(MAX *= 10)，從而控制輸入不同問題規(guī)模的耗時。再通過一個for(int i=0;i<20;i+)循環(huán)控制20組隨機數(shù)組。為了使得程序輸出更加直觀，部分數(shù)據(jù)后面沒有輸出。相應結果和過程如下所示（代碼和結果如下圖所示）。各排序算法的實現(xiàn)及實驗結果：1、 隨機數(shù)產生代碼1：srand(unsigned)time(NULL);For i=0 to 19randNum(MAX,array);當問題規(guī)模較小時，生成隨機函數(shù)randNum()在for循環(huán)下運行時間短，每次產生

3、的隨機數(shù)組都是一樣的，將srand(unsigned)time(NULL)語句放在for循環(huán)外面，就產生了20組不同的隨機數(shù)組。圖1、產生20組隨機數(shù)組2、選擇排序代碼2：for i=0 to n-2min=ifor j= i+1 to n-1if elemin>elej min=jswap(elei,elemin) /交換元素 圖2、選擇排序在不同數(shù)據(jù)規(guī)模下排序所消耗的時間3、冒泡排序代碼3：for i= 0 to n-1for j=0 to n-1-iif aj>aj+1swap(aj,aj+1) /交換圖3、冒泡排序在不同數(shù)據(jù)規(guī)模下排序所消耗的時間3、合并排序代碼4：MERG

4、E(A, p, q, r) n1 q - p + 1 n2 r - q create arrays L1 n1 + 1 and R1 n2 + 1 for i 1 to n1 do Li Ap + i - 1 for j 1 to n2 do Rj Aq + j Ln1 + 1 Rn2 + 1 i 1 j 1 for k p to r do if Li Rj then Ak Li i i + 1 else Ak Rj j j + 1 圖4、合并排序在不同數(shù)據(jù)規(guī)模下排序所消耗的時間4、快速排序代碼5：quick(ele0.n-1,left,right)if l<rlleft rright

5、xelel;while l<r while l<r && x<=eler /比x小則之后交換到前面的部分r- if l<r eleleler l+ while l<r && x>elel /比x大則前面交換到后面部分ll+if l<r elerelel r- elelx; quick(ele,left,l-1) / 遞歸調用 quick(ele,l+1,right)圖5、快速排序在不同數(shù)據(jù)規(guī)模下排序所消耗的時間5、插入排序代碼6：for i=1n-1 if elei<elei-1 temp=eleifor j= i

6、-1 to 0 && elej>temp elej+1elej elej+1temp圖6、插入排序在不同數(shù)據(jù)規(guī)模下排序所消耗的時間三實驗分析選擇排序： 圖7、由圖2數(shù)據(jù)整合而成的折線圖 表1、選擇排序在不同數(shù)據(jù)規(guī)模下排序所消耗的時間數(shù)據(jù)規(guī)模：10100100010000100000耗時（ms）002.05195.2519868.5圖形上：形狀基本符合n2（二次增長）數(shù)據(jù)上：我們發(fā)現(xiàn)當數(shù)據(jù)規(guī)模增大10倍時： 100010000： 195.25/2.05=95.24100 10000100000：19868.5/195.25=101.75100其他倍數(shù)也可得到類似的結果。結論

7、：當數(shù)據(jù)規(guī)模為10和100時因為數(shù)據(jù)太小，耗時約為0。但當數(shù)據(jù)規(guī)模為1000增大到10000時，并10000到100000時，規(guī)模增大10倍耗時都增大約100倍，可以計算出，選擇排序的時間復雜度為o（n2）。冒泡排序：圖8、由圖3數(shù)據(jù)整合而成的折線圖 表2、冒泡排序在不同數(shù)據(jù)規(guī)模下排序所消耗的時間數(shù)據(jù)規(guī)模：10100100010000100000耗時（ms）00.12194.1519708圖形上：形狀基本符合n2（二次增長）數(shù)據(jù)上：我們發(fā)現(xiàn)當數(shù)據(jù)規(guī)模增大10倍時： 1001000：2/0.1=20 （誤差太大）100010000:194.15/2=97.075 10010000100000:1

8、9708/194.15=101.5 100其他倍數(shù)也可得到類似的結果。結論：由于開始問題規(guī)模較小，產生誤差較大，但隨著問題規(guī)模的按10的倍數(shù)增大，耗時逐漸呈100的倍數(shù)增大，分析偽代碼也可以算出該算法的時間復雜度為o（n2）。隨著問題規(guī)模的增大，多種誤差會逐漸累積，耗時會超過o（n2）的倍數(shù)，但是整體上不會相差太大。與此相比，電腦等其他因素造成輕微的誤差可以忽略不計。合并排序：圖9、由圖4數(shù)據(jù)整合而成的折線圖表3、合并排序在不同數(shù)據(jù)規(guī)模下排序所消耗的時間數(shù)據(jù)規(guī)模：10100100010000100000耗時（ms）00.10.76.0559.2圖形上：形狀基本符合n（線性增長）數(shù)據(jù)上：我們發(fā)現(xiàn)

9、當數(shù)據(jù)規(guī)模增大10倍時： 1001000：:0.7/0.1=7 10（誤差較大）100010000： 6.05/0.7=8.64 1010000100000：59.2/6.05=9.78 10其他倍數(shù)也可得到類似的結果。結論：根據(jù)該算法的偽代碼，可以計算出時間復雜度為o（nlog2n），當數(shù)據(jù)規(guī)模擴大10倍時，耗時呈線性增長，逐漸接近于n。當數(shù)據(jù)規(guī)模擴大n倍時，相應的在時間的消耗上會擴大nlog2n倍，同時我們發(fā)現(xiàn)，理論上乘以nlog2n后的數(shù)據(jù)普遍會略小于實際數(shù)據(jù)，這主要原因快速排序需要遞歸調用，遞歸調用需要花費額外的時間?？焖倥判颍簣D10、由圖5數(shù)據(jù)整合而成的折線圖表4、快速排序在不同數(shù)據(jù)

10、規(guī)模下排序所消耗的時間數(shù)據(jù)規(guī)模：10100100010000100000耗時（ms）001.512.15137.95圖形上：形狀基本符合n（線性增長）數(shù)據(jù)上：我們發(fā)現(xiàn)當數(shù)據(jù)規(guī)模增大10倍時：100010000：:12.15/1.5=8.1 1010000100000： 137.95/12.15=10.1 10 其他倍數(shù)也可得到類似的結果。結論：根據(jù)快速排序算法的偽代碼，可以分析出該算法的時間復雜度是o（nlog2n），當數(shù)據(jù)規(guī)模擴大n倍時，相應的在時間的消耗上會擴大nlog2n倍。從實驗的數(shù)據(jù)上，可以看出隨著問題規(guī)模的增大，耗時上面也呈線性增長，但累積起來的誤差也使得程序的結果略微高于實驗值。

11、總體上的實驗結果和預期還是很接近的。插入排序：圖11、由圖6數(shù)據(jù)整合而成的折線圖表5、插入排序在不同數(shù)據(jù)規(guī)模下排序所消耗的時間數(shù)據(jù)規(guī)模：10100100010000100000耗時（ms）001.2112.8511329.5圖形上：形狀基本符合n2（二次增長）數(shù)據(jù)上：我們發(fā)現(xiàn)當數(shù)據(jù)規(guī)模增大10倍時： 100010000： 112.85/1.2=94 100 10000100000： 11329.5/112.85=100.4 100其他倍數(shù)也可得到類似的結果。結論：根據(jù)插入算法的偽代碼，可以計算出該算法的時間復雜度是o（n2），當數(shù)據(jù)規(guī)模擴大n倍時，相應的在時間的消耗上會擴大n2倍，理論上，如果

12、數(shù)據(jù)大具有特殊性，那此算法被影響的程度會比較大，他的的比較次數(shù)可以從線性次數(shù)，到n2次，賦值次數(shù)也可能由常數(shù)次變成n2總的來說，受數(shù)據(jù)影響較大。將五種排序的實驗匯總在一起，如下圖12所示圖12、由圖7、8、9、10、11整合而來從圖中以及之前的分析中我們可以得到以下結論1、在平均時間復雜度上面，冒泡排序、插入排序和選擇排序都最差為o（n2）。其主要原因是：隨著問題規(guī)模的增大，冒泡排序在比較次數(shù)上達到了o（n2），但這種排序同時也受交換次數(shù)的影響，而且最多時間復雜度也是o（n2）。如此，同樣是o（n2），但冒泡排序的二次項系數(shù)會比另外兩個大不少，所以最為耗時。 2、快速排序和合并排序都表現(xiàn)出比較

13、好的復雜度。但這兩者中，合并排序表現(xiàn)更好。其原因是：在最壞情況下，即整個序列都已經有序且完全倒序的情況下，快速排序呈o（n2）的增長，而歸并排序不管在什么情況下都呈o（nlog2n），隨著問題規(guī)模的增大，快速排序逐漸體現(xiàn)出這種弊端。四實驗心得本次實驗雖然花費很大的心思，但確實讓我對這幾種排序的認識更加深刻，同樣的數(shù)據(jù)，排序的時間可以相差如此之大，這可能會改變我每次都使用冒泡排序的這一習慣，同時，對算法的優(yōu)良性不同而導致的結果差異之大，感覺到好的算法是多么的重要，當然合理利用算法也是不可忽視的。這次實驗雖然花了很大精力，卻收獲累累。 指導教師批閱意見：成績評定： 指導教師簽字： 年 月 日備注：

14、注：1、報告內的項目或內容設置，可根據(jù)實際情況加以調整和補充。2、教師批改學生實驗報告時間應在學生提交實驗報告時間后10日內。附錄：代碼#include<stdio.h>#include<iostream>#include<windows.h>#include <Mmsystem.h>using namespace std;#include <ctime>#include <fstream>using namespace std;#define ARRAY_MAX 100000/*生成隨機函數(shù)*/void randNum(

15、int MAX,int *array)/srand(unsigned)time(NULL);/cout<<"生成的隨機數(shù)為："<<endl;for(int i=0;i<MAX;i+)arrayi = rand()%100; /cout<<arrayi<<" "/cout<<"tt耗時："/*選擇排序*/ void select_sort(int MAX,int *array)int i, j, k;for (i = 0; i < MAX; i+)k = i;for

16、 (j = i + 1; j < MAX; j+)if (arrayj < arrayk)k = j;if (k != i)int temp = arrayk;arrayk = arrayi;arrayi = temp;/*冒泡排序*/void buddle_sort(int MAX,int *array)int i, j;for(i=0;i<MAX;i+)for(j=i+1;j<MAX;j+)if(arrayi>arrayj)swap(arrayi,arrayj);/*合并排序*/void Merge(int *array, int p, int q, int

17、r)int n1 = q - p + 1;int n2 = r - q;int *L, *R, i, j, k;L = new intn1 + 1;R = new intn2 + 1;for (i = 0; i < n1; i+)Li = arrayp + i;for (i = 0; i < n2; i+)Ri = arrayq + 1 + i;Ln1 = INT_MAX;Rn2 = INT_MAX;for (i = 0, j = 0, k = p; k <= r; k+)if (Li <= Rj)arrayk = Li+;elsearrayk = Rj+;delete

18、 L;delete R;void merge_sort(int *array, int p, int r)if (p < r)int q = (p + r) / 2;merge_sort(array, p, q);/遞歸調用 merge_sort(array, q + 1, r);Merge(array, p, q, r);elsereturn;/*快速排序*/void quick_sort(int a, int low, int high) if(low >= high) return; int first = low; int last = high; int key = af

19、irst; while(first < last) while(first < last && alast >= key) -last; afirst = alast;/將比第一個小的數(shù)移到后面 while(first < last && afirst <= key) +first; alast = afirst; /將比第一個大的數(shù)移到前面 afirst = key;/記錄當前位置 quick_sort(a, low, first-1); quick_sort(a, first+1, high); /*插入排序*/void ins

20、ert_sort(int MAX,int *array)int i, j, temp;for (i = 1; i < MAX; i+)temp = arrayi;for(j=i;j > 0 && arrayj-1 > temp;j-)arrayj = arrayj-1;arrayj = temp;int main()int n,loop = 1;while(loop != 0)/產生隨機數(shù)組 clock_t time_start,time_end;double time_used = 0,count = 0;int MAX = 10;int arrayARRA

21、Y_MAX;cout<<"ntt請輸入序號選擇相應的操作："<<endl;cout<<"1.選擇排序 2.冒泡排序 3.合并排序 4.快速排序 5.插入排序 0.退出程序"<<endl;cout<<"*"<<endl; cin>>n;switch(n)case 0: loop = 0;break;case 1: for(int j=0;j<5;j+)/控制問題規(guī)模MAX從10-100000 cout<<"數(shù)組規(guī)模 MAX=&

22、quot;<<MAX<<" 時,耗時："<<endl; srand(unsigned)time(NULL);for(int i=0;i<20;i+)/控制20組隨機數(shù)產生 randNum(MAX,array);time_start = clock();select_sort(MAX,array);time_end = clock();time_used = time_end - time_start;cout<<time_used<<" "/cout<<endl;count +

23、= time_used;cout<<"n選擇排序平均耗時："<<count/20<<"毫秒"<<endl<<endl;count = 0; MAX *= 10;break;case 2: for(int j=0;j<5;j+)/控制問題規(guī)模MAX從10-100000 cout<<"數(shù)組規(guī)模 MAX="<<MAX<<" 時,耗時："<<endl; srand(unsigned)time(NULL);for

24、(int i=0;i<20;i+)/控制20組隨機數(shù)產生 randNum(MAX,array);time_start = clock();buddle_sort(MAX,array);time_end = clock();time_used = time_end - time_start;cout<<time_used<<" "/cout<<endl;count += time_used;cout<<"n冒泡排序平均耗時："<<count/20<<"毫秒"&

25、lt;<endl<<endl;count = 0; MAX *= 10;break;case 3: for(int j=0;j<5;j+)/控制問題規(guī)模MAX從10-100000 cout<<"數(shù)組規(guī)模 MAX="<<MAX<<" 時,耗時："<<endl; srand(unsigned)time(NULL);for(int i=0;i<20;i+)/控制20組隨機數(shù)產生 randNum(MAX,array);time_start = clock();merge_sort(ar

26、ray,0,MAX-1);time_end = clock();time_used = time_end - time_start;cout<<time_used<<" "/cout<<endl;count += time_used;cout<<"n合并排序平均耗時："<<count/20<<"毫秒"<<endl<<endl;count = 0; MAX *= 10;break;case 4: for(int l=0;l<5;l+)/控制問題規(guī)模MAX從10-100000 cout<<"數(shù)組規(guī)模 MAX="<<MAX<<" 時,耗時："<<endl; srand(unsigned)time(NULL);for(int i=0;i<20;i+)/控制20組隨機數(shù)產生 ra