深圳大學(xué)算法設(shè)計(jì)與楊煊實(shí)驗(yàn)一

1、深 圳 大 學(xué) 實(shí) 驗(yàn) 報(bào) 告 課程名稱： 算法設(shè)計(jì)與分析 實(shí)驗(yàn)項(xiàng)目名稱： 排序算法性能分析 學(xué)院： 專業(yè)、班級(jí)： 指導(dǎo)教師： 楊 烜 報(bào) 告 人： 學(xué)號(hào)： 實(shí)驗(yàn)報(bào)告提交時(shí)間： 2015.4.3 教務(wù)處制一、實(shí)驗(yàn)?zāi)康呐c實(shí)驗(yàn)環(huán)境 實(shí)驗(yàn)?zāi)康模?1. 掌握選擇排序、冒泡排序、合并排序、快速排序、插入排序算法原理 2. 掌握不同排序算法時(shí)間效率的經(jīng)驗(yàn)分析方法，驗(yàn)證理論分析與經(jīng)驗(yàn)分析的一致性。 實(shí)驗(yàn)環(huán)境：VC+ 6.0 二、實(shí)驗(yàn)原理與算法描述 算法（1）選擇排序 SelectSort(A0.n-1,n) /利用選擇排序?qū)o定的數(shù)組排序 /輸入：一個(gè)可排序數(shù)組A0.n-1 /輸出：非降序排列的數(shù)組A0.n

2、-1for i<-0 to n-2 do min<-ifor j<-i+1 to n-1 do if Aj<Amin min<-jswap Ai and Amin理論效率：C(n) (n2),不穩(wěn)定算法 算法（2）快速排序 QuickSort(A0.n-1,n) /利用快速排序?qū)o定的數(shù)組排序 /輸入：一個(gè)可排序數(shù)組A0.n-1 /輸出：非降序排列的數(shù)組A0.n-1if l<r s<-Partition(Al.r) /s是分裂位置Quicksort(Al.s-1)Quicksort(As+1.r) Partition(Al.r) /以第一個(gè)數(shù)為中軸，對(duì)

3、子數(shù)組進(jìn)行分區(qū) /輸入：數(shù)組A0.n-1中的子數(shù)組Al.r，由左右下標(biāo)l和r定義 /輸出：數(shù)組Al.r的一個(gè)分區(qū)，分裂點(diǎn)的未知作為函數(shù)的返回值p<-Ali<-l;j<-r+1repeat repeat i<-i+1 until Ai>=P repeat j<-j-1 until Aj<=P swap(Ai,Aj)until i>=jswap (Ai,Aj) /當(dāng)i>=j撤銷最后一次交換swap (Al,Aj) return j理論效率：C(n) (nlnn)，不穩(wěn)定算法 算法（3）合并排序 MergeSort(A0.n-1) /利用合并排序

4、對(duì)給定的數(shù)組排序 /輸入：一個(gè)可排序數(shù)組A0.n-1 /輸出：非降序排列的數(shù)組A0.n-1if n>1 copy A0.n/2-1 to B0.n/2-1 copy An/2.n-1 to C0.n/2-1 Mergesort(B0.n/2-1) Mergesort(C0.n/2-1) Merge(B,C,A) Merge(B0.p-1,C0.q-1,A0.p+q-1) /將兩個(gè)有序數(shù)組合并為一個(gè)有序數(shù)組 /輸入：兩個(gè)有序數(shù)組B0.p-1,C0.q-1 /輸出：A0.p+q-1中已經(jīng)有序存放了B和C中的元素i<-0;j<-0;k<-0while i<p and j

5、<q do if Bi<=Cj Ak<-Bi;i<-i+1 else Ak<-Cj;j<-j+1 k<-k+1if i=p copy Cj.q-1 to Ak.p+q-1else copy Bi.p-1 to Ak.p+q-1理論效率：C(n)(nlogn)，穩(wěn)定算法 算法（4）冒泡排序 BubbleSort(A0.n-1) /利用冒泡排序?qū)o定的數(shù)組排序 /輸入：一個(gè)可排序數(shù)組A0.n-1 /輸出：非降序排列的數(shù)組A0.n-1for i<-0 to n-2 do for j<-0 to n-2-i do if Aj+1<Aj swa

6、p Aj and Aj+1理論效率：C(n)(n2)，穩(wěn)定算法 算法（5）插入排序 InsertSort(A0.n-1,n) /利用插入排序?qū)o定的數(shù)組排序 /輸入：一個(gè)可排序數(shù)組A0.n-1 /輸出：非降序排列的數(shù)組A0.n-1for k<-2 to n do A0<-Akj<-k-1while (j!=0 and Aj>A0) do Aj+1<-Aj j<-j-1 Aj+1<-A0理論效率：C(n)(n2)，穩(wěn)定算法三、實(shí)驗(yàn)代碼與運(yùn)行截圖 實(shí)驗(yàn)關(guān)鍵代碼：1. 選擇排序2. 快速排序3. 合并排序4. 冒泡排序5. 插入排序四、實(shí)驗(yàn)數(shù)據(jù)整理與分析 表

7、一 選擇排序輸入規(guī)模n與運(yùn)行時(shí)間統(tǒng)計(jì)圖n10100100010000100000t(Avg)/seclim->0lim->00.00200.179517.8550 表二 快速排序輸入規(guī)模n與運(yùn)行時(shí)間統(tǒng)計(jì)圖n10100100010000100000t(Avg)/seclim->0lim->00.00100.00200.0435 表三 合并排序輸入規(guī)模n與運(yùn)行時(shí)間統(tǒng)計(jì)圖n10100100010000100000t(Avg)/seclim->0lim->00.00050.00250.0260 表四 冒泡排序輸入規(guī)模n與運(yùn)行時(shí)間統(tǒng)計(jì)圖n101001000100001

8、00000t(Avg)/seclim->0lim->00.00250.355039.8810 表五 插入排序輸入規(guī)模n與運(yùn)行時(shí)間統(tǒng)計(jì)圖n10100100010000100000t(Avg)/seclim->0lim->00.00050.09008.9120 圖1. 選擇排序時(shí)間效率與輸入規(guī)模n的關(guān)系圖 圖2. 快速排序時(shí)間效率與輸入規(guī)模n的關(guān)系圖 圖3. 合并排序時(shí)間效率與輸入規(guī)模n的關(guān)系圖 圖4. 冒泡排序時(shí)間效率與輸入規(guī)模n的關(guān)系圖 圖5. 插入排序時(shí)間效率與輸入規(guī)模n的關(guān)系圖 圖6. 5種不同排序算法時(shí)間效率對(duì)比圖實(shí)驗(yàn)分析：1. 從實(shí)驗(yàn)結(jié)果可以看出，可以驗(yàn)證，當(dāng)規(guī)

9、模n趨向無窮大的時(shí)候，排序算法的效率關(guān)系為合并排序<快速排序<插入排序<選擇排序<冒泡排序。2. 從實(shí)驗(yàn)結(jié)果可以看出，當(dāng)輸入規(guī)模為100000時(shí)，合并排序所需時(shí)間僅為0.026sec，而冒泡排序則大概需要40sec,合并排序的效率大概是冒泡排序的1500倍，從理論分析來看，合并排序的時(shí)間復(fù)雜度為(nlogn)，而冒泡排序的時(shí)間復(fù)雜度為(n2),當(dāng)n取100000時(shí)，兩者比值大約為1500，因此可以看出，理論效率與實(shí)際效率比值基本一致。其余幾種排序算法的效率比較也和此相同。同時(shí)，這也正是合并排序和快速排序比冒泡排序和選擇排序效率高這么多的原因。3. 從算法實(shí)現(xiàn)的角度來看，

10、選擇排序和插入排序，都必須執(zhí)行n-1趟；當(dāng)冒泡排序處于最壞情況下時(shí)同樣需要進(jìn)行n-1趟，同時(shí)冒泡排序進(jìn)行第i趟排序需要做n-i次關(guān)鍵字的比較和交換；而選擇排序每趟執(zhí)行同樣要n-i-1次關(guān)鍵字的比較；插入排序每執(zhí)行一趟排序最多比較i次；因此，這三種排序算法效率相比快速排序和合并排序較慢也是意料之中的。4.實(shí)驗(yàn)測(cè)試結(jié)果與理論結(jié)果存在著差距，可能是因?yàn)闇y(cè)試組數(shù)較少，實(shí)驗(yàn)所得數(shù)據(jù)較少，因此造成數(shù)據(jù)統(tǒng)計(jì)以及作圖不準(zhǔn)確，造成一定的誤差。5.不同計(jì)算機(jī)的硬件系統(tǒng)不同，不同計(jì)算機(jī)的性能不同，因此造成不同時(shí)間測(cè)試數(shù)據(jù)的微弱差距。五、實(shí)驗(yàn)結(jié)論與實(shí)驗(yàn)總結(jié) 實(shí)驗(yàn)結(jié)論：5種不同的算法都能實(shí)現(xiàn)排序，但效率不盡相同。從比較可以看出，當(dāng)輸入規(guī)模n比較小是，各個(gè)算法的優(yōu)劣體現(xiàn)的并不明顯，當(dāng)規(guī)模n達(dá)到一定程度時(shí)，不同算法之間的不同效率就明顯的體現(xiàn)出來了。實(shí)際效率與理論效