數(shù)據(jù)結構(C語言) 各種排序算法性能比較 畢業(yè)論

各種排序算法性能比較畢業(yè)論文 各種排序算法性能比較 系 電子信息工程系 專業(yè) 電子信息工程技術 姓名 于廣振 班級 電信083（系統(tǒng)） 學號0801133115指導教師 鄭雪芳 職稱 講師 設計時間 2010.11.222011.1.8 目錄摘要：3第一章、引言41.1、排序算法的背景41.2、排序算法研究現(xiàn)狀51.3、排序算法的意義51.4、排序算法設計目標6第二章、排序算法概要設計72.1、原始數(shù)據(jù)72.2、輸出數(shù)據(jù)72.3、數(shù)據(jù)處理72.4、排序算法數(shù)據(jù)結構設計82 .5排序算法的性能評價82.6、系統(tǒng)的模塊劃分及模塊功能92.6.1、主程序模塊92.6.2可排序表單元模塊92.7、模塊的測試數(shù)據(jù)10第三章、排序基本算法113.1、直接插入排序函數(shù)113.1.1基本原理113.1.2排序過程113.1.3直接插入排序算法113.1.4時間復雜度分析133.2、直接選擇排序函數(shù)133.2.1基本原理133.2.2排序過程143.2.3直接選擇排序算法143.2.4 時間復雜度分析153.3冒泡排序函數(shù)163.3.1基本原理163.3.2排序過程163.3.3冒泡排序算法183.3.4 時間復雜度分析193.4 Shell排序函數(shù)193.4.1基本原理193.4.2排序過程203.4.3 Shell排序算法213.4.4時間復雜度分析223.5堆排序函數(shù)233.5.1基本原理233.5.2排序過程233.5.3堆排序算法273.6快速排序函數(shù)283.6.1基本原理283.6.2排序過程293.6.3快速排序算法313.6.4快速排序時間復雜度分析333.7排序主調(diào)用函數(shù)333.7.1基本原理333.7.2排序主調(diào)用算法343.7.3排序主調(diào)用時間復雜度分析35第四章、運行與測試36第五章、結論38致謝39參考文獻40 摘要：在這兩年的專業(yè)基礎課的學習過程中，我們學習了程序設計基礎，面向對象程序設計，數(shù)據(jù)結構使用C+語言描述等課程。使得我們可以綜合運用所學知識，更進一步的理解各個課程之間的聯(lián)系。不僅鞏固了以前所學過的知識，而且學到了很多在書本上所沒有學到過的知識。在這個過程中我遇到了各種各樣的問題，同時在設計的過程中發(fā)現(xiàn)了自己的不足之處，對一些知識理解得不夠深刻。我這次的題目是各種排序性能的比較，這就要求我首先必須掌握各種排序的原理，并且還要把各個排序結合起來綜合考慮。我在實現(xiàn)排序功能是沒有遇到太大的問題，但在進行移動次數(shù)，比較次數(shù)和交換次數(shù)的統(tǒng)計中始終無法得出正確的結果，最終在指導老師的幫助下才完成。在程序寫好后，選擇用來測試的數(shù)據(jù)也很重要，否則體現(xiàn)不出一些問題。在這個程序中，如果排序的數(shù)據(jù)太少，則無法體現(xiàn)時間排名。通過這次課程設計，使我對數(shù)據(jù)結構有了更進一步的認識和了解，要通過不斷的上機操作才能更好地學習它，我也發(fā)現(xiàn)我的許多不足之處，對C+語言的一些庫函數(shù)不太了解，不能熟練掌握各種常用函數(shù)的功能，對函數(shù)調(diào)用的正確使用不夠熟悉，對C+中經(jīng)常出現(xiàn)的錯誤也不熟悉。通過這次課程設計，我更加體會到了實踐的重要性。  ！排序算法是數(shù)據(jù)結構這門課程核心內(nèi)容之 · 。它是計算機程序設計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎，廣泛的應用于信息學、系統(tǒng)工程等各種領域。學習排序算法是為了將實際問題中）聽涉及的對象在計算機中對它們進行處理。木文首先介紹排序的一些基木概念和一些常用的排序方法，然后利用 VC + 開發(fā) · 個數(shù)據(jù)結構的演示系統(tǒng)；該演示系統(tǒng)可以通過操作把數(shù)據(jù)結構中的主要排序常見的排序算法（有冒泡排序、選擇排序、直接插入排序、希爾排序、快速排序、堆排序等）表示出來。該項目在收集各種排序方法的基礎上，對其特點、效率、適用性等在不同的數(shù)據(jù)集上做全面的分析和比較，并以動態(tài)演示的方式展示一些經(jīng)典排序算法運行程。所使用的編程環(huán)境為TURBOC2。通過實驗可知，一般情況下,記錄規(guī)模較小時，直接插入排序較好；當記錄規(guī)模較大且無序時，快速排序較好。關鍵字：直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序；第一章、引言1.1、排序算法的背景21世紀是“信息”主導的世紀，是崇尚“創(chuàng)新與個性”發(fā)展的時代，體現(xiàn)“以人為本”、構建“和諧社會”是社會發(fā)展的主流。然而隨著全球經(jīng)濟一體化進程的不斷推進，市場與人才的競爭日趨激烈。對于國家倡導發(fā)展的IT產(chǎn)業(yè)，需要培養(yǎng)大量的、適應經(jīng)濟和科技發(fā)展的計算機人才。眾所周知，近年來，一些用人單位對部分大學畢業(yè)生到了工作崗位后，需要12年甚至多年的訓練才能勝任工作的“半成品”現(xiàn)象反映強烈。從中反映出單位對人才的需求越來越講究實用，社會要求學校培養(yǎng)學生的標準應該和社會實際需求的標準相統(tǒng)一。對于IT業(yè)界來講，一方面需要一定的科研創(chuàng)新型人才，從事高端的技術研究，占領技術發(fā)展的高地；另一方面，更需要計算機工程應用、技術應用及各類服務實施人才，這些人才可統(tǒng)稱“應用型”人才。應用型?？平逃?，簡單地講就是培養(yǎng)高層次應用型人才的本科教育。其培養(yǎng)目標應是面向社會的高新技術產(chǎn)業(yè)，培養(yǎng)在工業(yè)、工程領域的生產(chǎn)、建設、管理、服務等第一線崗位，直接從事解決實際問題、維持工作正常運行的高等技術應用型人才。這種人才，一方面掌握某一技術學科的基本知識和基本技能，另一方面又具有較強的解決實際問題的基本能力，他們常常是復合性、綜合性人才，受過較為完整的、系統(tǒng)的、有行業(yè)應用背景的“職業(yè)” 項目訓練，其最大的特色就是有較強的專業(yè)理論基礎支撐，能快速地適應職業(yè)崗位并發(fā)揮作用。因此，可以說“應用型人才培養(yǎng)既有本科人才培養(yǎng)的一般要求，又有強化崗位能力的內(nèi)涵，它是在本科基礎之上的以工程師層次培養(yǎng)為主的人才培養(yǎng)體系”，人才培養(yǎng)模式必須吸取一般本科教育和職業(yè)教育的長處，兼蓄并顧。“計算機科學與技術”專業(yè)教學指導委員會已經(jīng)在研究并指導實施計算機人才的“分類”培養(yǎng)，這需要我們轉變傳統(tǒng)的教育模式和教學方法，明確人才培養(yǎng)目標，構建課程體系，在保證“基礎的前提”下，重視素質的養(yǎng)成，突出“工程性”、“技術應用性”、“適應性”概念，突出知識的應用能力、專業(yè)技術應用能力、工程實踐能力、組織協(xié)調(diào)能力、創(chuàng)新能力和創(chuàng)業(yè)精神，較好地體現(xiàn)與實施人才培養(yǎng)過程的“傳授知識，訓練能力，培養(yǎng)素質”三者的有機統(tǒng)一。排序算法是在整個計算機科學一與技術領域上廣泛被使用的術語。排序算法是計算機程序設計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人一 I ' 智能等的重要基礎，廣泛的應用于信息學、系統(tǒng)??；程等各種領域。本人在研究各種算法的過程中，對其特點、效率、適用性等在不同的數(shù)據(jù)集卜做全面的分析和比較，并以動態(tài)演示的方式展示一些經(jīng)典排序算法運行過程，目的有以下五個方面：做算法的對比研究，培養(yǎng)研究能力；開發(fā)一個獨立的軟件，培養(yǎng)程序設計和軟件開發(fā)能力；初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能；提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；為教學服務，研究結果 nJ 對抽象的 算法與數(shù)據(jù)結構 的教學有一定的輔助作用。排序是計算機科學中最重要的研究問題之一, 它在計算機圖形、計算機輔助設計、機器人、模式識別及統(tǒng)計學等領域具有廣泛的應用。由于它固有的理論上的重要性,2000年它被列為對科學和工程計算的研究與實踐影響最大的10大問題之一。其功能是將一個數(shù)據(jù)元素的任意序列重新排列成一個按關鍵字有序的序列。1.2、排序算法研究現(xiàn)狀隨著計一算湘 L 技術的口益發(fā)展，其應用旱已不局限于簡單的數(shù)值運算。而涉及到問題的分析、數(shù)據(jù)結構框架的設計以及插入、刪除、排序、查找等復雜的非數(shù)值處理和操作。排序算法的學習就是為以后利川計算機資源高效地開發(fā)非數(shù)值處理的計算機程序打下堅實的理論、方法和技術基礎。近來國內(nèi)外專家學者們對排序算法又有了新的研究和發(fā)現(xiàn)。例如：我國山東大學的張峰和張金屯兩位教授共同研究了 我國植被數(shù)量分類和排序研究進展 這課題。很值得有關部門去學習和研究。1.3、排序算法的意義排序是計算機程序設計中的一種重要操作。它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關鍵字有序的序列。排序的方法很多，但是就其全面性能而言，很難提出一種被認為是最好的方法，每一種方法都有各自的優(yōu)缺點，適合在不同的環(huán)境下使用。如果按排序過程中依據(jù)的不同原則對內(nèi)部排序方法進行分類，則大致可分為直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序等六類。此實驗通過對直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序這幾種內(nèi)部排序算法進行比較，能使我們更好的掌握這些排序的基本思想及排序算法。通過該題目的設計過程，可以加深理解各種數(shù)據(jù)結構的邏輯結構、存儲結構及相應上運算的實現(xiàn)，進一步理解和熟練掌握課本中所學的各種數(shù)據(jù)結構，學會如何把學到的知識用于解決實際問題，培養(yǎng)我們的動手能力1.4、排序算法設計目標本課程設計對以下排序算法進行比較：直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序待排序表的元素關鍵字為整數(shù)，用不同的測試數(shù)據(jù)做測試比較。比較的指標為關鍵字的比較次數(shù)和關鍵字的移動次數(shù)。最后用圖、表格數(shù)據(jù)匯總數(shù)據(jù)，以便對這些內(nèi)部排序算法進行性能分析。本課程設計首先介紹排序的一些基本概念和一些常用的排序方法，然后利用 VC 十開發(fā)一個數(shù)據(jù)結構的演示系統(tǒng)；該演示系統(tǒng)可以通過操作把數(shù)據(jù)結構中的主要排序常見的排序算法（直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序）表示出來。該項目在收集齊種排序方法的基礎上，對其特點、效率、適用性等在不同的數(shù)據(jù)集上做全面的分析和比較，并以動態(tài)演示的方式展示一些經(jīng)典排序算法運行程。第二章、排序算法概要設計2.1、原始數(shù)據(jù)用戶輸入記錄的個數(shù)，數(shù)據(jù)由隨機數(shù)產(chǎn)生器生成。2.2、輸出數(shù)據(jù)產(chǎn)生的隨機數(shù)分別用直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序這些排序方法進行排序，輸出關鍵字的比較次數(shù)和移動次數(shù)。2.3、數(shù)據(jù)處理主程序產(chǎn)生1組隨機數(shù)起泡排序Shell排序快速排序直接選擇排序堆排序記錄關鍵字的比較次數(shù)和移動次數(shù)將隨機數(shù)保存在數(shù)組中循環(huán)20次輸出關鍵字的比較次數(shù)、移動次數(shù)的平均值直接選擇排序 2.4、排序算法數(shù)據(jù)結構設計本程序中，考慮的內(nèi)容就是待排序對象，排序的依據(jù)是關鍵字之間的大小比較，故在每個節(jié)點的類型定義中，至少得包含關鍵字key一項。不失一般性，這里就使用關鍵詞這一項，其他都省略，具體應用加上其他數(shù)據(jù)項即可。被排序對象是由一個個節(jié)點夠成，一個排序對象呢包含一系列指向一串節(jié)點的指針，排序對象的長度。本程序功能簡單。typedef structint key; /*關鍵字*/RecordNode; /*排序節(jié)點的類型*/typedef structRecordNode *record;int n; /*排序對象的大小*/SortObject; /*排序節(jié)點的類型*/2 .5排序算法的性能評價 ( 1 ）執(zhí)行時問和所需的輔助空間若排序算法所需的輔助空間并不依賴 J 七問題的規(guī)模 I , ，即輔助空問是 o ( l ) ，則稱之為就地排序（ In 一 PlaCe Sort ）。非就地排序一般要求的輔助空問為 o (n ）。 ( 2 ）算法本身的復雜程度排序算法的時間開銷：大多數(shù)排序算法的時問開銷主要是關鍵字之間的比較和記錄的移動。有的排序算法其執(zhí)行時間不僅依賴于問題的規(guī)模，還取決于輸入實例中數(shù)據(jù)的狀態(tài)。2.6、系統(tǒng)的模塊劃分及模塊功能MainSortMethodQuickSortHeapSortInsertSortSelectSortBubbleSortShellSortQuickOutput2.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,unsigned long *compare,unsigned long *exchange)DShell排序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,int left,int right,unsigned long *compare,unsigned long *exchange)/*6.快速排序*/G排序主調(diào)用函數(shù)void SortMethod(void)2.7、模塊的測試數(shù)據(jù)以關鍵字的數(shù)目分別為20，100，500為例,作為測試數(shù)據(jù)第三章、排序基本算法3.1、直接插入排序函數(shù)3.1.1基本原理假設待排序的n個記錄R0,R1,Rn順序存放在數(shù)組中，直接插入法在插入記錄Ri（i=1,2,n-1）時，記錄的集合被劃分為兩個區(qū)間R0,Ri-1和Ri+1,Rn-1,其中，前一個子區(qū)間已經(jīng)排好序，后一個子區(qū)間是當前未排序的部分，將關鍵碼Ki與Ki-1Ki-2，K0依次比較，找出應該插入的位置，將記錄Ri插，然后將剩下的i-1個元素按關鍵詞大小依次插入該有序序列，沒插入一個元素后依然保持該序列有序，經(jīng)過i-1趟排序后即成為有序序列。每次將一個待排序的記錄，按其關鍵字大小插入到前面已經(jīng)排好序的子文件中的適當位置，直到全部記錄插入完成為止。3.1.2排序過程關鍵字： 10 3 25 20 8 第一趟： 3 10 25 20 8 （將前兩個數(shù)據(jù)排序）第二趟： 3 10 25 20 8 （將 25 放入前面數(shù)據(jù)中的適當位置）第三趟： 3 10 20 25 8 （將 20 放入適當?shù)奈恢茫┑谒奶耍?3 8 10 20 25 （將 8 放入適當?shù)奈恢茫?.1.3直接插入排序算法void InsertSort(SortObject *p,unsigned long *compare,unsigned long *exchange)int i,j;RecordNode temp; SortObject *pvector;if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL)printf("OverFollow!");getchar();exit(1);for(i=0;i<p->n;i+)/* 復制數(shù)組*/pvector->recordi=p->recordi;pvector->n=p->n;*compare=0;*exchange=0;for(i=1;i<pvector->n;i+) temp=pvector->recordi; (*exchange)+; j=i-1; while(temp.key<pvector->recordj.key)&&(j>=0) (*compare)+; (*exchange)+; pvector->recordj+1=pvector->recordj; j-; if(j!=(i-1) pvector->recordj+1=temp; (*exchange)+; free(pvector);哨兵（監(jiān)視哨）有兩個作用：一是作為臨變量存放Ri（當前要進行比較的關鍵字）的副本；二是在查找循環(huán)中用來監(jiān)視下標變量j是否越界。當文件的初始狀態(tài)不同時，直接插入排序所耗費的時間是有很大差異的。最好情況是文件初態(tài)為正序，此時算法的時間復雜度為O(n)，最壞情況是文件初態(tài)為反序，相應的時間復雜度為O(n2)，算法的平均時間復雜度是O(n2)。算法的輔助空間復雜度是O(1)，是一個就地排序。3.1.4時間復雜度分析直接插入排序算法必須進行n-1趟。最好情況下，即初始序列有序，執(zhí)行n-1趟，但每一趟只比較一次，移動元素兩次，總的比較次數(shù)是(n-1)，移動元素次數(shù)是2(n-1)。因此最好情況下的時間復雜度就是O(n)。最壞情況(非遞增)下，最多比較i次，因此需要的比較次數(shù)是：所以，時間復雜度為O(n2)。 3.2、直接選擇排序函數(shù)3.2.1基本原理待排序的一組數(shù)據(jù)元素中，選出最小的一個數(shù)據(jù)元素與第一個位置的數(shù)據(jù)元素交換；然后在剩下的數(shù)據(jù)元素當中再找最小的與第二個位置的數(shù)據(jù)元素交換，循環(huán)到只剩下最后一個數(shù)據(jù)元素為止，依次類推直到所有記錄。第一趟從 n 個記錄中找出關鍵碼最小的記錄與第個記錄交換；第二趟，從第二個記錄開始的， 2 一 1 個記錄中再選出關鍵碼最小的記錄與第二個記錄交換；如此，第 i 趟，則從第 i 個記錄開始的 n 一 i + l 個記錄中選出關鍵碼最小的記錄一與第 i 個記錄交換，占到招個序列按關鍵碼有序。3.2.2排序過程【示例】：初始關鍵字 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 49 76 76 97第七趟排序后 13 27 38 49 49 76 76 97最后排序結果 13 27 38 49 49 76 76 973.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) printf("OverFollow!");getchar();exit(1); for(i=0;i<p->n;i+)/*復制數(shù)組*/ pvector->recordi=p->recordi;pvector->n=p->n;*compare=0;*exchange=0;for(i=0;i<pvector->n-1;i+) k=i; for(j=i+1;j<pvector->n;j+) (*compare)+; if(pvector->recordj.key<pvector->recordk.key) k=j; if(k!=i) temp=pvector->recordi; pvector->recordi=pvector->recordk; pvector->recordk=temp; ( *exchange)+=3; free(pvector);選擇排序法的第一層循環(huán)從起始元素開始選到倒數(shù)第二個元素,主要是在每次進入的第二層循環(huán)之前,將外層循環(huán)的下標賦值給臨時變量,接下來的第二層循環(huán)中,如果發(fā)現(xiàn)有比這個最小位置處的元素更小的元素,則將那個更小的元素的下標賦給臨時變量,最后,在二層循環(huán)退出后,如果臨時變量改變,則說明,有比當前外層循環(huán)位置更小的元素,需要將這兩個元素交換.3.2.4 時間復雜度分析該算法運行時間與元素的初始排列無關。不論初始排列如何，該算法都必須執(zhí)行n-1趟，每趟執(zhí)行n-i-1次關鍵字的比較，這樣總的比較次數(shù)為：所以，簡單選擇排序的最好、最壞和平均情況的時間復雜度都為O(n2)。3.3冒泡排序函數(shù)3.3.1基本原理在每一趟冒泡排序中，依次比較相鄰的兩個關鍵字大小，若為反序咋交換。經(jīng)過一趟起泡后，關鍵詞大的必須移到最后。按照這種方式進行第一趟在序列（I0In-1）中從前往后進行兩個相鄰元素的比較，若后者小，則交換，比較n-1次；第一趟排序結束，最大元素被交換到In-1中，下一趟只需在子序列（I0In-2）中進行；如果在某一趟排序中未交換元素，則不再進行下一趟排序。將被排序的記錄數(shù)組J1.n垂直排列，每個記錄Ji看作是重量為Ji.key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止，最后可完成。3.3.2排序過程將被排序的記錄數(shù)組R1.n垂直排列，每個記錄Ri看作是重量為Ri.key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。（1）初始    R1.n為無序區(qū)。（2）第一趟掃描    從無序區(qū)底部向上依次比較相鄰的兩個氣泡的重量，若發(fā)現(xiàn)輕者在下、重者在上，則交換二者的位置。即依次比較(Rn，Rn-1)，(Rn-1，Rn-2)，(R2，R1)；對于每對氣泡(Rj+1，Rj)，若Rj+1.key<Rj.key，則交換Rj+1和Rj的內(nèi)容。    第一趟掃描完畢時，"最輕"的氣泡就飄浮到該區(qū)間的頂部，即關鍵字最小的記錄被放在最高位置R1上。（3）第二趟掃描    掃描R2.n。掃描完畢時，"次輕"的氣泡飄浮到R2的位置上    最后，經(jīng)過n-1 趟掃描可得到有序區(qū)R1.n    第i趟掃描時，R1.i-1和Ri.n分別為當前的有序區(qū)和無序區(qū)。掃描仍是從無序區(qū)底部向上直至該區(qū)頂部。掃描完畢時，該區(qū)中最輕氣泡飄浮到頂部位置Ri上，結果是R1.i變?yōu)樾碌挠行騾^(qū)。49 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 := 1 To N-1 Do /做N-1趟排序/ begin NoSwap := True; /置未排序的標志/ For J := N - 1 DownTo 1 Do /從底部往上掃描/ begin If RJ+1< RJ Then /交換元素/ begin Temp := RJ+1; RJ+1 := RJ; RJ := Temp; NoSwap := False end; end; If NoSwap Then Return/本趟排序中未發(fā)生交換，則終止算法/ 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!"); getchar(); exit(1); for(i=0;i<p->n;i+)/* 復制數(shù)組*/ pvector->recordi=p->recordi; pvector->n=p->n; *compare=0; *exchange=0; for(i=0;i<pvector->n-1;i+) noswap=1; for(j=0;j<pvector->n-i-1;j+) (*compare)+; if(pvector->recordj+1.key<pvector->recordj.key) temp=pvector->recordj; pvector->recordj=pvector->recordj+1; pvector->recordj+1=temp; (*exchange)+=3; noswap=0; if(noswap) break; free(pvector);起泡排序的結束條件為：最后一趟沒有進行“交換”。從起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經(jīng)過一趟起泡，無序序列的長度只縮小1。 算法思想：將被排序的記錄數(shù)組R1.n垂直排列，每個記錄Ji看作是重量為Ji.key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組J：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止3.3.4 時間復雜度分析當原始數(shù)據(jù)正向有序時，冒泡排序出現(xiàn)最好情況。此時，只需進行一趟排序，作n-1次關鍵字比較，因此最好情況下的時間復雜度是O(n)。當原始數(shù)據(jù)反向有序時，冒泡排序出現(xiàn)最壞情況。此時，需進行n-1趟排序，第i趟需作(n-i)次關鍵字間的比較，并且需執(zhí)行(n-i)次元素交換，所以，比較次數(shù)為：因此,最壞情況下的時間復雜度為O(n2)。3.4 Shell排序函數(shù)3.4.1基本原理Shell排序又稱縮小增量排序,Shell排序法是以創(chuàng)建者Donald Shell的名字命名的.Shell排序法是對相鄰指定距離(稱為間隔)的元素進行比較,已知到使用當前間隔進行比較的元素都按順序排序為止.Shell把間隔縮小一半,然后繼續(xù)處理,當間隔最終變?yōu)?,并且不再出現(xiàn)變化時,Shell排序也就完成了其處理過程.先取一個整數(shù)d1<n,把全部記錄分成d1個組，所有距離為d1倍數(shù)的記錄放在一組中，先在各組內(nèi)排序；然后去d2<d1重復上訴分組和排序工作；直至所取的增量dt=1(dt<dt-l<<d2<d1)，即所有記錄放在同一組中進行直接插入，直到di=1，即所有記錄放在一組中為止3.4.2排序過程先取一個正整數(shù)d1<n，把所有序號相隔d1的數(shù)組元素放一組，組內(nèi)進行直接插入排序；然后取d2<d1，重復上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止 初始：d5 49 38 65 97 76 13 27 49* 55 04 49 13 |-| 38 27 |-| 65 49* |-| 97 55 |-| 76 04 |-| 一趟結果 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 04 65 |-|-| 49* 49 97 |-|-| 二趟結果 13 04 49* 38 27 49 55 65 97 76 d=1 13 04 49* 38 27 49 55 65 97 76 |-|-|-|-|-|-|-|-|-| 三趟結果 04 13 27 38 49* 49 55 65 76 973.4.3 Shell排序算法void ShellSort(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;i<p->n;i+)/* 復制數(shù)組*/ pvector->recordi=p->recordi; pvector->n=p->n; *compare=0; *exchange=0; for(increment=d;increment>0;increment/=2) for(i=increment;i<pvector->n;i+) temp=pvector->recordi; (*exchange)+; j=i-increment; while(j>=0&&temp.key<pvector->recordj.key) (*compare)+; pvector->recordj+increment=pvector->recordj; (*exchange)+;j-=increment; pvector->recordj+increment=temp; (*exchange)+; free(pvector);當增量d=1時，ShellPass和InsertSort基本一致，只是由于沒有哨兵而在內(nèi)循環(huán)中增加了一個循環(huán)判定條件"j>0"，以防下標越界。3.4.4時間復雜度分析希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。所以，希爾排序的時間復雜度會比o(n2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。所以希爾排序是不穩(wěn)定的，其時間復雜度為O(n 2)。3.5堆排序函數(shù)3.5.1基本原理堆排序思想很簡單，就是每次把關鍵詞調(diào)整為堆，取出堆頂元素與堆中最后一個元素交換，同時令堆得大小減一，把剩余的一些元素重新調(diào)整為堆，重復此過程，直到堆中只剩一個元素，n 個關鍵字序列 kl , k2 ， ， kn稱為堆，當且僅當該序列滿足如下性質（簡稱為堆性質） : ( l ) ki<= k2i 且 ki<=k2i+1或（ 2 ）ki>= k2i 且 ki>=k2i+1。若將此序列所存儲的向量 R 1n 看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于（或不小于）其左右孩子（若存在）結點的關鍵字。根結點（亦稱為堆頂）的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。根結點（亦稱為堆頂）的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。注意： 堆中任一子樹亦是堆。 以上討論的堆實際上是人叉堆，類似地可定義 k 叉堆。3.5.2排序過程堆排序是一樹形選擇排序。堆排序的特點是：在排序過程中，將 R 1 n 看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之問的內(nèi)在關系，在當前無序區(qū)中選抒關鍵字最大（或最小）的記錄。下面將從實際數(shù)據(jù)中演示其排序中的各個操作。原始數(shù)組： 22 53 72 1 1 34 44 11 15 28 3 10 65 第一步，從樹頂?shù)綐淙~把數(shù)填充進入，建立堆。紅色為卜一次交換的兩個數(shù)日宇列）。使記錄遞增有序，進一步排序。第一次交換：第二次交換：第三次交換：第四次交換：第五次交換：第六次交換：第七次交換：第八次交換：第九次交換：全程交換完成，得到最小值為 3 并且輸出它。從序列中刪除 3 ，重新建立堆。以次循環(huán)，直到全部輸出完成為止。3.5.3堆排序算法void HeapSort(SortObject *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;i<p->n;i+)/* 復制數(shù)組*/ pvector->recordi=p->recordi;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);/*首先構造第一個堆*/for(i=n-1;i>0;i-) temp=pvector->record0; pvector->record0=pvector->recordi; pvector->recordi=temp; (*exchange)+=3; SiftHeap(pvector,i,0,compare,exchange);/*重建新堆*/free(pvector);當增量d=1時，ShellPass和InsertSort基本一致，只是由于沒有哨兵而在內(nèi)循環(huán)中增加了一個循環(huán)判定條件"j>0"，以防下標越界。3.5.4時間復雜度分析堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調(diào)用Heapify實現(xiàn)的。堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是不穩(wěn)定的，算法時間復雜度O(nlog n)。3.6快速排序函數(shù)3.6.1基本原理首先我們選擇一個中間值 middle （程序中我們可使用數(shù)組中間值），把比中問值小的放在其左邊，比中問值大的放在其右邊。由于這個排序算法較復雜，我們先給出其進行一次排序的程序框架。在待排序的個記錄中任意取一個記錄（通常取第一個記錄）為區(qū)分標準，把所有小于該排序的記錄移到左邊，把所有大于該排序碼的記錄移到右邊，中級放所選記錄，為一趟快速排序。然后對前后兩個子序列分別重新上述過程，直到所有記錄都排好序。對任意給定的序列中某個元素，經(jīng)過一趟排序后，將原序列分割成兩個子序列(Rp(0),Rp(1),Rp(s-1)和(Rp(s+1),Rp(s+2),Rp(n-1)，其中前一個子序列中的所有元素的關鍵詞均小于或等于該元素的關鍵詞值Kp(s)，后一個子序列中元素的關鍵詞均大于或等于Kp(s)。稱該元素Rp(s)為分割元素，子序列(Rp(0),Rp(1),Rp(s-1)為其低端序列，(Rp(0),Rp(1),Rp(s-1)為其高端序列。很明顯，以后只需對低端和高端序列分別進行快速排序，直到子序列為空或只有一個元素時結束，最后得到有序序列。總之，每趟使表的第一個元素放在適當位置，將表兩分，再對兩子表進行同樣的遞歸劃分，直至劃分的子表長度為1！3.6.2排序過程假設要排序的數(shù)組是A1AN，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是： 1）、設置兩個變量I、J，排序開始的時候I：=1，J：=N； 2）以第一個數(shù)組元素作為關鍵數(shù)據(jù)，賦值給X，即X：=A1； 3）、從J開始向前搜索，即由后開始向前搜索（J：=J-1），找到第一個小于X的值，兩者交換； 4）、從I開始向后搜索，即由前開始向后搜索（I：=I+1），找到第一個大于X的值，兩者交換； 5）、重復第3、4步，直到I=J； 例如：待排序的數(shù)組A的值分別是：（初始關鍵數(shù)據(jù)X：=49） A1 A2 A3 A4 A5 A6 A7： 49 38 65 97 76 13 27進行第一次交換后： 27 38 65 97 76 13 49 ( 按照算法的第三步從后面開始找進行第二次交換后： 27 38 49 97 76 13 65 ( 按照算法的第四步從前面開始找>X的值，65>49,兩者交換，此時I：=3 )進行第三次交換后： 27 38 13 97 76 49 65( 按照算法的第五步將又一次執(zhí)行算法的第三步從后開始找進行第四次交換后： 27 38 13 49 76 97 65( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時J：=4 ) 此時再執(zhí)行第三不的時候就發(fā)現(xiàn)I=J，從而結束一躺快速排序，那么經(jīng)過一躺快速排序之后的結果是：27 38 13 49 76 97 65，即所以大于49的數(shù)全部在49的后面，所以小于49的數(shù)全部在49的前面。 快速排序就是遞歸調(diào)用此過程在以49為中點分割這個數(shù)據(jù)序列，分別對前面一部分和后面一部分進行類似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個有序的序列，根據(jù)這種思想對于上述數(shù)組A的快速排序的全過程如圖6所示：初始狀態(tài) 49 38 65 97 76 13 27 進行一次快速排序之后劃分為 27 38 13 49 76 97 65分別對前后兩部分進行快速排序 13 27 38 結束 結束 49 65 76 97 49 65 結束 結束1）、設有N（假設N=10）個數(shù)，存放在S數(shù)組中；2）、在S1。N中任取一個元素作為比較基準，例如取T=S1，起目的就是在定出T應在排序結果中的位置K，這個K的位置在：S1。K-1<=SK<=SK+1.N，即在SK以前的數(shù)都小于SK，在SK以后的數(shù)都大于SK；3）、利用分治思想（即大化小的策略）可進一步對S1。K-1和SK+1。N兩組數(shù)據(jù)再進行快速排序直到分組對象只有一個數(shù)據(jù)為止。如具體數(shù)據(jù)如下，那么第一躺快速排序的過程是：數(shù)組下標： 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 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 45 48 93 72 53通過一躺排序將45放到應該放的位置K，這里K=6，那么再對S1。5和S6。10分別進行快速排序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->recordi; (*exchange)+; while(i!=j) while(pvector->recordj.key>=temp.key)&&(j>i) (*compare)+; j-;