北郵數(shù)據(jù)結(jié)構(gòu)實驗報告排序.doc

數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱： 實驗四排序?qū)W生姓名： 班 級： 班內(nèi)序號： 學(xué) 號： 日 期： 2014年12月19日1實驗要求實驗?zāi)康耐ㄟ^實現(xiàn)下述實驗內(nèi)容，學(xué)習(xí)、實現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。實驗內(nèi)容使用簡單數(shù)組實現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法： 1、插入排序 2、希爾排序3、冒泡排序4、快速排序5、簡單選擇排序6、堆排序（選作）7、歸并排序（選作）8、基數(shù)排序（選作）9、其他要求： 1、測試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)2、對于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動次數(shù)（其中關(guān)鍵字交換計為3次移動）。 3、對于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時間，精確到微秒（選作）4、對2和3的結(jié)果進(jìn)行分析，驗證上述各種算法的時間復(fù)雜度編寫測試main()函數(shù)測試線性表的正確性。2. 程序分析首先，題目要求測試不同的數(shù)據(jù)，所以可以手動輸入待排序元素。其次，由于對一組數(shù)據(jù)要求用不同的排序算法來處理，所以需要一個復(fù)制函數(shù)把排序前的無序數(shù)組寄存出去，為下一次排序做準(zhǔn)備。再次，由于每次排序后都需要把排序后的結(jié)果打印出來，代碼是一樣的，根據(jù)相同的代碼可以封裝成一個函數(shù)的思想，所以還需增加一個打印函數(shù)。2.1 存儲結(jié)構(gòu)本程序采用簡單數(shù)組來儲存輸入的待排序數(shù)組2.2 關(guān)鍵算法分析核心算法思想： 1. 利用教材講述的基本算法思想，實現(xiàn)七種排序算法，統(tǒng)計其運行相關(guān)數(shù)據(jù)。 2. 將七種排序函數(shù)入口地址作為函數(shù)指針數(shù)組，實現(xiàn)快速調(diào)用和統(tǒng)計。使得程序代碼可讀 性增、結(jié)構(gòu)更加優(yōu)化。關(guān)鍵算法思想描述和實現(xiàn)： 關(guān)鍵算法1： 實現(xiàn)七種算法的基本排序功能。 1、 插入排序：依次將待排序的序列中的每一個記錄插入到先前排序好的序列中，直到全部記錄排序完畢。插入排序的思想是：每次從無序區(qū)取一元素將其添加到有序區(qū)中。2、 希爾排序：先將整個序列分割成若干個子列，分別在各個子列中運用直接插入排序，待整個序列基本有序時，再對全體記錄進(jìn)行一次直接插入排序。3、 冒泡排序：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序記錄為止。4、 快速排序：首先選擇一個基準(zhǔn)，將記錄分割為兩部分，左支小于或等于基準(zhǔn)，右支則大于基準(zhǔn)，然后對兩部分重復(fù)上述過程，直至整個序列排序完成。 5、 選擇排序：從待排序的記錄序列中選擇關(guān)鍵碼最?。ɑ蜃畲螅┑挠涗洸⑺c序列中的第一個記錄交換位置；然后從不包括第一個位置上的記錄序列中選擇關(guān)鍵碼最?。ɑ蜃畲螅┑挠涗洸⑺c序列中的第二個記錄交換位置；如此重復(fù)，直到序列中只剩下一個記錄為止。 2.3 其他時間復(fù)雜度與空間復(fù)雜度理論分析可以得出各種排序算法的時間復(fù)雜度和空間復(fù)雜度，如下表所示：排序方法平均情況最好情況最壞情況輔助空間直接插入排序O(n2)O(n)O(n2)O(1)希爾排序O(nlog2n)O(n2)O(n1.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. 程序運行結(jié)果程序運行框圖：實際測試和分析：實際運行結(jié)果如下：1 正序排序2 倒序排序3 亂序排序4. 總結(jié)1、在初期構(gòu)思代碼的時候，首先構(gòu)造了各種算法的基本實現(xiàn)代碼，封裝成類，已經(jīng)能夠?qū)崿F(xiàn)七種排序的基本功能，并且測試無誤。后來考慮能否優(yōu)化本程序，首先考慮到測試算法的需求，需要大量隨機(jī)數(shù)，因為增添了隨機(jī)函數(shù)發(fā)生器，滿足各種測試條件的需求。之后考慮如何能簡化代碼以實現(xiàn)多達(dá)七種排序算法的簡單調(diào)用、亂序和順序以及逆序數(shù)據(jù)的分別排序和性能指標(biāo)統(tǒng)計、算法移動次數(shù)和比較次數(shù)的精確統(tǒng)計。如果設(shè)計不合理，將使得主調(diào)函數(shù)的調(diào)用代碼冗長，可讀性變差。因而采用了函數(shù)指針數(shù)組和統(tǒng)一的接口函數(shù)，采用二維數(shù)組存儲移動次數(shù)和比較次數(shù)，調(diào)用精確的系統(tǒng)函數(shù)實現(xiàn)時間的統(tǒng)計。此外還添加了一些列優(yōu)化，特別是函數(shù)封裝的方法，使得程序的結(jié)構(gòu)變得更加合理，版面風(fēng)格也變得好看，可讀性增強(qiáng)。 2、程序的優(yōu)化是一個艱辛的過程，如果只是實現(xiàn)一般的功能，將變得容易很多，當(dāng)加上優(yōu)化，不論是效率還是結(jié)構(gòu)優(yōu)化，都需要精心設(shè)計。這次做優(yōu)化的過程中，遇到不少阻力。由于優(yōu)化中用到很多類的封裝和訪問控制方面的知識，而這部分知識恰好是大一一年學(xué)習(xí)的薄弱點。因而以后要多花力氣學(xué)習(xí)C+編程語言，必須要加強(qiáng)這方面的訓(xùn)練，這樣才能在將編程思想和數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為代碼的時候能得心應(yīng)