實驗報告
一、 實驗目的
在電腦科學與數學中，排序演算法是一種基本並且常用的演算法，乙個排序演演算法是一種能將一串資料依照特定排序方式的一種演演算法。有效的排序演演算法在一些演演算法中是重要的，如此這些演演算法才能得到正確解答。排序演演算法也用在處理文字資料以及產生人類可讀的輸出結果。
由於實際工作中處理的數量巨大，所以排序演算法對演算法本身的速度要求很高。通過實現相關一些排序演算法，加深對於演算法知識的理解與學習。
二、 實驗題目
要求實現合併排序，插入排序，希爾排序，快速排序，氣泡排序，桶排序演算法，並比較這些演算法的效能。
三、 實驗要求
（一）在隨機產生的空間大小分別為 n = 10， 1000，10000，100000 的排序樣本（取值為[0,1]）上測試以上演算法。
（二）結果輸出:
1） n=10時，排序結果。
2） n=1000，10000，100000時，對同乙個樣本例項，不同排序完成所需的時間。
3） n=1000，10000，100000時，每個排序用不同的樣本多試驗幾次（最低5次）得出平均時間，比較不同排序演算法所用的平均時間。
四、 實驗內容
◆ 各種排序演算法相關**的實現及其原理說明如下：
1. 合併排序
對於合併排序，演算法過程說明如下：
設兩個有序的子檔案(相當於輸入堆)放在同一向量中相鄰的位置上：r[low..m]，r[m+1..
high]，先將它們合併到乙個區域性的暫存向量r1(相當於輸出堆)中，待合併完成後將r1複製回r[low..high]中。
合併過程中，設定i，j和p三個指標，其初值分別指向這三個記錄區的起始位置。合併時依次比較r[i]和r[j]的關鍵字，取關鍵字較小的記錄複製到r1[p]中，然後將被複製記錄的指標i或j加1，以及指向複製位置的指標p加1。
重複這一過程直至兩個輸入的子檔案有乙個已全部複製完畢，此時將另一非空的子檔案中剩餘記錄依次複製到r1中即可。
2.插入排序
關於直接插入排序的演算法說明如下：
假設待排序的記錄存放在陣列r[1..n]中。初始時，r[1]自成1個有序區，無序區為r[2..
n]。從i=2起直至i=n為止，依次將r[i]插入當前的有序區r[1..i-1]中，生成含n個記錄的有序區。
直接插入排序是由兩層巢狀迴圈組成的。外層迴圈標識並決定待比較的數值。內層迴圈為待比較數值確定其最終位置。
直接插入排序是將待比較的數值與它的前乙個數值進行比較，所以外層迴圈是從第二個數值開始的。當前一數值比待比較數值大的情況下繼續迴圈比較，直到找到比待比較數值小的並將待比較數值置入其後一位置，結束該次迴圈。
3.希爾排序
關於希爾排序演算法的說明如下：
先取乙個小於n的整數d1作為第乙個增量，把檔案的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同乙個組中。先在各組內進行直接插人排序；然後，取第二個增量d24.快速排序
對於快速排序演算法說明如下：
第一步：(初始化)設定兩個指標i和j，它們的初值分別為區間的下界和上界，即i=low，i=high；選取無序區的第乙個記錄r[i](即r[low])作為基準記錄，並儲存下來；
第二步：令j自high起向左掃瞄，直到找到第1個關鍵字小於基準關鍵字的記錄r[j]，將r[j])移至i所指的位置上，這相當於r[j]和基準元素r[i]進行了交換，使關鍵字小於基準關鍵字的記錄移到了基準的左邊，交換後r[j]中相當於是基準元素；然後，令i指標自i+1位置開始向右掃瞄，直至找到第1個關鍵字大於基準關鍵字的記錄r[i]，將r[i]移到i所指的位置上，這相當於交換了r[i]和基準r[j]，使關鍵字大於基準關鍵字的記錄移到了基準的右邊，交換後r[i]中又相當於存放了基準元素；接著令指標j自位置j-1開始向左掃瞄，如此交替改變掃瞄方向，從兩端各自往中間靠攏，直至i=j時，i便是基準元素最終的位置，將基準元素放在此位置上就完成了一次劃分。
5.氣泡排序
對於氣泡排序的說明如下：
依次比較相鄰的兩個數，將小數放在前面，大數放在後面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放後。
然後比較第2個數和第3個數，將小數放前，大數放後，如此繼續，直至比較最後兩個數，將小數放前，大數放後。至此第一趟結束，將最大的數放到了最後。在第二趟：
仍從第一對數開始比較（因為可能由於第2個數和第3個數的交換，使得第1個數不再小於第2個數），將小數放前，大數放後，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到乙個新的最大數（其實在整個數列中是第二大的數）。如此下去，重複以上過程，直至最終完成排序。
6.桶排序
對於桶排序演算法，說明如下：
桶排序的思想是把[0，1)劃分為n個大小相同的子區間，每一子區間是乙個桶。然後將n個記錄分配到各個桶中。因為關鍵字序列是均勻分布在[0，1)上的，所以一般不會有很多個記錄落入同乙個桶中。
由於同一桶中的記錄其關鍵字不盡相同，所以必須採用關鍵字比較的排序方法(通常用插入排序)對各個桶進行排序，然後依次將各非空桶中的記錄連線起來即可。
◆ 實驗執行結果
先產生十個隨機數，測試個演算法的輸出，驗證功能是否正常。執行後介面顯示如下：
● 隨機數產生介面
● 產生了10個隨機數之後，依次選擇不同的演算法，排序後輸出，看結果是否顯示正常，介面如下：
對於桶排序，這裡為了計算排序時間的準確性，暫時沒有輸出，因為桶排序的輸出和其他的輸出不一樣，其他排序的輸出直接呼叫了myprint輸出函式，但對於桶排序，它的輸出要在排序之後利用當時的結構輸出，這樣會影響到後面時間計算的準確性（因為會讓計算時間誤加上輸出的時間）。為了單獨驗證桶排序的正確性，重新生成隨機數，特讓其輸出一次，截圖如下：
總結：由以上六種演算法對隨機產生的10個數排序，均正確。可見個排序演算法是正確的。
n=1000，10000，50000，60000時，對同乙個樣本例項，不同排序完成時間的統計，如下所示：（100000數字太多，系統總是出錯，故沒取）
● 先隨機產生1000個隨機數，然後排序，花費時間如下：
● 接著重新隨機產生10000個隨機數，然後排序，花費時間如下：
● 重新產生50000個隨機數，然後分別排序，花費時間如下：
● 重新產生60000個隨機數，然後分別排序，話費時間如下：
● n=1000，10000，50000時，每個排序用不同的樣本多試驗5次後得出平均時間，比較不同排序演算法所用的平均時間。
對於這一項，平均執行時間列表如下：（單位：毫秒）
對於最後一行，平均時間一次為合併/插入/希爾/快速/冒泡/桶排序的平均時間，前六行用「/」隔開的依次為各排序演算法對於固定數量的隨機數排序5次試驗所花費的時間。
五、 實驗分析及總結
根據以上結果，可見，快速排序和希爾排序是屬於其中比較好的排序方式，總結以及參考借鑑相關資料之後，列出各排序演算法的時間複雜度以及效能優劣如下圖所示：
各種排序演算法按平均時間將排序分為四類：
（1） 平方階(o(n2))排序
一般稱為簡單排序，例如直接插入和氣泡排序；
（2） 線性對數階(o(nlgn))排序
如快速和合併排序；
（3） o(n1+￡)階排序
￡是介於0和1之間的常數，即0<￡<1，如希爾排序；
（4） 線性階(o(n))排序
如桶排序。
各種排序方法比較
簡單排序中直接插入最好，快速排序最快，當檔案為正序時，直接插入和冒泡均最佳。
影響排序效果的因素
因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法應綜合考慮下列因素：
①待排序的記錄數目n；
②記錄的大小(規模)；
③關鍵字的結構及其初始狀態；
④對穩定性的要求；
⑤語言工具的條件；
⑥儲存結構；
⑦時間和輔助空間複雜度等。
不同條件下，排序方法的選擇
(1) 若n較小(如n≤50)，可採用直接插入排序。當記錄規模較小時，直接插入排序較好。
(2)若檔案初始狀態基本有序(指正序)，則應選用直接插人、冒泡或快速排序為宜；
(3)若n較大，則應採用時間複雜度為o(nlgn)的排序方法：快速排序或合併排序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
若要求排序穩定，則可選用合併排序。
桶排序不常用，在這個實驗中，最終花費時間不太可觀。它最糟糕的時候，也要花費n的平方階時間。而且浪費儲存空間。
六、 實驗心得
這次實驗是《演算法導論》學習過程中布置的兩個實驗之一，主要是系統的學習以及實現了常用的一些排序演算法。這些演算法的學習，對於後續階段理論的學習非常重要，很有利於鍛鍊思維能力以及優化解題能力。
在做整個實驗的過程中，遇到過不少困難，對於各種演算法起先並不是很了解，於是花了大量時間在演算法原理的學習之上，也參閱學習了一些資料，收穫頗豐。
整個實驗做下來，收穫很大。對於計算機的學習有了比以往更濃的興趣，也希望今後能保持這種新鮮感和興趣，爭取更大的收穫。非常感謝這次實驗的機會！
資料結構實驗報告實驗六排序演算法
昆明理工大學資訊工程與自動化學院學生實驗報告 201 201 學年第一學期 課程名稱 資料結構開課實驗室年月日 一.實驗內容 排序演算法，包括直接插入排序，希爾排序，氣泡排序，快速排序，直接選擇排序，堆排序等等。二.實驗目的 1.掌握各種查詢演算法理解和實現 2.增強上機程式設計除錯能力 三.主要程...
中南大學演算法實驗報告
中南大學 演算法分析與設計 實驗報告 實驗一 歸併排序 編寫乙個簡單的程式，實現歸併排序 1 實驗目的 了解並熟練掌握歸併排序 2 實驗內容 給定乙個陣列，並使其按照所要求的顯示輸出 3 演算法思想分析 遞迴是簡單的方法，但是其不能很好的表示出歸併 非遞迴的方法能比較好的從底層開始顯示整個歸併排序的...
磁碟排程演算法實驗報告
作業系統實驗報告 實驗三 磁碟排程演算法 學生 俞澤濤 學號 201206090131 學院 電氣與資訊工程學院 系別 計算機系 專業 網路工程 實驗時間 2014年5月21日 報告時間 2014年5月25日 一 實驗內容 模擬電梯排程演算法，實現對磁碟的驅動排程。二 實驗目的 磁碟是一種高速 大量...