《數(shù)據(jù)結(jié)構(gòu)(C語言) 各種排序算法性能比較 畢業(yè)論》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語言) 各種排序算法性能比較 畢業(yè)論（42頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、各種排序算法性能比較 畢業(yè)論文 各種排序算法性能比較 系 電子信息工程系 專業(yè) 電子信息工程技術(shù) 姓名 于廣振 班級 電信083（系統(tǒng)） 學(xué)號0801133115 指導(dǎo)教師 鄭雪芳 　 職稱 講師 設(shè)計時間 2010.11.22－2011.1.8 目錄 摘要： 3 第一章、引言 4 1.1、排序算法的背景 4 1.2、排序算法研究現(xiàn)狀 5 1.3、排序算法的意義 5

2、 1.4、排序算法設(shè)計目標(biāo) 6 第二章、排序算法概要設(shè)計 7 2.1、原始數(shù)據(jù) 7 2.2、輸出數(shù)據(jù) 7 2.3、數(shù)據(jù)處理 7 2..4、排序算法數(shù)據(jù)結(jié)構(gòu)設(shè)計 8 2 .5排序算法的性能評價 8 2.6、系統(tǒng)的模塊劃分及模塊功能 9 2.6.1、主程序模塊 9 2.6.2可排序表單元模塊 9 2.7、模塊的測試數(shù)據(jù) 10 第三章、排序基本算法 11 3.1、直接插入排序函數(shù) 11 3.1.1基本原理 11 3.1.2排序過程 11 3.1.3直接插入排序算法 11 3.1.4時間復(fù)雜度分析 13 3.2、直接選擇排序函數(shù) 13 3.2.1基本原理 13 3

3、.2.2排序過程 14 3.2.3直接選擇排序算法 14 3.2.4 時間復(fù)雜度分析 15 3.3冒泡排序函數(shù) 16 3.3.1基本原理 16 3.3.2排序過程 16 3.3.3冒泡排序算法 18 3.3.4 時間復(fù)雜度分析 19 3.4 Shell排序函數(shù) 19 3.4.1基本原理 19 3.4.2排序過程 20 3.4.3 Shell排序算法 21 3.4.4時間復(fù)雜度分析 22 3.5堆排序函數(shù) 23 3.5.1基本原理 23 3.5.2排序過程 23 3.5.3堆排序算法 27 3.6快速排序函數(shù) 28 3.6.1基本原理 28 3.6.2排序過

4、程 29 3.6.3快速排序算法 31 3.6.4快速排序時間復(fù)雜度分析 33 3.7排序主調(diào)用函數(shù) 33 3.7.1基本原理 33 3.7.2排序主調(diào)用算法 34 3.7.3排序主調(diào)用時間復(fù)雜度分析 35 第四章、運行與測試 36 第五章、結(jié)論 38 致謝 39 參考文獻(xiàn) 40 摘要： 在這兩年的專業(yè)基礎(chǔ)課的學(xué)習(xí)過程中，我們學(xué)習(xí)了程序設(shè)計基礎(chǔ)，面向?qū)ο蟪绦蛟O(shè)計，數(shù)據(jù)結(jié)構(gòu)——使用C+

5、+語言描述等課程。使得我們可以綜合運用所學(xué)知識，更進(jìn)一步的理解各個課程之間的聯(lián)系。不僅鞏固了以前所學(xué)過的知識，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識。在這個過程中我遇到了各種各樣的問題，同時在設(shè)計的過程中發(fā)現(xiàn)了自己的不足之處，對一些知識理解得不夠深刻。 我這次的題目是各種排序性能的比較，這就要求我首先必須掌握各種排序的原理，并且還要把各個排序結(jié)合起來綜合考慮。我在實現(xiàn)排序功能是沒有遇到太大的問題，但在進(jìn)行移動次數(shù)，比較次數(shù)和交換次數(shù)的統(tǒng)計中始終無法得出正確的結(jié)果，最終在指導(dǎo)老師的幫助下才完成。在程序?qū)懞煤螅x擇用來測試的數(shù)據(jù)也很重要，否則體現(xiàn)不出一些問題。在這個程序中，如果排序的數(shù)據(jù)太少，

6、則無法體現(xiàn)時間排名。 通過這次課程設(shè)計，使我對數(shù)據(jù)結(jié)構(gòu)有了更進(jìn)一步的認(rèn)識和了解，要通過不斷的上機操作才能更好地學(xué)習(xí)它，我也發(fā)現(xiàn)我的許多不足之處，對C++語言的一些庫函數(shù)不太了解，不能熟練掌握各種常用函數(shù)的功能，對函數(shù)調(diào)用的正確使用不夠熟悉，對C++中經(jīng)常出現(xiàn)的錯誤也不熟悉。通過這次課程設(shè)計，我更加體會到了實踐的重要性。??！ 排序算法是數(shù)據(jù)結(jié)構(gòu)這門課程核心內(nèi)容之 · 。它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)排序算法是為了將實際問題中）聽涉及的對象在計算機中對它們進(jìn)行處理。木文首先介紹排序的一些基木概念和一些常用的排

7、序方法，然后利用 VC + ＋開發(fā) · 個數(shù)據(jù)結(jié)構(gòu)的演示系統(tǒng)；該演示系統(tǒng)可以通過操作把數(shù)據(jù)結(jié)構(gòu)中的主要排序常見的排序算法（有冒泡排序、選擇排序、直接插入排序、希爾排序、快速排序、堆排序等）表示出來。該項目在收集各種排序方法的基礎(chǔ)上，對其特點、效率、適用性等在不同的數(shù)據(jù)集上做全面的分析和比較，并以動態(tài)演示的方式展示一些經(jīng)典排序算法運行程。 所使用的編程環(huán)境為TURBOC2。通過實驗可知，一般情況下,記錄規(guī)模較小時，直接插入排序較好；當(dāng)記錄規(guī)模較大且無序時，快速排序較好。 關(guān)鍵字：直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序； 第一章、引言 1.1、排序算

8、法的背景 21世紀(jì)是“信息”主導(dǎo)的世紀(jì)，是崇尚“創(chuàng)新與個性”發(fā)展的時代，體現(xiàn)“以人為本”、構(gòu)建“和諧社會”是社會發(fā)展的主流。然而隨著全球經(jīng)濟(jì)一體化進(jìn)程的不斷推進(jìn)，市場與人才的競爭日趨激烈。對于國家倡導(dǎo)發(fā)展的IT產(chǎn)業(yè)，需要培養(yǎng)大量的、適應(yīng)經(jīng)濟(jì)和科技發(fā)展的計算機人才。 眾所周知，近年來，一些用人單位對部分大學(xué)畢業(yè)生到了工作崗位后，需要1～2年甚至多年的訓(xùn)練才能勝任工作的“半成品”現(xiàn)象反映強烈。從中反映出單位對人才的需求越來越講究實用，社會要求學(xué)校培養(yǎng)學(xué)生的標(biāo)準(zhǔn)應(yīng)該和社會實際需求的標(biāo)準(zhǔn)相統(tǒng)一。對于IT業(yè)界來講，一方面需要一定的科研創(chuàng)新型人才，從事高端的技術(shù)研究，占領(lǐng)技術(shù)發(fā)展的高地；另一方面，更需

9、要計算機工程應(yīng)用、技術(shù)應(yīng)用及各類服務(wù)實施人才，這些人才可統(tǒng)稱“應(yīng)用型”人才。 應(yīng)用型?？平逃唵蔚刂v就是培養(yǎng)高層次應(yīng)用型人才的本科教育。其培養(yǎng)目標(biāo)應(yīng)是面向社會的高新技術(shù)產(chǎn)業(yè)，培養(yǎng)在工業(yè)、工程領(lǐng)域的生產(chǎn)、建設(shè)、管理、服務(wù)等第一線崗位，直接從事解決實際問題、維持工作正常運行的高等技術(shù)應(yīng)用型人才。這種人才，一方面掌握某一技術(shù)學(xué)科的基本知識和基本技能，另一方面又具有較強的解決實際問題的基本能力，他們常常是復(fù)合性、綜合性人才，受過較為完整的、系統(tǒng)的、有行業(yè)應(yīng)用背景的“職業(yè)” 項目訓(xùn)練，其最大的特色就是有較強的專業(yè)理論基礎(chǔ)支撐，能快速地適應(yīng)職業(yè)崗位并發(fā)揮作用。因此，可以說“應(yīng)用型人才培養(yǎng)既有本科人才培

10、養(yǎng)的一般要求，又有強化崗位能力的內(nèi)涵，它是在本科基礎(chǔ)之上的以‘工程師’層次培養(yǎng)為主的人才培養(yǎng)體系”，人才培養(yǎng)模式必須吸取一般本科教育和職業(yè)教育的長處，兼蓄并顧。“計算機科學(xué)與技術(shù)”專業(yè)教學(xué)指導(dǎo)委員會已經(jīng)在研究并指導(dǎo)實施計算機人才的“分類”培養(yǎng)，這需要我們轉(zhuǎn)變傳統(tǒng)的教育模式和教學(xué)方法，明確人才培養(yǎng)目標(biāo)，構(gòu)建課程體系，在保證“基礎(chǔ)的前提”下，重視素質(zhì)的養(yǎng)成，突出“工程性”、“技術(shù)應(yīng)用性”、“適應(yīng)性”概念，突出知識的應(yīng)用能力、專業(yè)技術(shù)應(yīng)用能力、工程實踐能力、組織協(xié)調(diào)能力、創(chuàng)新能力和創(chuàng)業(yè)精神，較好地體現(xiàn)與實施人才培養(yǎng)過程的“傳授知識，訓(xùn)練能力，培養(yǎng)素質(zhì)”三者的有機統(tǒng)一。 排序算法是在整個計算機科學(xué)一

11、與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。排序算法是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人一 I ' －智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)?。怀痰雀鞣N領(lǐng)域。本人在研究各種算法的過程中，對其特點、效率、適用性等在不同的數(shù)據(jù)集卜做全面的分析和比較，并以動態(tài)演示的方式展示一些經(jīng)典排序算法運行過程，目的有以下五個方面：做算法的對比研究，培養(yǎng)研究能力；開發(fā)一個獨立的軟件，培養(yǎng)程序設(shè)計和軟件開發(fā)能力；初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；為教學(xué)服務(wù)，研究結(jié)果 nJ 對抽象的 《 算法與數(shù)據(jù)結(jié)構(gòu) 》 的教學(xué)有一

12、定的輔助作用。 排序是計算機科學(xué)中最重要的研究問題之一, 它在計算機圖形、計算機輔助設(shè)計、機器人、模式識別及統(tǒng)計學(xué)等領(lǐng)域具有廣泛的應(yīng)用。由于它固有的理論上的重要性,2000年它被列為對科學(xué)和工程計算的研究與實踐影響最大的10大問題之一。其功能是將一個數(shù)據(jù)元素的任意序列重新排列成一個按關(guān)鍵字有序的序列。 1.2、排序算法研究現(xiàn)狀 隨著計一算湘 L 技術(shù)的口益發(fā)展，其應(yīng)用旱已不局限于簡單的數(shù)值運算。而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計以及插入、刪除、排序、查找等復(fù)雜的非數(shù)值處理和操作。排序算法的學(xué)習(xí)就是為以后利川計算機資源高效地開發(fā)非數(shù)值處理的計算機程序打下堅實的理論、方法和技術(shù)基礎(chǔ)。近來

13、國內(nèi)外專家學(xué)者們對排序算法又有了新的研究和發(fā)現(xiàn)。例如：我國山東大學(xué)的張峰和張金屯兩位教授共同研究了 《 我國植被數(shù)量分類和排序研究進(jìn)展 》 這課題。很值得有關(guān)部門去學(xué)習(xí)和研究。 1.3、排序算法的意義 排序是計算機程序設(shè)計中的一種重要操作。它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關(guān)鍵字有序的序列。 排序的方法很多，但是就其全面性能而言，很難提出一種被認(rèn)為是最好的方法，每一種方法都有各自的優(yōu)缺點，適合在不同的環(huán)境下使用。如果按排序過程中依據(jù)的不同原則對內(nèi)部排序方法進(jìn)行分類，則大致可分為直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序等六類。 此實驗通過對

14、直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序這幾種內(nèi)部排序算法進(jìn)行比較，能使我們更好的掌握這些排序的基本思想及排序算法。通過該題目的設(shè)計過程，可以加深理解各種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)上運算的實現(xiàn)，進(jìn)一步理解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，學(xué)會如何把學(xué)到的知識用于解決實際問題，培養(yǎng)我們的動手能力 1.4、排序算法設(shè)計目標(biāo) 本課程設(shè)計對以下排序算法進(jìn)行比較：直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序 待排序表的元素關(guān)鍵字為整數(shù)，用不同的測試數(shù)據(jù)做測試比較。比較的指標(biāo)為關(guān)鍵字的比較次數(shù)和關(guān)鍵字的移動次數(shù)。最后用圖、表格數(shù)據(jù)

15、匯總數(shù)據(jù)，以便對這些內(nèi)部排序算法進(jìn)行性能分析。 本課程設(shè)計首先介紹排序的一些基本概念和一些常用的排序方法，然后利用 VC 十＋開發(fā)一個數(shù)據(jù)結(jié)構(gòu)的演示系統(tǒng)；該演示系統(tǒng)可以通過操作把數(shù)據(jù)結(jié)構(gòu)中的主要排序常見的排序算法（直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序）表示出來。該項目在收集齊種排序方法的基礎(chǔ)上，對其特點、效率、適用性等在不同的數(shù)據(jù)集上做全面的分析和比較，并以動態(tài)演示的方式展示一些經(jīng)典排序算法運行程。 第二章、排序算法概要設(shè)計 2.1、原始數(shù)據(jù) 用戶輸入記錄的個數(shù)，數(shù)據(jù)由

16、隨機數(shù)產(chǎn)生器生成。 2.2、輸出數(shù)據(jù) 產(chǎn)生的隨機數(shù)分別用直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序這些排序方法進(jìn)行排序，輸出關(guān)鍵字的比較次數(shù)和移動次數(shù)。 2.3、數(shù)據(jù)處理 主程序 產(chǎn)生1組隨機數(shù) 起泡 排序 Shell排序 快速 排序 直接選擇排序 堆排序 記錄關(guān)鍵字的比較次數(shù)和移動次數(shù) 將隨機數(shù)保存在數(shù)組中 循環(huán)20次 輸出關(guān)鍵字的比較次數(shù)、移動次數(shù)的平均值 直接選擇排序 2..4、排序算法數(shù)據(jù)結(jié)構(gòu)設(shè)計 本程序中，考慮的內(nèi)容就是待排序?qū)ο?，排序的依?jù)是關(guān)鍵字之間的大小比較，故在每個節(jié)點的類型定義中，至少得包含關(guān)鍵

17、字key一項。不失一般性，這里就使用關(guān)鍵詞這一項，其他都省略，具體應(yīng)用加上其他數(shù)據(jù)項即可。被排序?qū)ο笫怯梢粋€個節(jié)點夠成，一個排序?qū)ο竽匕幌盗兄赶蛞淮?jié)點的指針，排序?qū)ο蟮拈L度。本程序功能簡單。 typedef struct { int key; /*關(guān)鍵字*/ }RecordNode; /*排序節(jié)點的類型*/ typedef struct { RecordNode *record; int n; /*排序?qū)ο蟮拇笮?/ }SortObject; /*排序節(jié)點的類型*/ 2 .5排序算法的性能評價 ( 1 ）執(zhí)行時問和所需的輔助空間若排序算法所需的輔助空間并不依

18、賴 J 七問題的規(guī)模 I , ，即輔助空問是 o ( l ) ，則稱之為就地排序（ In 一 PlaCe Sort ）。非就地排序一般要求的輔助空問為 o (n ）。 ( 2 ）算法本身的復(fù)雜程度排序算法的時間開銷：大多數(shù)排序算法的時問開銷主要是關(guān)鍵字之間的比較和記錄的移動。有的排序算法其執(zhí)行時間不僅依賴于問題的規(guī)模，還取決于輸入實例中數(shù)據(jù)的狀態(tài)。 2.6、系統(tǒng)的模塊劃分及模塊功能 Main Sort Method Quick Sort HeapSort InsertSort Select Sort BubbleSort

19、ShellSort Quick Output 2.6.1、主程序模塊 void main（） 2.6.2可排序表單元模塊 A．直接插入排序 void InsertSort (SortObject *p,unsigned long *compare,unsigned long *exchange) B.直接選擇排序 void SelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange) C.冒泡排序 void BubbleSort (SortObject *p,un

20、signed long *compare,unsigned long *exchange) D．Shell排序 void ShellSort(SortObject *p,int d,unsigned long *compare,unsigned long *exchange) E．堆排序 void SiftHeap(SortObject *pvector,int size,int p,unsigned long *compare,unsigned long *exchange)/*調(diào)整為堆*/ F．快速排序 void QuickSort(SortObject *pvector

21、,int left,int right,unsigned long *compare,unsigned long *exchange)/*6.快速排序*/ G．排序主調(diào)用函數(shù) void SortMethod(void) 2.7、模塊的測試數(shù)據(jù) 以關(guān)鍵字的數(shù)目分別為20，100，500為例,作為測試數(shù)據(jù) 第三章、排序基本算法 3.1、直接插入排序函數(shù) 3.1.1基本原理 假設(shè)待排序的n個記錄{R0,R1,…,Rn}順序存放在數(shù)組中，直接插入法在插入記錄Ri（i=

22、1,2,…n-1）時，記錄的集合被劃分為兩個區(qū)間[R0,Ri-1]和[Ri+1,Rn-1],其中，前一個子區(qū)間已經(jīng)排好序，后一個子區(qū)間是當(dāng)前未排序的部分，將關(guān)鍵碼Ki與Ki-1Ki-2，…，K0依次比較，找出應(yīng)該插入的位置，將記錄Ri插，然后將剩下的i-1個元素按關(guān)鍵詞大小依次插入該有序序列，沒插入一個元素后依然保持該序列有序，經(jīng)過i-1趟排序后即成為有序序列。每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。 3.1.2排序過程 關(guān)鍵字： [ 10 ] 3 25 20 8 第一趟： [ 3 10 ] 25 20 8 （將前兩個數(shù)

23、據(jù)排序） 第二趟： [ 3 10 25 20] 8 （將 25 放入前面數(shù)據(jù)中的適當(dāng)位置） 第三趟： [ 3 10 20 25 ] 8 （將 20 放入適當(dāng)?shù)奈恢茫? 第四趟： [ 3 8 10 20 25 ]（將 8 放入適當(dāng)?shù)奈恢茫? 3.1.3直接插入排序算法 void InsertSort(SortObject *p,unsigned long *compare,unsigned long *exchange) { int i,j; RecordNode temp; SortObject *pvector; if((pvector=(SortObject

24、 *)malloc(sizeof(SortObject)))==NULL) { printf("OverFollow!"); getchar(); exit(1); } for(i=0;in;i++)/* 復(fù)制數(shù)組*/ pvector->record[i]=p->record[i]; pvector->n=p->n; *compare=0; *exchange=0; for(i=1;in;i++) { temp=pvector->record[i]; (*exchange)++;

25、 j=i-1; while((temp.keyrecord[j].key)&&(j>=0)) { (*compare)++; (*exchange)++; pvector->record[j+1]=pvector->record[j]; j--; } if(j!=(i-1)) { pvector->record[j+1]=temp; (*exchange)++; } } f

26、ree(pvector); } 哨兵（監(jiān)視哨）有兩個作用：一是作為臨變量存放R[i]（當(dāng)前要進(jìn)行比較的關(guān)鍵字）的副本；二是在查找循環(huán)中用來監(jiān)視下標(biāo)變量j是否越界。 當(dāng)文件的初始狀態(tài)不同時，直接插入排序所耗費的時間是有很大差異的。最好情況是文件初態(tài)為正序，此時算法的時間復(fù)雜度為O(n)，最壞情況是文件初態(tài)為反序，相應(yīng)的時間復(fù)雜度為O(n2)，算法的平均時間復(fù)雜度是O(n2)。算法的輔助空間復(fù)雜度是O(1)，是一個就地排序。 3.1.4時間復(fù)雜度分析 直接插入排序算法必須進(jìn)行n-1趟。最好情況下，即初始序列有序，執(zhí)行n-1趟，但每一趟只比較一次，移動元素兩次，總的比較次數(shù)

27、是(n-1)，移動元素次數(shù)是2(n-1)。因此最好情況下的時間復(fù)雜度就是O(n)。最壞情況(非遞增)下，最多比較i次，因此需要的比較次數(shù)是：所以，時間復(fù)雜度為O(n2)。 3.2、直接選擇排序函數(shù) 3.2.1基本原理 待排序的一組數(shù)據(jù)元素中，選出最小的一個數(shù)據(jù)元素與第一個位置的數(shù)據(jù)元素交換；然后在剩下的數(shù)據(jù)元素當(dāng)中再找最小的與第二個位置的數(shù)據(jù)元素交換，循環(huán)到只剩下最后一個數(shù)據(jù)元素為止，依次類推直到所有記錄。第一趟從 n 個記錄中找出關(guān)鍵碼最小的記錄與第個記錄交換；第二趟，從第二個記錄開始的， 2 一 1 個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換；如此，第 i 趟，則從第 i 個記

28、錄開始的 n 一 i + l 個記錄中選出關(guān)鍵碼最小的記錄一與第 i 個記錄交換，占到招個序列按關(guān)鍵碼有序。 3.2.2排序過程 【示例】： 初始關(guān)鍵字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49

29、49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序結(jié)果 13 27 38 49 49 76 76 97 3.2.3直接選擇排序算法 void SelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange) { int i,j,k; RecordNode temp; SortObject *pvector; if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)

30、 { printf("OverFollow!"); getchar(); exit(1); } for(i=0;in;i++)/*復(fù)制數(shù)組*/ pvector->record[i]=p->record[i]; pvector->n=p->n; *compare=0; *exchange=0; for(i=0;in-1;i++) { k=i; for(j=i+1;jn;j++) { (*compare)++;

31、 if(pvector->record[j].keyrecord[k].key) k=j; } if(k!=i) { temp=pvector->record[i]; pvector->record[i]=pvector->record[k]; pvector->record[k]=temp; ( *exchange)+=3; } } free(pvector); } 選擇排序法的第一層循環(huán)從起始元素開始選到倒數(shù)第

32、二個元素,主要是在每次進(jìn)入的第二層循環(huán)之前,將外層循環(huán)的下標(biāo)賦值給臨時變量,接下來的第二層循環(huán)中,如果發(fā)現(xiàn)有比這個最小位置處的元素更小的元素,則將那個更小的元素的下標(biāo)賦給臨時變量,最后,在二層循環(huán)退出后,如果臨時變量改變,則說明,有比當(dāng)前外層循環(huán)位置更小的元素,需要將這兩個元素交換. 3.2.4 時間復(fù)雜度分析 該算法運行時間與元素的初始排列無關(guān)。不論初始排列如何，該算法都必須執(zhí)行n-1趟，每趟執(zhí)行n-i-1次關(guān)鍵字的比較，這樣總的比較次數(shù)為：所以，簡單選擇排序的最好、最壞和平均情況的時間復(fù)雜度都為O(n2)。 3.3冒泡排序函數(shù) 3.3.1基本原理 在每一趟冒泡排序中，依次比較相鄰

33、的兩個關(guān)鍵字大小，若為反序咋交換。經(jīng)過一趟起泡后，關(guān)鍵詞大的必須移到最后。按照這種方式進(jìn)行第一趟在序列（I[0]~I[n-1]）中從前往后進(jìn)行兩個相鄰元素的比較，若后者小，則交換，比較n-1次；第一趟排序結(jié)束，最大元素被交換到I[n-1]中，下一趟只需在子序列（I[0]~I[n-2]）中進(jìn)行；如果在某一趟排序中未交換元素，則不再進(jìn)行下一趟排序。將被排序的記錄數(shù)組J[1..n]垂直排列，每個記錄J[i]看作是重量為J[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復(fù)進(jìn)行，直到最后任何兩個氣泡都是輕者在上，重者在下為

34、止，最后可完成。 3.3.2排序過程 將被排序的記錄數(shù)組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復(fù)進(jìn)行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 （1）初始 　??? R[1..n]為無序區(qū)。 （2）第一趟掃描 　??? 從無序區(qū)底部向上依次比較相鄰的兩個氣泡的重量，若發(fā)現(xiàn)輕者在下、重者在上，則交換二者的位置。即依次比較(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；對于每對氣泡(R[j+1]

35、，R[j])，若R[j+1].key

36、9 13 13 13 13 13 13 13 　　38 49 27 27 27 27 27 27 　　65 38 49 38 38 38 38 38 　　97 65 38 49 49 49 49 49 　　76 97 65 49 49 49 49 49 　　13 76 97 65 65 65 65 65 　　27 27 76 97 76 76 76 76 　　 49 49 49 76 97 97 97 97 　Procedure BubbleSort(Var R : FileType) //從下往上掃描的起泡排序// 　　Begin 　　For I :

37、= 1 To N-1 Do //做N-1趟排序// 　　begin 　　NoSwap := True; //置未排序的標(biāo)志// 　　For J := N - 1 DownTo 1 Do //從底部往上掃描// 　　begin 　　If R[J+1]< R[J] Then //交換元素// 　　begin 　　Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp; 　　NoSwap := False 　　end; 　　end; 　　If NoSwap Then Return//本趟排序中未發(fā)生交換，則終止算法//

38、　　end 　　End; //BubbleSort// 3.3.3冒泡排序算法 void BubbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange) { int i,j,noswap; RecordNode temp; SortObject *pvector; if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL) { printf("OverFollow!");

39、 getchar(); exit(1); } for(i=0;in;i++)/* 復(fù)制數(shù)組*/ pvector->record[i]=p->record[i]; pvector->n=p->n; *compare=0; *exchange=0; for(i=0;in-1;i++) { noswap=1; for(j=0;jn-i-1;j++) { (*compare)++; if(pvect

40、or->record[j+1].keyrecord[j].key) { temp=pvector->record[j]; pvector->record[j]=pvector->record[j+1]; pvector->record[j+1]=temp; (*exchange)+=3; noswap=0; } } if(noswap) break; } free(pvector); } 起泡排序的結(jié)束條件為

41、：最后一趟沒有進(jìn)行“交換”。從起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經(jīng)過一趟起泡，無序序列的長度只縮小1。 [算法思想]：將被排序的記錄數(shù)組R[1..n]垂直排列，每個記錄J[i]看作是重量為J[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組J：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復(fù)進(jìn)行，直到最后任何兩個氣泡都是輕者在上，重者在下為止 3.3.4 時間復(fù)雜度分析 當(dāng)原始數(shù)據(jù)正向有序時，冒泡排序出現(xiàn)最好情況。此時，只需進(jìn)行一趟排序，作n-1次關(guān)鍵字比較，因此最好情況下的時間復(fù)雜度是O(n)。當(dāng)原始

42、數(shù)據(jù)反向有序時，冒泡排序出現(xiàn)最壞情況。此時，需進(jìn)行n-1趟排序，第i趟需作(n-i)次關(guān)鍵字間的比較，并且需執(zhí)行(n-i)次元素交換，所以，比較次數(shù)為：因此,最壞情況下的時間復(fù)雜度為O(n2)。 3.4 Shell排序函數(shù) 3.4.1基本原理 Shell排序又稱縮小增量排序,Shell排序法是以創(chuàng)建者Donald Shell的名字命名的.Shell排序法是對相鄰指定距離(稱為間隔)的元素進(jìn)行比較,已知到使用當(dāng)前間隔進(jìn)行比較的元素都按順序排序為止.Shell把間隔縮小一半,然后繼續(xù)處理,當(dāng)間隔最終變?yōu)?,并且不再出現(xiàn)變化時,Shell排序也就完成了其處理過程.先取一個整數(shù)d1

43、錄分成d1個組，所有距離為d1倍數(shù)的記錄放在一組中，先在各組內(nèi)排序；然后去d2

44、 　　38 27 　　|-------------------| 　　65 49* 　　|-------------------| 　　97 55 　　|-------------------| 　　76 04 　　|-------------------| 　　一趟結(jié)果 　　13 27 49* 55 04 49 38 65 97 76 　　d=3 　　13 27 49* 55 04 49 38 65 97 76 　　13 55 38 76 　　|------------|------------|------------| 　　27

45、04 65 　　|------------|------------| 　　49* 49 97 　　|------------|------------| 　　二趟結(jié)果 　　13 04 49* 38 27 49 55 65 97 76 　　d=1 　　13 04 49* 38 27 49 55 65 97 76 　　|----|----|----|----|----|----|----|----|----| 　　三趟結(jié)果 　　04 13 27 38 49* 49 55 65 76 97 3.4.3 Shell排序算法 void ShellSo

46、rt(SortObject *p,int d,unsigned long *compare,unsigned long *exchange) { int i,j,increment; RecordNode temp; SortObject *pvector; if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL) { printf("OverFollow!"); getchar(); exit(1); } for(i=0

47、;in;i++)/* 復(fù)制數(shù)組*/ pvector->record[i]=p->record[i]; pvector->n=p->n; *compare=0; *exchange=0; for(increment=d;increment>0;increment/=2) { for(i=increment;in;i++) { temp=pvector->record[i]; (*exchange)++; j=i-increment;

48、 while(j>=0&&temp.keyrecord[j].key) { (*compare)++; pvector->record[j+increment]=pvector->record[j]; (*exchange)++; j-=increment; } pvector->record[j+increment]=temp; (*exchange)++; }

49、 } free(pvector); } 當(dāng)增量d=1時，ShellPass和InsertSort基本一致，只是由于沒有哨兵而在內(nèi)循環(huán)中增加了一個循環(huán)判定條件"j>0"，以防下標(biāo)越界。 3.4.4時間復(fù)雜度分析 希爾排序是按照不同步長對元素進(jìn)行插入排序，當(dāng)剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快；當(dāng)元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨摺Ｋ?，希爾排序的時間復(fù)雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其

50、穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。所以希爾排序是不穩(wěn)定的，其時間復(fù)雜度為O(n ^2)。 3.5堆排序函數(shù) 3.5.1基本原理 堆排序思想很簡單，就是每次把關(guān)鍵詞調(diào)整為堆，取出堆頂元素與堆中最后一個元素交換，同時令堆得大小減一，把剩余的一些元素重新調(diào)整為堆，重復(fù)此過程，直到堆中只剩一個元素，n 個關(guān)鍵字序列 kl , k2 ， … ， kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)（簡稱為堆性質(zhì)） : ( l ) ki<= k2i 且 ki<=k2i+1或（ 2 ）ki>= k2i 且 ki>=k2i+1。若將此序列所存儲的向量 R 「 1…n ］看做是一棵完全二叉樹的存儲結(jié)構(gòu)，則

51、堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的關(guān)鍵字均不大于（或不小于）其左右孩子（若存在）結(jié)點的關(guān)鍵字。根結(jié)點（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最小者的堆稱為小根堆。根結(jié)點（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最大者，稱為大根堆。 注意： ① 堆中任一子樹亦是堆。 ② 以上討論的堆實際上是人叉堆，類似地可定義 k 叉堆。 3.5.2排序過程 堆排序是一樹形選擇排序。堆排序的特點是：在排序過程中，將 R 「1… n 〕 看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之問的內(nèi)在關(guān)系，在當(dāng)前無序區(qū)中選抒關(guān)鍵字最大（或最?。┑挠涗洝Ｏ旅鎸膶嶋H數(shù)

52、據(jù)中演示其排序中的各個操作。原始數(shù)組： 22 53 72 1 1 34 44 11 15 28 3 10 65 第一步，從樹頂?shù)綐淙~把數(shù)填充進(jìn)入，建立堆。紅色為卜一次交換的兩個數(shù)日宇列）。 使記錄遞增有序，進(jìn)一步排序。第一次交換： 第二次交換： 第三次交換： 第四次交換： 第五次交換： 第六次交換： 第七次交換： 第八次交換： 第九次交換： 全程交換完成，得到最小值為 3 并且輸出它。從序列中刪除 3 ，重新建立堆。以次循環(huán)，直到全部輸出完成為止。 3.5.3堆排序算法 void HeapSort(SortOb

53、ject *p,unsigned long *compare,unsigned long *exchange)/*5.堆排序*/ { int i,n; RecordNode temp; SortObject *pvector; if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL) { printf("OverFollow!"); getchar(); exit(1); } for(i=0;in;i++)/* 復(fù)制數(shù)組*/

54、 pvector->record[i]=p->record[i]; pvector->n=p->n; *compare=0; *exchange=0; n=pvector->n; for(i=n/2-1;i>=0;i--) SiftHeap(pvector,n,i,compare,exchange);/*首先構(gòu)造第一個堆*/ for(i=n-1;i>0;i--) { temp=pvector->record[0]; pvector->record[0]=pvector->record[i]; pvector

55、->record[i]=temp; (*exchange)+=3; SiftHeap(pvector,i,0,compare,exchange); }/*重建新堆*/ free(pvector); } 當(dāng)增量d=1時，ShellPass和InsertSort基本一致，只是由于沒有哨兵而在內(nèi)循環(huán)中增加了一個循環(huán)判定條件"j>0"，以防下標(biāo)越界。 3.5.4時間復(fù)雜度分析 　堆排序的時間，主要由建立初始堆和反復(fù)重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用Heapify實現(xiàn)的。堆排序的最壞時間復(fù)雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。

56、由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是不穩(wěn)定的，算法時間復(fù)雜度O(nlog n)。 3.6快速排序函數(shù) 3.6.1基本原理 首先我們選擇一個中間值 middle （程序中我們可使用數(shù)組中間值），把比中問值小的放在其左邊，比中問值大的放在其右邊。由于這個排序算法較復(fù)雜，我們先給出其進(jìn)行一次排序的程序框架。在待排序的個記錄中任意取一個記錄（通常取第一個記錄）為區(qū)分標(biāo)準(zhǔn)，把所有小于該排序的記錄移到左邊，把所有大于該排序碼的記錄移到右邊，中級放所選記錄，為一趟快速排序。然后對前后兩個子序列分別重新上述過程，直到所有記錄都排好序。對任意給定的序列中某個元素，經(jīng)

57、過一趟排序后，將原序列分割成兩個子序列(Rp(0),Rp(1),…,Rp(s-1))和(Rp(s+1),Rp(s+2),…,Rp(n-1))，其中前一個子序列中的所有元素的關(guān)鍵詞均小于或等于該元素的關(guān)鍵詞值Kp(s)，后一個子序列中元素的關(guān)鍵詞均大于或等于Kp(s)。稱該元素Rp(s)為分割元素，子序列(Rp(0),Rp(1),…,Rp(s-1))為其低端序列，(Rp(0),Rp(1),…,Rp(s-1))為其高端序列。很明顯，以后只需對低端和高端序列分別進(jìn)行快速排序，直到子序列為空或只有一個元素時結(jié)束，最后得到有序序列?？傊?，每趟使表的第一個元素放在適當(dāng)位置，將表兩分，再對兩子表進(jìn)行同樣的遞

58、歸劃分，直至劃分的子表長度為1！ 3.6.2排序過程 假設(shè)要排序的數(shù)組是A[1]……A[N]，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是： 1）、設(shè)置兩個變量I、J，排序開始的時候I：=1，J：=N； 2）以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A[1]； 3）、從J開始向前搜索，即由后開始向前搜索（J：=J-1），找到第一個小于X的值，兩者交換； 4）、從I開始向后搜索，即由前開始向后搜索（I：=I+1），找到第一個大于X的值，

59、兩者交換； 5）、重復(fù)第3、4步，直到I=J； 例如：待排序的數(shù)組A的值分別是：（初始關(guān)鍵數(shù)據(jù)X：=49） A[1] A[2] A[3] A[4] A[5] A[6] A[7]： 49 38 65 97 76 13 27 進(jìn)行第一次交換后： 27 38 65 97 76 13 49

60、 ( 按照算法的第三步從后面開始找 進(jìn)行第二次交換后： 27 38 49 97 76 13 65 ( 按照算法的第四步從前面開始找>X的值，65>49,兩者交換，此時I：=3 ) 進(jìn)行第三次交換后： 27 38 13 97 76 49 65 ( 按照算法的第五步將又一次執(zhí)行算法的第三步從后開始找 進(jìn)行第四次交換后： 27 38 13

61、 49 76 97 65 ( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時J：=4 ) 此時再執(zhí)行第三不的時候就發(fā)現(xiàn)I=J，從而結(jié)束一躺快速排序，那么經(jīng)過一躺快速排序之后的結(jié)果是：27 38 13 49 76 97 65，即所以大于49的數(shù)全部在49的后面，所以小于49的數(shù)全部在49的前面。 快速排序就是遞歸調(diào)用此過程——在以49為中點分割這個數(shù)據(jù)序列，分別對前面一部分和后面一部分進(jìn)行類似的快速排序，從而完成全部數(shù)據(jù)序

62、列的快速排序，最后把此數(shù)據(jù)序列變成一個有序的序列，根據(jù)這種思想對于上述數(shù)組A的快速排序的全過程如圖6所示： 初始狀態(tài) {49 38 65 97 76 13 27} 進(jìn)行一次快速排序之后劃分為 {27 38 13} 49 {76 97 65} 分別對前后兩部分進(jìn)行快速排序 {13} 27 {38} 結(jié)束 結(jié)束 {49 65}

63、 76 {97} 49 {65} 結(jié)束 結(jié)束 1）、設(shè)有N（假設(shè)N=10）個數(shù)，存放在S數(shù)組中； 2）、在S[1。。N]中任取一個元素作為比較基準(zhǔn)，例如取T=S[1]，起目的就是在定出T應(yīng)在排序結(jié)果中的位置K，這個K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的數(shù)都小于S[K]，在S[K]以后的數(shù)都大于S[K]

64、； 3）、利用分治思想（即大化小的策略）可進(jìn)一步對S[1。。K-1]和S[K+1。。N]兩組數(shù)據(jù)再進(jìn)行快速排序直到分組對象只有一個數(shù)據(jù)為止。 如具體數(shù)據(jù)如下，那么第一躺快速排序的過程是： 數(shù)組下標(biāo)： 1 2 3 4 5 6 7 8 9 10 45 36 18 53 72 30 48 93 15 36 （1） 36 36 18 53 72 30

65、48 93 15 45 （2） 36 36 18 45 72 30 48 93 15 53 （3） 36 36 18 15 72 30 48 93 45 53 （4） 36 36 18 15 45 30 48 93 72 53 （5） 36 36 18 15 30

66、 45 48 93 72 53 通過一躺排序?qū)?5放到應(yīng)該放的位置K，這里K=6，那么再對S[1。。5]和S[6。。10]分別進(jìn)行快速排序 3.6.3快速排序算法 void QuickSort(SortObject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)/*6.快速排序*/ { int i,j; RecordNode temp; if(left>=right) return; i=left; j=right; temp=pvector->record[i]; (*exchange)++; while(i!=j) { while((pvector->record[j].key>=temp.key)&&(j>i)) { (*compare)++; j--; }