五種排序算法分析

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

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

3、的隨機(jī)數(shù)組都是一樣的，將srand(unsigned)time(NULL)語(yǔ)句放在for循環(huán)外面，就產(chǎn)生了20組不同的隨機(jī)數(shù)組。圖1、產(chǎn)生20組隨機(jī)數(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ī)模下排序所消耗的時(shí)間3、冒泡排序代碼3：for i= 0 to n-1for j=0 to n-1-iif aj>aj+1swap(aj,aj+1) /交換圖3、冒泡排序在不同數(shù)據(jù)規(guī)模下排序所消耗的時(shí)間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ī)模下排序所消耗的時(shí)間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) / 遞歸調(diào)用 quick(ele,l+1,right)圖5、快速排序在不同數(shù)據(jù)規(guī)模下排序所消耗的時(shí)間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ī)模下排序所消耗的時(shí)間三實(shí)驗(yàn)分析選擇排序： 圖7、由圖2數(shù)據(jù)整合而成的折線圖 表1、選擇排序在不同數(shù)據(jù)規(guī)模下排序所消耗的時(shí)間數(shù)據(jù)規(guī)模：10100100010000100000耗時(shí)（ms）002.05195.2519868.5圖形上：形狀基本符合n2（二次增長(zhǎng)）數(shù)據(jù)上：我們發(fā)現(xiàn)當(dāng)數(shù)據(jù)規(guī)模增大10倍時(shí)： 100010000： 195.25/2.05=95.24100 10000100000：19868.5/195.25=101.75100其他倍數(shù)也可得到類似的結(jié)果。結(jié)論

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

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

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

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

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

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

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

14、注：1、報(bào)告內(nèi)的項(xiàng)目或內(nèi)容設(shè)置，可根據(jù)實(shí)際情況加以調(diào)整和補(bǔ)充。2、教師批改學(xué)生實(shí)驗(yàn)報(bào)告時(shí)間應(yīng)在學(xué)生提交實(shí)驗(yàn)報(bào)告時(shí)間后10日內(nèi)。附錄：代碼#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/*生成隨機(jī)函數(shù)*/void randNum(

15、int MAX,int *array)/srand(unsigned)time(NULL);/cout<<"生成的隨機(jī)數(shù)為："<<endl;for(int i=0;i<MAX;i+)arrayi = rand()%100; /cout<<arrayi<<" "/cout<<"tt耗時(shí)："/*選擇排序*/ 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);/遞歸調(diào)用 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;/將比第一個(gè)小的數(shù)移到后面 while(first < last && afirst <= key) +first; alast = afirst; /將比第一個(gè)大的數(shù)移到前面 afirst = key;/記錄當(dāng)前位置 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)/產(chǎn)生隨機(jī)數(shù)組 clock_t time_start,time_end;double time_used = 0,count = 0;int MAX = 10;int arrayARRA

21、Y_MAX;cout<<"ntt請(qǐng)輸入序號(hào)選擇相應(yīng)的操作："<<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+)/控制問(wèn)題規(guī)模MAX從10-100000 cout<<"數(shù)組規(guī)模 MAX=&

22、quot;<<MAX<<" 時(shí),耗時(shí)："<<endl; srand(unsigned)time(NULL);for(int i=0;i<20;i+)/控制20組隨機(jī)數(shù)產(chǎn)生 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選擇排序平均耗時(shí)："<<count/20<<"毫秒"<<endl<<endl;count = 0; MAX *= 10;break;case 2: for(int j=0;j<5;j+)/控制問(wèn)題規(guī)模MAX從10-100000 cout<<"數(shù)組規(guī)模 MAX="<<MAX<<" 時(shí),耗時(shí)："<<endl; srand(unsigned)time(NULL);for

24、(int i=0;i<20;i+)/控制20組隨機(jī)數(shù)產(chǎn)生 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冒泡排序平均耗時(shí)："<<count/20<<"毫秒"&

25、lt;<endl<<endl;count = 0; MAX *= 10;break;case 3: for(int j=0;j<5;j+)/控制問(wèn)題規(guī)模MAX從10-100000 cout<<"數(shù)組規(guī)模 MAX="<<MAX<<" 時(shí),耗時(shí)："<<endl; srand(unsigned)time(NULL);for(int i=0;i<20;i+)/控制20組隨機(jī)數(shù)產(chǎn)生 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合并排序平均耗時(shí)："<<count/20<<"毫秒"<<endl<<endl;count = 0; MAX *= 10;break;case 4: for(int l=0;l<5;l+)/控制問(wèn)題規(guī)模MAX從10-100000 cout<<"數(shù)組規(guī)模 MAX="<<MAX<<" 時(shí),耗時(shí)："<<endl; srand(unsigned)time(NULL);for(int i=0;i<20;i+)/控制20組隨機(jī)數(shù)產(chǎn)生 ra