北郵數(shù)據(jù)結構實驗報告排序

1、數(shù)據(jù)結構實驗報告實驗名稱： 實驗四排序學生姓名： 班 級： 班內序號： 學 號： 日 期： 2014年12月19日1實驗要求實驗目的通過實現(xiàn)下述實驗內容，學習、實現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。實驗內容使用簡單數(shù)組實現(xiàn)下面各種排序算法，并進行比較。排序算法： 1、插入排序 2、希爾排序3、冒泡排序4、快速排序5、簡單選擇排序6、堆排序（選作）7、歸并排序（選作）8、基數(shù)排序（選作）9、其他要求： 1、測試數(shù)據(jù)分成三類：正序、逆序、隨機數(shù)據(jù)2、對于這三類數(shù)據(jù)，比較上述排序算法中關鍵字的比較次數(shù)和移動次數(shù)（其中關鍵字交換計為3次移動）。 3、對于這三類數(shù)據(jù)，比

2、較上述排序算法中不同算法的執(zhí)行時間，精確到微秒（選作）4、對2和3的結果進行分析，驗證上述各種算法的時間復雜度編寫測試main()函數(shù)測試線性表的正確性。2. 程序分析首先，題目要求測試不同的數(shù)據(jù)，所以可以手動輸入待排序元素。其次，由于對一組數(shù)據(jù)要求用不同的排序算法來處理，所以需要一個復制函數(shù)把排序前的無序數(shù)組寄存出去，為下一次排序做準備。再次，由于每次排序后都需要把排序后的結果打印出來，代碼是一樣的，根據(jù)相同的代碼可以封裝成一個函數(shù)的思想，所以還需增加一個打印函數(shù)。2.1 存儲結構本程序采用簡單數(shù)組來儲存輸入的待排序數(shù)組2.2 關鍵算法分析核心算法思想： 1. 利用教材講述的基本算法思想，實

3、現(xiàn)七種排序算法，統(tǒng)計其運行相關數(shù)據(jù)。 2. 將七種排序函數(shù)入口地址作為函數(shù)指針數(shù)組，實現(xiàn)快速調用和統(tǒng)計。使得程序代碼可讀 性增、結構更加優(yōu)化。關鍵算法思想描述和實現(xiàn)： 關鍵算法1： 實現(xiàn)七種算法的基本排序功能。 1、 插入排序：依次將待排序的序列中的每一個記錄插入到先前排序好的序列中，直到全部記錄排序完畢。插入排序的思想是：每次從無序區(qū)取一元素將其添加到有序區(qū)中。2、 希爾排序：先將整個序列分割成若干個子列，分別在各個子列中運用直接插入排序，待整個序列基本有序時，再對全體記錄進行一次直接插入排序。3、 冒泡排序：兩兩比較相鄰記錄的關鍵碼，如果反序則交換，直到沒有反序記錄為止。4、 快速排序：首

4、先選擇一個基準，將記錄分割為兩部分，左支小于或等于基準，右支則大于基準，然后對兩部分重復上述過程，直至整個序列排序完成。 5、 選擇排序：從待排序的記錄序列中選擇關鍵碼最?。ɑ蜃畲螅┑挠涗洸⑺c序列中的第一個記錄交換位置；然后從不包括第一個位置上的記錄序列中選擇關鍵碼最?。ɑ蜃畲螅┑挠涗洸⑺c序列中的第二個記錄交換位置；如此重復，直到序列中只剩下一個記錄為止。 2.3 其他時間復雜度與空間復雜度理論分析可以得出各種排序算法的時間復雜度和空間復雜度，如下表所示：排序方法平均情況最好情況最壞情況輔助空間直接插入排序O(n2)O(n)O(n2)O(1)希爾排序O(nlog2n)O(n2)O(n1

5、.3)O(n2)O(1)起泡排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)O(n2)簡單選擇排O(n2)O(n2)O(n2)O(1)3. 程序運行結果程序運行框圖：實際測試和分析：實際運行結果如下：1 正序排序2 倒序排序3 亂序排序4. 總結1、在初期構思代碼的時候，首先構造了各種算法的基本實現(xiàn)代碼，封裝成類，已經能夠實現(xiàn)七種排序的基本功能，并且測試無誤。后來考慮能否優(yōu)化本程序，首先考慮到測試算法的需求，需要大量隨機數(shù)，因為增添了隨機函數(shù)發(fā)生器，滿足各種測試條件的需求。之后考慮如何能簡化代碼以實現(xiàn)多達七種排序算法的簡單調用、亂序

6、和順序以及逆序數(shù)據(jù)的分別排序和性能指標統(tǒng)計、算法移動次數(shù)和比較次數(shù)的精確統(tǒng)計。如果設計不合理，將使得主調函數(shù)的調用代碼冗長，可讀性變差。因而采用了函數(shù)指針數(shù)組和統(tǒng)一的接口函數(shù)，采用二維數(shù)組存儲移動次數(shù)和比較次數(shù)，調用精確的系統(tǒng)函數(shù)實現(xiàn)時間的統(tǒng)計。此外還添加了一些列優(yōu)化，特別是函數(shù)封裝的方法，使得程序的結構變得更加合理，版面風格也變得好看，可讀性增強。 2、程序的優(yōu)化是一個艱辛的過程，如果只是實現(xiàn)一般的功能，將變得容易很多，當加上優(yōu)化，不論是效率還是結構優(yōu)化，都需要精心設計。這次做優(yōu)化的過程中，遇到不少阻力。由于優(yōu)化中用到很多類的封裝和訪問控制方面的知識，而這部分知識恰好是大一一年學習的薄弱點。因而以后要多花力氣學習C+編程語言，必須要加強這方面的訓練，這樣才能在將編程思想和數(shù)據(jù)結構轉換為代碼的時候能得心應手。3、改進：本程序代碼設