幾種排序算法的平均性能比較(實驗報告)

1、實驗課程：算法分析與設(shè)計(驗證型實驗)實驗名稱：幾種排序算法的平均性能比較 實驗目標：(1) 幾種排序算法在平均情況下哪一個更快。(2) 加深對時間復雜度概念的理解。實驗任務(wù)：(1) 實現(xiàn)幾種排序算法(selectionsort, insertionsort,bottomupsort,quicksort, 堆排序)。對于快 速分類，SPLIT中的劃分元素采用三者A(low), A(high), A( low+high)/2)中其值居中者。(2) 隨機產(chǎn)生20組數(shù)據(jù)(比如n=5000i, K i < 20)。數(shù)據(jù)均屬于圍(0, 105)的整數(shù)。對 于同一組數(shù)據(jù)，運行以上幾種排序算法，并記錄

2、各自的運行時間(以毫秒為單位)。(3) 根據(jù)實驗數(shù)據(jù)及其結(jié)果來比較這幾種分類算法的平均時間和比較次數(shù)，并得出結(jié)論。實驗設(shè)備及環(huán)境：PC; C/C+等編程語言。實驗主要步驟：(1) 明確實驗目標和具體任務(wù)；(2) 理解實驗所涉及的幾個分類算法；(3) 編寫程序?qū)崿F(xiàn)上述分類算法；(4) 設(shè)計實驗數(shù)據(jù)并運行程序、記錄運行的結(jié)果；(5) 根據(jù)實驗數(shù)據(jù)及其結(jié)果得出結(jié)論；(6) 實驗后的心得體會。問題分析(包括問題描述、建模、算法的基本思想及程序?qū)崿F(xiàn)的技巧等)：選擇排序：令A1n為待排序數(shù)組，利用歸納法，假設(shè)我們知道如何對后n-1個元素排序，即對啊An排序。對某個j,1<=j<=n,設(shè)Aj是最

3、小值。首先，如果就！=1,我們交換A1和Aj。然后由假設(shè)，已知如何對A2.n排序，因此可對在 A2n中的元素遞歸地排序?？砂堰f歸改為迭代。算法程序?qū)崿F(xiàn)如下：void SelectionSort( int *Array, int n, int &c)int i,j,k;int aa;c=0;for (i=0;i<n;i+)k=i;for (j=i+1;j<n;j+)c+;if (Arrayj<Arrayk)k=j;if (k!=i)aa=Arrayi;Arrayi=Arrayk;Arrayk=aa;插入排序：將 n 個元素的數(shù)列分為已有序和無序兩個部分， 每次處理就是將

4、無序數(shù)列的第 一個元素與有序數(shù)列的元素從后往前逐個進行比較，找出插入位置，將 該元素插入到有序 數(shù)列的合適位置中。算法程序?qū)崿F(xiàn)如下：void InsertionSort( int *Array, int n, int &c)int i,j;int aa;c=0;for (i=0;i<n;i+)aa=Arrayi;j=i-1;while (j>=0 && Arrayj>aa)c+;Arrayj+1=Arrayj;j=j-1;Arrayj+1=aa;自底向上合并排序： 利用分治法思想， 將兩個 (或兩個以上) 有序表合并成一個新的有序表， 即把待排序序列分

5、為若干個子序列， 每個子序列是有序的。 然后再把有序子序列合并為整體 有序 序列。 將已有序的子序列合并，得到完全有序的序列； 即先使每個子序列有序， 再使 子序列段間有序。算法程序?qū)崿F(xiàn)如下：void Merge( int *A, int p, int q, int r, int &c)int *B= new int r-p+1; int s=p;int t=q+1;int k=0;while (s<=q && t<=r) c+;if (As<=At)Bk=As;s=s+1;elseBk=At; t=t+1;k=k+1;if (s=q+1)while

6、(t<=r)Bk=At;k=k+1; t=t+1;elsewhile (s<=q)Bk=As;k=k+1;s=s+1;k=0;while (p<=r)Ap=Bk;k+;p+; delete B;void BottomupSort( int *Array, int n, int &c)int s,i, t=1;c=0;while (t<n)s=t;t=2*s;i=0;while (i+t<n)Merge(Array,i,i+s-1,i+t-1,c);i=i+t;if (i+s<n)Merge(Array,i,i+s-1,n-1,c);快速排序：設(shè)要排序

7、的數(shù)組是A0AN-1，首先任意選取一個數(shù)據(jù)(通常選用第一個數(shù)據(jù))作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速排序?？焖倥判蚓褪沁f歸調(diào)用此過程。算法程序?qū)崿F(xiàn)如下：void Split( int *A, int low, int high, int &w, int &c)int aa,x;int j,i=low;int mid=(low+high)/2;if (Alow<Ahigh)if (Amid<Alow)w=low;else if (Amid<Ahigh)w=mid;else w=high;elseif (

8、Amid<Ahigh)w=high;else if (Amid<Alow)w=mid;else w=low;c+;x=Aw;aa=Alow;Alow=Aw;Aw=aa;for (j=low+1;j<=high;j+)c+;if (Aj<=x)i=i+1;if (i!=j)aa=Ai;Ai=Aj;Aj=aa;aa=Alow;Alow=Ai;Ai=aa;w=i;void Quick( int *A, int low, int high, int &c)int w;if (low<high)Split(A,low,high,w,c);Quick(A,low,w-

9、1,c);Quick(A,w+1,high,c);void QuickSort( int *Array, int n, int &c)c=0;Quick(Array,0,n-1,c);堆排序： 堆排序利用了大根堆 ( 或小根堆 ) 堆頂記錄的關(guān)鍵字最大 ( 或最小 ) 這一特征， 使得在 當前無序區(qū)中選取最大 (或最小 )關(guān)鍵字的記錄變得簡單。 先將初始文件 R1.n 建成一個大根堆,此堆為初始的無序區(qū)， 再將關(guān)鍵字最大的記錄 R1（ 即堆頂 ）和無序區(qū)的最后一個記錄 Rn 交 換 ， 由 此 得 到 新 的 無 序 區(qū) R1.n-1和 有 序 區(qū) Rn ， 且 滿 足R1.n- 1.

10、keys < Rn.ke y,由于交換后新的根R1可能違反堆性質(zhì)，故應(yīng)將當前無序區(qū)R仁n-1調(diào)整為堆。然 后再次將R1.n-1中關(guān)鍵字最大的記錄 R1和該區(qū)間的最后一個 記錄 Rn-1 交換，由此得到新的無序區(qū) R1.n-2 和有序區(qū) Rn- 1.n ，且仍滿足關(guān)系R1. n- 2.keys < R n-1. n .keys，同樣要將R1. n-2 調(diào)整為堆。 直到無序區(qū)只有一個元素為止。void Siftdown( int *H, int n, int i, int &c) bool done= false ;int j,a;if (2*i+1>n) return

11、;while (2*i+1<=n && !done)j=i;i=2*i+1;c=c+2;if (i+1<=n && Hi+1>Hi)i=i+1;if (Hj<Hi)a=Hi;Hi=Hj;Hj=a;else done=true ;void MakeHeap(int *A, int n, int &c)int i;for (i=(n-2)/2;i>=0;i-)Siftdown(A,n-1,i,c);void HeapSort( int *A, int n, int &c)c=0;MakeHeap(A,n,c);int j

12、;int x;for (j=n-1;j>=1;j-)x=A0;A0=Aj;Aj=x;選擇排序合弄排序，決速排序3286928040&4463270482704-1801246041156622816577771019402運行時間100000生成隨機數(shù)Siftdow n(AA,j-1,0,c);實驗數(shù)據(jù)及其結(jié)果（可用圖表形式給出）輸入規(guī)模nselecti onin serti onbottomupquickHeap5000運行時間（毫秒）7878000數(shù)組兀素比較次數(shù)124975006200198568136318310774410000運行時間（毫秒）3122811600數(shù)組兀

13、素比較次數(shù)499950002520847512365813811123542420000運行時間（毫秒）1263112316016數(shù)組兀素比較次數(shù)1999900009975063926747630292351081230000運行時間（毫秒）28702527161615數(shù)組兀素比較次數(shù)44998500022497904141026846028980036640000運行時間（毫秒）52104509471516數(shù)組元素比較次數(shù)799980000402537541574791663812110117250000運行時間（毫秒）81747004471631數(shù)組元素比較次數(shù)12499750006260

14、68874733390866351140973420919201920920209202092120922209222092220923209232092420924*209242024209242092420925209252092620927209272Q927209272092720928202&20929汕92920929209302093020«02C9302093020530209312093120931209322093220933209332093320933209342093420934209342093420&3520935209362093720

15、93720937209372093S2Q93S2094 Q209402094120941209412094120942209432043209432094420945209452094520945209462094620948209482094820949209492049209502095 Q20951209512095220952209532095320954209542095520955209552095520955209552255209562095620957209572095720957209582095820958209592095920959209592095920960209

16、S02096120961209612Q96120962209622 09&22眈2209522095220963209632096320963209632Q964209642Q9672096720&68209682 09&820968209602096920969209692096920970209702097020?71209722097220972209722 0973209732Q9732Q973209742Q974209742097420975209752097520976209762097720977209772097820970209782097820978

17、209792097920980209B1209S1209812098220982209832090420W4209BS20996209B6209862098620986209862098720988209&02Q9S920網(wǎng)2058920990209902099120991209912099220992209922099220W2209922099J20993209032099J2099320993209932099420994209942099520996209962099620998209962099620999Z09992099920999| |同時運行比較次齣實驗結(jié)果分析及結(jié)論：選擇排序算法最穩(wěn)定， 算法的效率只跟輸入規(guī)模有關(guān)， 與元素序列無關(guān)， 但也是效率最 差。插入排序