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

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