數(shù)據(jù)結(jié)構(gòu)課程設(shè)計----內(nèi)部排序算法性能分析

1、<p><b>　　課程名稱：數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　本科學生課程設(shè)計（論文）</p><p>　　題 目 內(nèi)部排序算法性能分析 </p><p>　　姓 名 </p><p>　　學

2、 號 </p><p>　　學 部 計算機科學與技術(shù) </p><p>　　專業(yè)、年級 計科1003 </p><p>　　指 導 教 師 </p><p&

3、gt;　　2011年12月24日</p><p><b>　　摘 要</b></p><p>　　排序是計算機科學中基本的研究課題之一,其目的是方便記錄的查找、插入和刪除.通過描述冒泡、選擇、插入、堆和快速6種排序算法，內(nèi)部排序其算法靈活方便，因此成為了程序算法中一個必不可少的應(yīng)用，所以在應(yīng)用之前要經(jīng)過嚴謹?shù)乃伎疾挪粫鲥e，不會造成計算機運算速度的延遲，才會完全發(fā)揮內(nèi)

4、部排序的性能。</p><p>　　內(nèi)部排序的方法種類繁多，但就其全面性能而言，很難提出一種被認為是最好的方法。但就其全面性能而言，很難提出一種被認為是最好的方法，每一種方法都有各自的優(yōu)缺點，適合不同的環(huán)境（如記錄的初始排序列狀態(tài)等）下使用。如果安排序過程中依據(jù)的不同原則對內(nèi)部排序方法進行分類，則大致可分為插入排序、交換排序，選擇排序，歸并排序和計數(shù)排序等五類；如果按內(nèi)部排序過程中所需要的工作量來區(qū)分，則可分為3

5、類：（1）簡單的排序方法，該時間復(fù)雜度為O(n*n)；（2）先進的排序方法，該時間復(fù)雜度為O（nlogn）；（3）基數(shù)排序，其時間復(fù)雜度為O（d*n）；主要介紹非常實用而算法又容易接受的的這六類排序。</p><p>　　由于很多人在使用的過程中，不知道那種排序適合他們的程度設(shè)計，因此導致該算法沒有得到充分的應(yīng)用，起泡排序最簡單的排序，很容易寫出代碼，但運算時間復(fù)雜度稍長一些；直接排序能夠很快的最大和最小的數(shù)據(jù)，

6、但假如數(shù)據(jù)較多，操作比較繁瑣；簡單選擇排序穩(wěn)定比較次數(shù)與起泡排序一樣，則相對之還要慢；快速排序速度快，數(shù)據(jù)移動少，平均性能比較好，但是性能不穩(wěn)定；希爾排序是插入算法的改進，由于多次的插入造成了其穩(wěn)定性不好；堆排序在最壞情況下時間復(fù)雜度也為O(nlogn)，并且它僅需一個記錄大小供交換用的輔助存儲空間，但在記錄數(shù)較少時不提倡使用； </p><p>　　但本文主要介紹這6類排序（起泡排序、直接排序、簡單選擇排序、快

7、速排序、希爾排序、堆排序）一些優(yōu)點和缺陷，對缺陷加以改進。通過對傳統(tǒng)算法的性能分析，發(fā)現(xiàn)其中的缺陷，對算法的設(shè)想來彌補中間的不足，以致算法的性能有所提高。</p><p>　　關(guān)鍵字: 數(shù)據(jù)結(jié)構(gòu)、內(nèi)部排序、算法改進、性能分析</p><p><b>　　目 錄</b></p><p>　　第1章 前 言1</p><

8、;p><b>　　1.1分析問題1</b></p><p><b>　　1.2研究背景1</b></p><p><b>　　1.3研究方向2</b></p><p><b>　　1.4研究方法2</b></p><p>　　1.5結(jié)構(gòu)與安排

9、2</p><p>　　第2章 系統(tǒng)功能分析3</p><p>　　2.1 需求分析及實現(xiàn)目標3</p><p>　　2.1.1應(yīng)用現(xiàn)狀及存在的問題3</p><p>　　2.1.2 實現(xiàn)任務(wù)3</p><p>　　2.2可行性分析4</p><p>　　2.2.1技術(shù)可行性4&l

10、t;/p><p>　　2.2.2 工具可行性4</p><p>　　2.2.3 經(jīng)濟可行性4</p><p>　　2.2.4 操作可行性4</p><p>　　第3章 總體設(shè)計5</p><p>　　3.1設(shè)計需求及描述5</p><p>　　3.1.1設(shè)計問題描述5</p>

11、<p>　　3.1.2 設(shè)計需求分析5</p><p>　　3.1.3 系統(tǒng)設(shè)計的實質(zhì)功能5</p><p>　　3.2 設(shè)計原理與設(shè)計內(nèi)容6</p><p>　　3.2.1系統(tǒng)總體結(jié)構(gòu)6</p><p>　　3.2.2“內(nèi)部操作過程”菜單設(shè)計原理如圖所示。6</p><p>　　3.2.2“

12、排序性能分析”菜單設(shè)計原理7</p><p>　　3.2.3設(shè)計內(nèi)容7</p><p>　　第4章 詳細設(shè)計9</p><p><b>　　4.1冒泡排序9</b></p><p>　　4.2直接插入排序10</p><p>　　4.3希爾排序11</p><p&g

13、t;　　4.4簡單選擇排序13</p><p>　　4.5快速排序14</p><p><b>　　4.6堆排序16</b></p><p>　　4.7六種排序方法討論18</p><p>　　第5章 排序算法的改進20</p><p>　　5.1雙向冒泡排序算法20</p>

14、;<p>　　5.2雙倍快速排序的算法21</p><p>　　5.3選擇排序的算法22</p><p>　　5.4 堆排序的改進算法24</p><p>　　第六章 系統(tǒng)實現(xiàn)及數(shù)據(jù)測試29</p><p><b>　　6.1主界面29</b></p><p>　　6.2“

15、排序內(nèi)部操作過程”菜單29</p><p>　　6.2.1當用戶輸入0-6的數(shù)字時則會隨意的進入下一級子菜單30</p><p>　　6.2.2輸入“2”進行“希爾”排序30</p><p>　　6.3“性能分析”菜單31</p><p>　　6.3.1當用戶輸入“1”時進行“插入與希爾”排序之間的性能分析比較31</p>

16、;<p>　　6.3.2當用戶輸入“1”時進行“插入與冒泡”排序之間的性能分析比較32</p><p><b>　　總 結(jié)33</b></p><p><b>　　參考文獻34</b></p><p><b>　　第1章 前 言</b></p><p>

17、<b>　　1.1分析問題</b></p><p>　　排序是指將一個數(shù)據(jù)元素序列排列成一個有序列的過程。排序是計算機的一個重要的領(lǐng)域，并廣泛應(yīng)用于數(shù)據(jù)處理、情報檢索、商業(yè)金融及企業(yè)管理等許多方面。資料表明，在當今計算機系統(tǒng)中，花費在排序上的時間占了系統(tǒng)運行的時間的很大比重。相當多的計算機中，有50%以上的CPU時間是用在排序數(shù)據(jù)上的。因此為了提高計算機系統(tǒng)的工作效率，研究和發(fā)展更有效的排序

18、算法的十分重要的。</p><p>　　目前人們已經(jīng)提出了許多不同的排序算法，然而如果在不適應(yīng)的場合的應(yīng)用，那么其平均時間(averageTime)和最差時間(worstTime)就會不理想，其排序算效率就會大大的降低，如國防系統(tǒng)和生命支持系統(tǒng)，如果排序方法性能低下，將會令我們大大的失望。另外用來衡量排序算法的標準是穩(wěn)定性，在那些比較復(fù)雜的排序中其穩(wěn)定性不是很好，容易程序出錯，就這樣造成我們計算機的運算時間加長和

19、內(nèi)存地址的浪費。</p><p><b>　　1.2研究背景</b></p><p>　　由于排序是數(shù)據(jù)結(jié)構(gòu)中的重要的一個部分，也是在實際開發(fā)中易遇到的問題，所以研究各種排序算法的時間消耗對于實際應(yīng)用當中很有必要通過分析實際結(jié)合算法的特性進行選擇和使用哪種算法可以使實際問題得到更好更充分的解決！該系統(tǒng)通過對各種內(nèi)部排序算法如直接插入排序，冒泡排序，簡單選擇排序，快速排

20、序，希爾排序，堆排序等，以關(guān)鍵碼的比較次數(shù)分析其特點，并進行比較，估算每種算法的時間消耗，從而比較各種算法的優(yōu)劣和使用情況，排序表的數(shù)據(jù)是多種不一樣的情況，如隨機產(chǎn)生數(shù)據(jù)、極端的數(shù)據(jù)如已是正序或逆序數(shù)據(jù)。比較的結(jié)果用一個直方圖來表示。</p><p>　　然而在本文中我們將選擇其中最基本也是最常用的6種內(nèi)部排序（直接插入排序，冒泡排序，簡單選擇排序，快速排序，希爾排序，堆排序）進行討論，介紹它們的基本思想和實現(xiàn)過

21、程，分析各種算法的時間、空間復(fù)雜性、比較次數(shù)、移動次數(shù)以及穩(wěn)定性，以期讀者能夠掌握這些算法及其特點中，在實際應(yīng)用中能夠結(jié)合具體問題設(shè)計出正確而高效率的數(shù)據(jù)排序程序。</p><p><b>　　1.3研究方向</b></p><p>　　排序算法其種類繁多，但還是有一些未解次的問題，例如：選擇排序，快速排序，希爾排序，堆排序仍然面臨排序后的不穩(wěn)定性；從而還面臨一種穩(wěn)定

22、的算法也可由不穩(wěn)定的算法來實現(xiàn)；冒泡排序很容易實現(xiàn)，但是它的時間復(fù)雜度和移動次數(shù)的問題仍然存在；更讓人不可思議的是有些排序這兩種缺點都存在；同樣每一種排序算法都有它的優(yōu)缺點，適合于不同的環(huán)境。因此，在實際應(yīng)用中，應(yīng)根據(jù)具體情況進行選擇。首先，考慮排序?qū)Ψ€(wěn)定性的要求，若要求穩(wěn)定，則只能在穩(wěn)定的排序方法中選取，否則可以在所有的方法中選??；其次要考慮待排序的序列記錄數(shù)目n，若n較大則可以在改進的方法中選取，否則在簡單方法中選??；然后再考慮其他

23、因素。本文主要是通過排序來從中發(fā)現(xiàn)的穩(wěn)定性、比較次數(shù)以及移動次數(shù)等問題，從而從性能上分析得出不足并加以改進。</p><p><b>　　1.4研究方法</b></p><p>　　基于Visual C++ 6.0平臺編程是當今程序者的青睞，它有著強大的性能、完全豐富的工具及高速的處理速度和完備的兼容性。不僅可以簡化編程的設(shè)計并且算法應(yīng)用靈活，使應(yīng)用程序的開發(fā)更為簡便

24、。C++是為開發(fā)大型程序而研制的，它比C語言困難得多，它功能豐富、表達能力強、使用靈活方便、應(yīng)用面廣、目標程序效率高、可移植性好，既具有高級語言的優(yōu)點，又具有低級語言的許多特點，完全適合于編寫系統(tǒng)軟件；本人就利用上述C++開發(fā)軟件編寫了《內(nèi)部排序算法性能分析系統(tǒng)》，采用人機互動的操作模式，系統(tǒng)經(jīng)過顯示主界面功能，然后用戶的需要操作，實現(xiàn)了兩種排序相互之間的優(yōu)缺點，從而從中獲得一些性能分析結(jié)論讓人們更好應(yīng)用各種排序。</p>

25、<p><b>　　1.5結(jié)構(gòu)與安排</b></p><p>　　本文主要是介紹六種排序的性能分析，首先“前言”對研究背景和研究目的作了簡單的介紹；其次“系統(tǒng)功能分析”對本系的說明和講解；再次“總體設(shè)計”對本系統(tǒng)做了一個簡要引導，并且通過“總體設(shè)計”對該系統(tǒng)的運行懂得差不多了；“詳細設(shè)計”就是對系統(tǒng)有了詳細的設(shè)計過程，更進一步知道設(shè)計原理；“排序算法的改進” 介紹傳統(tǒng)算法的不足，

26、經(jīng)過設(shè)想對原算法加以改進“系統(tǒng)實現(xiàn)及數(shù)據(jù)測試”不但讓我們知道了系統(tǒng)的界面和一些操作的實施，讓你知道整個算法的設(shè)計并且加以理解。</p><p>　　第2章 系統(tǒng)功能分析</p><p>　　2.1 需求分析及實現(xiàn)目標</p><p>　　2.1.1應(yīng)用現(xiàn)狀及存在的問題</p><p>　　隨著社會的發(fā)展，計算機科學技術(shù)應(yīng)用又邁進了一大步，然而

27、在很多的應(yīng)用過程中不時產(chǎn)生很多錯誤或延遲，尤其是在鋼鐵廠、天氣預(yù)報的預(yù)測、火箭的發(fā)射等一些大型的場所，這無疑處理器在處理的過程中不能出一些差錯，因此就要對那些已編制好的程序的算法要求比較嚴謹、排序就是其中之一。很多人在運用的過程中對其算法不夠了解或者考慮不周，因此給處理器造成了不必的誤時。就拿火箭發(fā)射來說，如果排序方法性能低下，將是非常危險的。我們將會看到有幾個排序算法能夠提供某種保證機制，可以消除在最差情況下不可接受的執(zhí)行性能。<

28、;/p><p>　　另外存在一個比較大的問題就是排序的穩(wěn)定性。穩(wěn)定排序方法保持相等元素的相關(guān)順序。例如，假設(shè)有一個學生數(shù)組，其中的每一項由學生的姓和其品質(zhì)總分數(shù)組成，根據(jù)品質(zhì)總分數(shù)排序。如果排序方法穩(wěn)定，并且（”balan”,28）開始時位于比(“wang”,28)小的索引位置，排序后(“balan”,28)仍然位于比(“wang”,28)小的索引位置。穩(wěn)定性可以簡化工程開發(fā)。例如，假設(shè)上面提到的數(shù)組已經(jīng)根據(jù)排好序了

29、，有一個根據(jù)品質(zhì)總分數(shù)排序的應(yīng)用程序調(diào)用，對于擁有同樣品質(zhì)總分數(shù)的學生，他們的順序還是按字母順序。穩(wěn)定排序不需要附加其他確保相同品質(zhì)總分數(shù)的學生按字母順序排列的工作就可以完成了。因此，對于程序員來說這是必備的重要技能，同時掌握它是他們當前一項急迫的任務(wù)。</p><p>　　2.1.2 實現(xiàn)任務(wù)</p><p>　　排序數(shù)據(jù)是由系統(tǒng)隨機產(chǎn)生，再通過用戶根據(jù)自已所需的進行對這六種排序的操作，

30、簡潔清晰、容易理解，提高了對該六種排序性能的應(yīng)用。</p><p>　　用戶只需按界面上的提示操作。</p><p>　　這六種排序的性能分析由系統(tǒng)自動的給予分析并且可以看到整個的排序過程(如：移動的次數(shù)、比較的次數(shù)以及穩(wěn)定性好壞)</p><p>　　在系統(tǒng)隨機產(chǎn)生數(shù)據(jù)是用戶最好是多采用幾組數(shù)據(jù)進行比較這樣的正確率要高，同時測試系統(tǒng)的性能好壞。</p>

31、<p><b>　　2.2可行性分析</b></p><p>　　所謂可行性分析就是用最小的代價在盡可能短的時間內(nèi)確定問題是否能夠解決。這步工作的主要是要進行一次大大壓縮簡化了的系統(tǒng)分析和設(shè)計的過程，也就是在較高層次上以比較抽象的方式進行系統(tǒng)分析和設(shè)計的過程?？尚行匝芯康淖罡救蝿?wù)是對以后的行動方針提出建議，以避免時間、資源、人力和金錢的浪費，推薦一個較好的解決方案，并且為工程

32、制定一個初步的計劃。</p><p>　　2.2.1技術(shù)可行性</p><p>　　本系統(tǒng)采用人機操作進行管理，用visual C++ 6.0進行前臺設(shè)計、系統(tǒng)隨機產(chǎn)生數(shù)據(jù)，用戶通過界面操作，系統(tǒng)自動給予合理分析，由于visual C++ 6.0功能強大、使用的靈活、良好的可擴展性、以及廣泛實際應(yīng)用，充分說明本系統(tǒng)在技術(shù)方面的可行性。</p><p>　　2.2.2

33、 工具可行性</p><p><b>　　軟件方面：</b></p><p>　　信息時代對于軟件的應(yīng)用已不是人們的難題，人們在日常辦公中用的計算機操作的系統(tǒng)等都屬于軟件部分。</p><p><b>　　硬件方面：</b></p><p>　　計算機普及到今天，人們對于它的擁有已不少見，它的硬件設(shè)

34、備完全能夠滿足人們的需求，而價格也能被人們所接受。</p><p>　　2.2.3 經(jīng)濟可行性</p><p>　　這是個超小型的性能分析系統(tǒng)，從投入的人力，財力與物力來講是非常之小的，只要一臺電腦，一臺打印機，這個系統(tǒng)就可以搞起來，考慮到學校里有電腦，現(xiàn)只要購置一臺打印機就可以了。從節(jié)省人力方面，可以讓管理人員從繁與復(fù)雜的工作中解脫出來，做更多的工作，可以給讀者提高到更深的一個層次。&l

35、t;/p><p>　　2.2.4 操作可行性</p><p>　　本系統(tǒng)設(shè)計清晰，有良好的用戶接口，操作簡潔，完全可以給用戶解決，并達到操作過程中的直觀、方便、實用、安全等要求，因此操作方面具有可行性。</p><p><b>　　第3章 總體設(shè)計</b></p><p>　　3.1設(shè)計需求及描述</p>&l

36、t;p>　　3.1.1設(shè)計問題描述</p><p>　　設(shè)計一個測試程序比較起泡排序、直接排序、簡單選擇排序、快速排序、希爾排序、堆排序算法的關(guān)鍵字比較次數(shù)和移動次數(shù)以取得直觀感受。待排序表的表長不小于10，表中數(shù)據(jù)隨機產(chǎn)生，至少用5組不同數(shù)據(jù)作比較，比較指標有：關(guān)鍵字參加比較次數(shù)和關(guān)鍵字的移動次數(shù)（關(guān)鍵字交換記為3次移動）。最后輸出比較結(jié)果.</p><p>　　3.1.2 設(shè)計

37、需求分析</p><p>　　用數(shù)組S來存放系統(tǒng)隨機產(chǎn)生的100個數(shù)據(jù)，并放到R數(shù)組中，數(shù)據(jù)由程序隨機產(chǎn)生，用戶只需查看結(jié)果。</p><p>　　利用全局變量times和changes來分別統(tǒng)計起泡排序、直接排序、簡單選擇排序、快速排序、希爾排序、堆排序算法的比較次數(shù)和移動次數(shù)，然后輸出結(jié)果，并在每一次統(tǒng)計之后，將times和changes都賦值為0。</p><p&

38、gt;　　在主函數(shù)中調(diào)用用戶自定義函數(shù)，輸出比較結(jié)果。</p><p>　　本程序是對幾種內(nèi)部排序算法的關(guān)鍵字進行性能分析的程序，它分為以下幾個部分：a、建立數(shù)組；b、調(diào)用函數(shù)求比較和移動次數(shù)；c、輸出結(jié)果。</p><p>　　3.1.3 系統(tǒng)設(shè)計的實質(zhì)功能</p><p>　　用戶啟動該系統(tǒng)進入主菜單，在主菜單中有三個菜單命令，可以按照用戶的意愿來選擇他想要的命

39、令</p><p>　　當你選擇“排序內(nèi)部操作過程”菜單時，即可進入一下子菜單，你可以看到這六種排序的內(nèi)部排序過程，并且可以知道這六種排序具體的移動次數(shù)、比較次數(shù)以及穩(wěn)定性的好壞。</p><p>　　當你選擇“排序性能分析”菜單時，馬上進入下一級子菜單，你可以知道這六種排序之間的一些性能相關(guān)的知識，這一級菜單是用戶來安排，如果不知道那兩種排序的性能那種占優(yōu)勢好一些，你可以輸入排序的編號，

40、然后系統(tǒng)給你分析，給出結(jié)論。</p><p>　　3.2 設(shè)計原理與設(shè)計內(nèi)容</p><p>　　3.2.1系統(tǒng)總體結(jié)構(gòu)</p><p>　　系統(tǒng)總體結(jié)構(gòu)如圖4.1所示：</p><p>　　圖3.1 系統(tǒng)總體結(jié)構(gòu)</p><p>　　3.2.2“內(nèi)部操作過程”菜單設(shè)計原理如圖所示。</p><p&

41、gt;　　圖3.2“內(nèi)部操作過程”菜單</p><p>　　3.2.2“排序性能分析”菜單設(shè)計原理</p><p>　　“排序性能分析”菜單的算法是調(diào)用“內(nèi)部操作過程”菜單的算法，根據(jù)這一原理而成的，就不一一的介紹了，請讀者自已去理解“內(nèi)部操作過程”的設(shè)計過程。</p><p><b>　　3.2.3設(shè)計內(nèi)容</b></p>&l

42、t;p>　　內(nèi)部排序系統(tǒng)具體實現(xiàn)的功能包括：快速排序，冒泡排序，希爾排序，簡單選擇排序，堆排序，直接排序等這六大排序的集成六個主要的函數(shù)如下：</p><p>　　快速排序函數(shù)：partition();</p><p>　　希爾排序函數(shù)：Shellsort();</p><p>　　簡單選擇排序函數(shù)：selectsort();</p><p

43、>　　堆排序函數(shù)：heap();</p><p>　　直接排序函數(shù)：insertsort();</p><p>　　起泡排序函數(shù)：Bubblesort();</p><p><b>　　排序數(shù)據(jù)類型定義：</b></p><p>　　ADT paixu{</p><p>　　數(shù)據(jù)對象：D={

44、aij|aij屬于{1，2，3…},i,j>0}</p><p>　　數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,ai∈D，i=2,...,n}</p><p><b>　　基本操作：</b></p><p>　　Insertsort();</p><p>　　初始條件：數(shù)組已經(jīng)存在。</p&g

45、t;<p>　　操作過程：將一個記錄插入到已經(jīng)排好序的有序列表中，從而得到了一個新的、記錄新增1的有序表。</p><p>　　Bubblesort();</p><p>　　初始條件：數(shù)組已經(jīng)存在。</p><p>　　操作過程：兩兩比較待排序記錄的鍵值，并交換不滿足順序要求的那些偶對，知道全部滿足順序要求為止。</p><p&g

46、t;　　Shellsort();</p><p>　　初始條件：數(shù)組已經(jīng)存在。</p><p>　　操作過程：先取定一個正整數(shù)d1<n,把全部記錄分成d1個組，所有距離為d1倍數(shù)的記錄放在一組中，在各組內(nèi)進行插入排序，然后取d2<d1重復(fù)上述分組和排序工作，直至取di=1,即所有記錄放在一個組中排序為止。</p><p>　　Selectsort();&

47、lt;/p><p>　　初始條件：數(shù)組已經(jīng)存在。</p><p>　　操作過程：每次從待排序的記錄中選出鍵值最?。ɑ蜃畲螅┑挠涗?，順序放在已經(jīng)排序的記錄序列的最好，直到全部排完。</p><p>　　heapsort ();</p><p>　　初始條件：數(shù)組已經(jīng)存在。</p><p>　　操作過程：對一組待排序的的鍵值，

48、首先是把它們按堆的定義排列成一個序列，這就找到了最小鍵值，然后把最小的鍵值取出，用剩下的鍵值再重建堆，便得到次小鍵值，如此反復(fù)進行，知道把全部鍵值排好序為止。</p><p>　　partition()；</p><p>　　初始條件：數(shù)組已經(jīng)存在。</p><p>　　操作過程：在待排序的n個記錄中任取一個記錄，以該記錄的鍵值為基準用交換的方法將所有記錄分成兩部分

49、，所有鍵值比它小的放在一邊，大的放另一邊，并把該記錄放在中間，然后重復(fù)至完成。</p><p><b>　　} ADT 排序</b></p><p><b>　　第4章 詳細設(shè)計</b></p><p><b>　　4.1冒泡排序</b></p><p>　　冒泡排序（Bubb

50、leSort）是我們大家都熟知的排序，其基本概念是：依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個和第2個數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個數(shù)和第3個數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對數(shù)開始比較（因為可能由于第2個數(shù)和第3個數(shù)的交換，使得第1個數(shù)不再小于第2個數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒

51、數(shù)第二個數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個新的最大數(shù)（其實在整個數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過程，直至最終完成排序。</p><p>　　由于在排序過程中總是小數(shù)往前放，大數(shù)往后放，相當于氣泡往上升，所以稱作冒泡排序。</p><p>　　用二重循環(huán)實現(xiàn)，外循環(huán)變量設(shè)為i，內(nèi)循環(huán)變量設(shè)為j。外循環(huán)重復(fù)9次，內(nèi)循環(huán)依次重復(fù)9，8，...，1

52、次。每次進行比較的兩個元素都是與內(nèi)循環(huán)j有關(guān)的，它們可以分別用a[j]和a[j+1]標識，i的值依次為1,2,...,9，對于每一個i, j的值依次為1,2,...10-i。</p><p>　　算法：for(i=1;i<=L-6;i++)/*外循環(huán)：控制比較趟數(shù)*/</p><p><b>　　{</b></p><p>　　for(j

53、=L;j>=i+1;j--)/*內(nèi)循環(huán)：進行每趟比較*/</p><p><b>　　{</b></p><p>　　times++;/*比較次數(shù)*/</p><p>　　if(R[j]<R[j-1]) /*如果R[j]小于R[j-1],交換兩者的位置*/</p><p><b>　　{ </

54、b></p><p>　　R[0]=R[j];</p><p>　　R[j]=R[j-1];</p><p>　　R[j-1]=R[0];</p><p>　　exchange=TRUE;</p><p>　　changes+=3;/*移動次數(shù)*/</p><p><b>　　}

55、}</b></p><p>　　冒泡排序的最好 、最壞 、平均情況下的時間復(fù)雜度都為 O (n2 ) ,故算法的平均時間復(fù)雜度也為 O (n2 ) 。但是若在某趟排序中未發(fā)現(xiàn)氣泡位置的交換 ,則說明待排序的無序區(qū)中所有氣泡均滿足輕者在上、重者在下的原則 ,即為正序 ,則冒泡排序過程可在此趟掃描后就終止 ;在每趟排序過程中 ,無序區(qū) R [ i. . n]的范圍可能會有較大改變 ,而不是遞減 ;對某

56、些不對稱性情況 ,在排序過程中 ,可改變其掃描方向。</p><p><b>　　4.2直接插入排序</b></p><p>　　直接插入排序(Straight Insertion Sort)是一種最簡單的排序方法，它基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。</p><p>　　每次從無序表中取出第一

57、個元素，把它插入到有序表的合適位置，使有序表仍然有序。</p><p>　　第一趟比較前兩個數(shù),然后把第二個數(shù)按大小插入到有序表中; 第二趟把第三個數(shù)據(jù)與前兩個數(shù)從前向后掃描，把第三個數(shù)按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。</p><p>　　直接插入排序是由兩層嵌套循環(huán)組成的。外層循環(huán)標識并決定待比較的數(shù)值。內(nèi)層循環(huán)為待比較數(shù)值確定其最終位

58、置。直接插入排序是將待比較的數(shù)值與它的前一個數(shù)值進行比較，所以外層循環(huán)是從第二個數(shù)值開始的。當前一數(shù)值比待比較數(shù)值大的情況下繼續(xù)循環(huán)比較，直到找到比待比較數(shù)值小的并將待比較數(shù)值置入其后一位置，結(jié)束該次循環(huán)。</p><p>　　值得注意的是，我們必需用一個存儲空間來保存當前待比較的數(shù)值，因為當一趟比較完成時，我們要將待比較數(shù)值置入比它小的數(shù)值的后一位 插入排序類似玩牌時整理手中紙牌的過程。插入排序的基本方法是：每

59、步將一個待排序的記錄按其關(guān)鍵字的大小插到前面已經(jīng)排序的序列中的適當位置，直到全部記錄插入完畢為止。</p><p>　　算法：for(i=2;i<=L;i++)</p><p><b>　　{</b></p><p>　　if(R[i]<R[i-1])</p><p>　　{ R[0]=R[i];j=i

60、-1;//復(fù)制哨兵</p><p>　　while(R[0]<R[j])</p><p><b>　　{</b></p><p>　　times++; changes++;</p><p>　　R[j+1]=R[j];j--;//記錄后移</p><p><b>　　}</b

61、></p><p>　　R[j+1]=R[0];//插入到正確位置</p><p>　　changes++;</p><p><b>　?。?lt;/b></p><p>　　按以上算法進行直接插入排序的過程如圖4.1所示：</p><p>　　初始序列：i=1 [46] 58 15 45 90

62、18 10 62</p><p>　　i=2 [46 58] 15 45 90 18 10 62</p><p>　　i=3 [15 46 58] 45 90 18 10 62</p><p>　　i=4 [15 45 46 58] 90 18 10 62</p><p>　　i=5 [15 45 46 58 90] 18 10 62<

63、/p><p>　　i=6 [15 18 45 46 58 90] 10 62</p><p>　　i=7 [10 15 18 45 46 58 90] 62</p><p>　　i=8 [10 15 18 45 46 58 62 90]</p><p>　　圖4.1直接插入排序過程</p><p>　　從算法的實現(xiàn)過程可見

64、，在最壞情況下，線性插入排序每插入一個元素需要進行i-1次比較，需要插入元素為N-1個，所以最大比較次數(shù)為：N(N-1)/2,該算法的時間復(fù)雜性為O(N*N) 空間復(fù)雜度為O(1)，因此，直接插入排序?qū)儆诜€(wěn)定的排序</p><p><b>　　4.3希爾排序</b></p><p>　　希爾排序(Shell Sort)又稱“縮小增量排序”(Diminishing In

65、crement Sort)，它也是一種屬于插入排序類的方法，但在時間效率上跟其他的幾種排序方法有了較大的改進。</p><p>　　希爾排序基本思想：先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。</p><p>　　先看一下希爾排序的過程。初始關(guān)鍵字序列如下面所示。首先將該序列分成5個子序列{R1,,R6}

66、,{R2,R7}……{R5,R10},如下面所示，分別對每個子序列進行直接插入排序，排序完后，然后進行第二趟希爾排序，即分別對下列3個子序列：{R1,R4,R7,R10},{R2,R5,R8}和{R3,R6,R9}進行直接插入排序，其結(jié)果如第二趟排序所示，最后對整個序列進行一趟直接插入排序。至此，希爾排序結(jié)束，整個序列的記錄已按關(guān)鍵字非遞減有序排列，如下圖4.2所示：</p><p>　　【初始關(guān)鍵字】：49

67、 38 65 97 76 13 49 55 04</p><p>　　一趟排序結(jié)果：13 27 49 55 04 49 38 65 97 76</p><p>　　13 55 38 76</p><p>　　27

68、 04 65</p><p>　　49 49 97</p><p>　　二趟排序結(jié)果：13 04 49 38 27 49 55 65 97 76 </p><p>　　三趟排序結(jié)果：04 13

69、 27 38 49 49 55 65 76 97</p><p>　　圖4.2希爾排序過程</p><p>　　從上述排序過程可見，希爾排序的一個特點是：子序列的構(gòu)成不是簡單地“逐段分割”而是將相隔某個“增量”的記錄組成一個子序列。如上例中，第一趟排序時的增量為5，第二趟排序時的增量為3，第三趟排序時的增量為1，由于在前兩趟的插入排序中記錄

70、的關(guān)鍵字是和同一子序列中的前一個記錄的關(guān)鍵進行比較，到越后面排序的數(shù)變得越來越有序，為此算法如下：</p><p>　　for(i=d+1;i<=n；i++) //將R[d+1．．n]分別插入各組當前的有序區(qū)</p><p>　　if(R[ i ].key<R[i-d].key) {</p><p>　　R[0]=R[i];j=i-d；

71、 //R[0]只是暫存單元，不是哨兵</p><p>　　do { //查找R的插入位置</p><p>　　R[j+d]=R[j]； //后移記錄</p><p>　　j=j-d； //查找前一記錄</p><p>　　}while(j>0&

72、amp;&R[0].key<R[j].key)；</p><p>　　R[j+d]=R[0]； ｝ //插入R到正確的位置上</p><p>　　算法優(yōu)劣：不需要大量的輔助空間，和歸并排序一樣容易實現(xiàn)。希爾排序是基于插入排序的一種算法， 在此算法基礎(chǔ)之上增加了一個新的特性，提高了效率。希爾排序的時間復(fù)雜度為 O(N*(logn)2)， 沒有快速排序算法快 O(

73、n*(logn))，因此中等大小規(guī)模表現(xiàn)良好，對規(guī)模非常大的數(shù)據(jù)排序不是 最優(yōu)選擇。但是比O(n2）復(fù)雜度的算法快得多。并且希爾排序非常容易實現(xiàn)，算法代碼短而簡單。 此外，希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，與此同時快速排序在最壞 的情況下執(zhí)行的效率會非常差。 專家門提倡，幾乎任何排序工作在開始時都可以用希爾排序，若在實際使用中證明它不夠快， 再改成快速排序這樣更高級的排序算法. 本質(zhì)上講，希爾排序算法的一種改進，減

74、少了其復(fù)制的次數(shù)，速度要快很多。 原因是，當N值很大時數(shù)據(jù)項每一趟排序需要的個數(shù)很少，但數(shù)據(jù)項的距離很長。 當N值減小時每一趟需要和動的數(shù)據(jù)增多，此時已經(jīng)接近于它們排序后的最終位置。 正是這兩種情況的結(jié)合才使希爾排序效率比插入排序高很多。</p><p>　　穩(wěn)定性：希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快；當元素基本有序了，步長很小，插入

75、排序?qū)τ谟行虻男蛄行屎芨?。所以，希爾排序的時間復(fù)雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。</p><p><b>　　4.4簡單選擇排序</b></p><p>　　一趟簡單選擇排序的操

76、作為：通過n-i次關(guān)鍵字間的比較，從n-i+j個記錄中選出關(guān)鍵字最小的記錄，并和第i（1<i<n）個記錄交換之。</p><p>　　N個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：</p><p>　　初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。</p><p>　　第1趟排序,在無序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]

77、，將它與無序區(qū)的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)。</p><p>　　第i趟排序,第i趟排序開始時，當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當前無序區(qū)中選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個記錄R交換，使R[1..i]和R分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新

78、無序區(qū)。</p><p>　　這樣，n個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。</p><p>　　for(i=1;i<=L;i++)</p><p>　　{ n=i;</p><p>　　for(j=i+1;j<=L;j++)</p><p>　　{ times++;

79、</p><p>　　if (R[j]<R[h])</p><p><b>　　h=j;</b></p><p><b>　　if(h!=j)</b></p><p>　　{ R[0]=R[h];R[h]=R[i];R[i]=R[0];</p><p>

80、;　　changes+=3;} }</p><p><b>　　數(shù)據(jù)排序過程：</b></p><p>　　初始關(guān)鍵字 [49 38 65 97 76 13 27 49]</p><p>　　第一趟排序后 13 [38 65 97 76 49 27 49]</p><p>　　第二趟排序后 13 27 [65 97

81、 76 49 38 49]</p><p>　　第三趟排序后 13 27 38 [97 76 49 65 49]</p><p>　　第四趟排序后 13 27 38 49 [76 97 65 49 ]</p><p>　　第五趟排序后 13 27 38 49 49 [97 65 76]</p><p>　　第六趟排序后 13 27 38 49

82、 49 65 [97 76]</p><p>　　第七趟排序后 13 27 38 49 49 65 76 [97]</p><p>　　最后排序結(jié)果 13 27 38 49 49 65 76 97</p><p>　　從上述可見，算法的結(jié)構(gòu)是一個雙重循環(huán)。假設(shè)共有N個數(shù)據(jù)，則內(nèi)循環(huán)體的總數(shù)執(zhí)行次數(shù)為：N（N-1）=N*N/2，移動次數(shù)為(n+4)(n-1)/2，因此

83、時間復(fù)雜O(n*n)，內(nèi)循環(huán)體為一判斷語句，需要比較兩個關(guān)鍵字的大小，并且在滿足條件時要執(zhí)行交換過程。選擇排序算法只需要有限的幾個輔助內(nèi)存且與線性中元素的個數(shù)N無關(guān)，因此，算法的空間復(fù)雜性是常數(shù)級的，即O（1）。</p><p><b>　　4.5快速排序</b></p><p>　　快速排序（Quicksort）是對冒泡排序的一種改進。最有效、從而最廣泛使用的排序算

84、法之一是由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。</p><p><b>　　其算法如下：</b></p><p>　　設(shè)置兩個變量i、j，排序開

85、始的時候：i=0，j=n-1；</p><p>　　以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即 key=A[0]；</p><p>　　從j開始向前搜索，即由后開始向前搜索（j=j-1），找到第一個小于key的值A(chǔ)[j]，并與key交換；</p><p>　　從i開始向后搜索，即由前開始向后搜索（i=i+1），找到第一個大于key的A[i]，與key交換；<

86、;/p><p>　　重復(fù)第3、4、5步，直到 I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。找到并交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j-完成的最后另循環(huán)結(jié)束。)</p><p>　　例如：待排序的數(shù)組A的值分別是：（初始關(guān)鍵數(shù)據(jù)：X=49） 注意關(guān)鍵X永遠不變，永遠是和X進行比較，無論在什么位子，最后的目的就是把X放在中間，小的放

87、前面大的放后面如4.2所示：</p><p>　　初始關(guān)鍵字： 49 38 65 97 76 13 27 49</p><p>　　i j j </p>

88、;<p>　　進行1次交換之后：27 38 65 97 76 13 49</p><p>　　i i j</p><p>　　進行2次交換之后：27 38 97 76 13 65 49</p&g

89、t;<p>　　i j j</p><p>　　進行3次交換之后：27 38 13 97 76 65 49</p><p>　　i i j </p><p>　　進行4次交換之后：27 38 13

90、 76 97 65 49</p><p>　　i j j</p><p>　　完成一趟排序： 27 38 13 49 76 97 65 49</p><p>　　有序序列 ｛13 27 38 49 49

91、 65 76 97｝</p><p>　　圖4.3快速排序過程</p><p>　　快速排序的時間主要耗費在劃分操作上，對長度為k的區(qū)間進行劃分，共需k-1次關(guān)鍵字的比較。</p><p>　　在最壞情況是每次劃分選取的基準都是當前無序區(qū)中關(guān)鍵字最小(或最大)的記錄，劃分的結(jié)果是基準左邊的子區(qū)間為空(或右邊的子區(qū)間為空)，而劃分所得的另一個非空的子

92、區(qū)間中記錄數(shù)目，僅僅比劃分前的無序區(qū)中記錄個數(shù)減少一個。因此，快速排序必須做n-1次劃分，第i次劃分開始時區(qū)間長度為n-i+1，所需的比較次數(shù)為n-i(1≤i≤n-1)，故總的比較次數(shù)達到最大值：Cmax = n(n-1)/2=O(n2)</p><p>　　然而在最好情況下，每次劃分所取的基準都是當前無序區(qū)的"中值"記錄，劃分的結(jié)果是基準的左、右兩個無序子區(qū)間的長度大致相等。總的關(guān)

93、鍵字比較次數(shù)：0(nlgn)</p><p>　　在當前無序區(qū)中選取劃分的基準關(guān)鍵字是決定算法性能的關(guān)鍵，如下所示：</p><p>　　"三者取中"規(guī)則，即在當前區(qū)間里，將該區(qū)間首、尾和中間位置上的關(guān)鍵字比較，取三者之中值所對應(yīng)的記錄作為基準，在劃分開始前將該基準記錄和該區(qū)伺的第1個記錄進行交換，此后的劃分過程與上面所給的Partition算法完全相同。</p&

94、gt;<p>　　取位于low和high之間的隨機數(shù)k(low≤k≤high)，用R[k]作為基準。 選取基準最好的方法是用一個隨機函數(shù)產(chǎn)生一個取位于low和high之間的隨機數(shù)k(low≤k≤high)，用R[k]作為基準，這相當于強迫R[low..high]中的記錄是隨機分布的。用此方法所得到的快速排序一般稱為隨機的快速排序。</p><p>　　注意：隨機化的快速排序與一般的快速排序

95、算法差別很小。但隨機化后，算法的性能大大地提高了，尤其是對初始有序的文件，一般不可能導致最壞情況的發(fā)生。算法的隨機化不僅僅適用于快速排序，也適用于其它需要數(shù)據(jù)隨機分布的算法。</p><p>　　盡管快速排序的最壞時間為O(n2)，但就平均性能而言，它是基于關(guān)鍵字比較的內(nèi)部排序算法中速度最快者，快速排序亦因此而得名。它的平均時間復(fù)雜度為O(nlgn)。</p><p><b>　

96、　4.6堆排序</b></p><p>　　堆排序(Heap Sort) 是指利用堆積樹（堆）這種資料結(jié)構(gòu)所設(shè)計的一種排序算法，可以利用數(shù)組的特點快速定位指定索引的元素。</p><p>　　堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當前無序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡單。</p><p>　　排序之前首先建

97、堆，堆的定義如下：n個元素的序列｛k1,k2……，kn｝當且僅當滿足下關(guān)系時，稱之為堆。</p><p>　　若將和此序列對應(yīng)的一維數(shù)組看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中年有非終端結(jié)點的值均不大于或不小于其左、右孩子結(jié)點的值。由此,若序列｛k1,k2,……，kn｝是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值或（或最大值）下列兩個序列為堆，對應(yīng)的完全二叉樹如圖4.3所示：</

98、p><p>　　圖4.4（A）堆元素最大 （ b）堆元素最小</p><p>　　大根堆排序的基本思想</p><p>　　先將初始文件R[1..n]建成一個大根堆,此堆為初始的無序區(qū)</p><p>　　再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序

99、區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key</p><p>　　由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].

100、keys，同樣要將R[1..n-2]調(diào)整為堆。直到無序區(qū)只有一個元素為止。</p><p>　　大根堆排序算法的基本操作：</p><p>　　初始化操作：將R[1..n]構(gòu)造為初始堆；</p><p>　　每一趟排序的基本操作：將當前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調(diào)整為堆(亦稱重建堆)。</p><p>

101、;<b>　　算法：</b></p><p>　　for(i=(L/2);i>=1;i--)//將二叉樹轉(zhuǎn)換成堆</p><p>　　CreateHeap(i,L);//建堆</p><p>　　for(i=L-1,k=1;i>=1;i--,k++)</p><p><b>　　{</b>

102、;</p><p>　　temp=R[i+1];//堆（heap）的root值和最后一個值交換</p><p>　　R[i+1]=R[1];</p><p>　　R[1]=temp;</p><p>　　changes+=3;</p><p>　　CreateHeap(1,i);</p><p>

103、;<b>　　}</b></p><p>　　從上述分析：堆[排序的時間，主要由建立初始]堆和反復(fù)重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用CreateHeap實現(xiàn)的。</p><p>　　堆排序的最壞時間復(fù)雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件?！　《雅判蚴蔷偷嘏判?，輔助空間為O

104、(1)，由它是不穩(wěn)定的排序方法。</p><p>　　4.7六種排序方法討論</p><p>　　綜合比較上述的各種內(nèi)部排序方法，大致有如下結(jié)果（見下表）</p><p><b>　　表4.1</b></p><p><b>　　附注：</b></p><p>　　堆排序、冒

105、泡排序、希爾排序和快速排序中，在待排序的數(shù)據(jù)已經(jīng)基本有序是，花費時間最多的反而是快速排序，此是最不利于發(fā)揮其特長。</p><p>　　在以比較為基礎(chǔ)的排序方法中，“比較關(guān)鍵字的大小”和“將關(guān)鍵字從一個位置移動到另一個位置”這兩種操作的次數(shù)決定了算法的時間復(fù)雜性，它們是算法的時間復(fù)雜性的兩項指標。</p><p>　　在局部有序和待排序的關(guān)鍵字序列數(shù)目較小時，最佳的內(nèi)部排序方法是直接插入排

106、序。</p><p>　　在冒泡排序的每一趟中，只能將關(guān)鍵字最大或最小的元素移動到正確的置，其他關(guān)鍵字有可能在交換的過程中朝著與最終排序相反方向移動；快速排序的每一趟中，不僅能將樞軸的元素移動到正確的位置，而且其他關(guān)鍵字所移動的方向也與其最終排序的位置方向一致。</p><p>　　設(shè)有一個堆，取出堆中最大元素后，將它重新調(diào)整為堆，所需要的時間復(fù)雜度為O(nlogn)</p>

107、<p>　　假設(shè)待排序的關(guān)鍵字序列有n（例如，n=10000）個元素，若僅找出其中最大的k（例如k=10）個元素，則采有堆排序最省時間；若僅找出其中第k個最小元素，則采用快速排序最省時間</p><p>　　如何選擇好的排序方法：</p><p>　　沒有哪一種排序方法是絕對好的。每一種排序方都有優(yōu)缺點，適合于不同的環(huán)境。因此，在實際應(yīng)用中，應(yīng)根據(jù)具體情況進行選擇。首先，考慮排

108、序?qū)Ψ€(wěn)定性的要求，若要求穩(wěn)定，則只能在穩(wěn)定的排序方法中選取，否則可以在所有的方法中選取；其次要考慮待排序列的記錄數(shù)目n，若n較大，則可以在改進的方法中選取，否則在簡單方法中選?。蝗缓笤倏紤]其他因素。綜上所述，可得以上結(jié)論：</p><p>　　當待排序的序列的記錄數(shù)目n較大，記錄按關(guān)鍵字的值分布比較隨機，并且對排序穩(wěn)定必不作要求時，宜選用快速排序。</p><p>　　當待排序的序列的記錄

109、數(shù)目n較大，記錄按關(guān)鍵字的值分布可能出現(xiàn)升序或逆序的情況，并且對排序穩(wěn)定性不作要求時，宜選用堆排序。</p><p>　　當待排序的序列的記錄數(shù)目n較小，記錄的關(guān)鍵字的排列基本有序，分布比較隨機且對排序有穩(wěn)定性要求時，宜選用插入排序。</p><p>　　4、當待排序的序列的記錄數(shù)目n較小，并且對排序有穩(wěn)定性要求進，宜選用選擇排序；若記錄的關(guān)鍵字的值不接近逆序，也可選用直接插入排序。<

110、;/p><p>　　第5章 排序算法的改進</p><p>　　5.1雙向冒泡排序算法</p><p>　　對于輸入的子序列 L [ low…High ]看成豎著排列的“氣泡”,然后分別從上端 (Low)向底端 ( High)掃描。在掃描的過程中時刻注意兩個相鄰元素的順序 ,保證上端的元素小于下端的元素 ,這樣經(jīng)過一趟掃描后就使較大的元素沉到下面。然后再從底端向上端掃描

111、 ,由于在前一趟掃描過程中最大的元素已經(jīng)沉到最底端 ,所以這次掃描最大的元素不再參加排序 ,將剩下的元素進行排序 ,排序的過程中保證使得底端元素大于頂端元素。這樣反復(fù)的掃描 ,并不斷縮小排序空間 ,直到整個序列有序位置。這樣直觀上看 ,雙向冒泡排序法先讓重的氣泡沉到底下 ,然后讓輕的氣泡浮上來 ,然后再讓大的氣泡沉下去 ,讓次輕的氣泡浮上來 ,依次反復(fù) ,直到帶排序列有序為止。</p><p>　　算法是利用兩個

112、指針 low和 high記錄帶排序列區(qū)域 L [ low…h(huán)igh ] ,用指針變量 t記錄在每趟掃描過程中最近一次交換記錄的位置 ,在每次掃描開始 t的初始值分別為 Low或 high ,并且在掃描結(jié)束后再讓 t和 low或 high進行比較 ,如果發(fā)現(xiàn)某次 t值沒有改變 ,則說明序列已經(jīng)有序 ,并且用 break跳出循環(huán) ,提前結(jié)束排序。</p><p><b>　　代碼實現(xiàn)：</b>&

113、lt;/p><p>　　While (low < high)</p><p><b>　　{</b></p><p>　　t=low;//t指向帶排序區(qū)間的離最底端</p><p>　　For (i = low ; i < high ; i + + )</p><p><b>　

114、　{</b></p><p>　　if (L [ i ] > L [ i + 1 ] ) </p><p>　　{m=l[i];l[i]=l[i+1];l[i+1]=m;</p><p>　　t=i;} //記錄最近一次移動的關(guān)鍵字的位置</p><p>　　if(t

115、==low) break; //檢查是否待排關(guān)鍵字有序，如有序則退出循環(huán)，結(jié)束排序</p><p>　　else high=t; //縮小待排序列的范圍</p><p>　　for (i = high ; i > low ; i + + )</p><p>　　{ if (L[ i