深圳大學算法設計與楊煊實驗一

1、深 圳 大 學 實 驗 報 告 課程名稱： 算法設計與分析 實驗項目名稱： 排序算法性能分析 學院： 專業(yè)、班級： 指導教師： 楊 烜 報 告 人： 學號： 實驗報告提交時間： 2015.4.3 教務處制一、實驗目的與實驗環(huán)境 實驗目的： 1. 掌握選擇排序、冒泡排序、合并排序、快速排序、插入排序算法原理 2. 掌握不同排序算法時間效率的經(jīng)驗分析方法，驗證理論分析與經(jīng)驗分析的一致性。 實驗環(huán)境：VC+ 6.0 二、實驗原理與算法描述 算法（1）選擇排序 SelectSort(A0.n-1,n) /利用選擇排序對給定的數(shù)組排序 /輸入：一個可排序數(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) /利用快速排序對給定的數(shù)組排序 /輸入：一個可排序數(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) /以第一個數(shù)為中軸，對

3、子數(shù)組進行分區(qū) /輸入：數(shù)組A0.n-1中的子數(shù)組Al.r，由左右下標l和r定義 /輸出：數(shù)組Al.r的一個分區(qū)，分裂點的未知作為函數(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) /當i>=j撤銷最后一次交換swap (Al,Aj) return j理論效率：C(n) (nlnn)，不穩(wěn)定算法 算法（3）合并排序 MergeSort(A0.n-1) /利用合并排序

4、對給定的數(shù)組排序 /輸入：一個可排序數(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) /將兩個有序數(shù)組合并為一個有序數(shù)組 /輸入：兩個有序數(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) /利用冒泡排序對給定的數(shù)組排序 /輸入：一個可排序數(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) /利用插入排序對給定的數(shù)組排序 /輸入：一個可排序數(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)定算法三、實驗代碼與運行截圖 實驗關鍵代碼：1. 選擇排序2. 快速排序3. 合并排序4. 冒泡排序5. 插入排序四、實驗數(shù)據(jù)整理與分析 表

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

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

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

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