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

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

1、各種排序算法性能比較畢業(yè)論文 各種排序算法性能比較 系 電子信息工程系 專業(yè) 電子信息工程技術(shù) 姓名 于廣振 班級(jí) 電信083（系統(tǒng)） 學(xué)號(hào)0801133115指導(dǎo)教師 鄭雪芳 職稱 講師 設(shè)計(jì)時(shí)間 2010.11.222011.1.8 目錄摘要：3第一章、引言41.1、排序算法的背景41.2、排序算法研究現(xiàn)狀51.3、排序算法的意義51.4、排序算法設(shè)計(jì)目標(biāo)6第二章、排序算法概要設(shè)計(jì)72.1、原始數(shù)據(jù)72.2、輸出數(shù)據(jù)72.3、數(shù)據(jù)處理72.4、排序算法數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)82 .5排序算法的性能評(píng)價(jià)82.6、系統(tǒng)的模塊劃分及模塊功能92.6.1、主程序模塊92.6.2可排序表單元模塊92.7、模塊

2、的測(cè)試數(shù)據(jù)10第三章、排序基本算法113.1、直接插入排序函數(shù)113.1.1基本原理113.1.2排序過(guò)程113.1.3直接插入排序算法113.1.4時(shí)間復(fù)雜度分析133.2、直接選擇排序函數(shù)133.2.1基本原理133.2.2排序過(guò)程143.2.3直接選擇排序算法143.2.4 時(shí)間復(fù)雜度分析153.3冒泡排序函數(shù)163.3.1基本原理163.3.2排序過(guò)程163.3.3冒泡排序算法183.3.4 時(shí)間復(fù)雜度分析193.4 Shell排序函數(shù)193.4.1基本原理193.4.2排序過(guò)程203.4.3 Shell排序算法213.4.4時(shí)間復(fù)雜度分析223.5堆排序函數(shù)233.5.1基本原理23

3、3.5.2排序過(guò)程233.5.3堆排序算法273.6快速排序函數(shù)283.6.1基本原理283.6.2排序過(guò)程293.6.3快速排序算法313.6.4快速排序時(shí)間復(fù)雜度分析333.7排序主調(diào)用函數(shù)333.7.1基本原理333.7.2排序主調(diào)用算法343.7.3排序主調(diào)用時(shí)間復(fù)雜度分析35第四章、運(yùn)行與測(cè)試36第五章、結(jié)論38致謝39參考文獻(xiàn)40 摘要：在這兩年的專業(yè)基礎(chǔ)課的學(xué)習(xí)過(guò)程中，我們學(xué)習(xí)了程序設(shè)計(jì)基礎(chǔ)，面向?qū)ο蟪绦蛟O(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)使用C+語(yǔ)言描述等課程。使得我們可以綜合運(yùn)用所學(xué)知識(shí)，更進(jìn)一步的理解各個(gè)課程之間的聯(lián)系。不僅鞏固了以前所學(xué)過(guò)的知識(shí)，而且學(xué)到了很多在書(shū)本上所沒(méi)有學(xué)到過(guò)的知識(shí)。在這個(gè)

4、過(guò)程中我遇到了各種各樣的問(wèn)題，同時(shí)在設(shè)計(jì)的過(guò)程中發(fā)現(xiàn)了自己的不足之處，對(duì)一些知識(shí)理解得不夠深刻。我這次的題目是各種排序性能的比較，這就要求我首先必須掌握各種排序的原理，并且還要把各個(gè)排序結(jié)合起來(lái)綜合考慮。我在實(shí)現(xiàn)排序功能是沒(méi)有遇到太大的問(wèn)題，但在進(jìn)行移動(dòng)次數(shù)，比較次數(shù)和交換次數(shù)的統(tǒng)計(jì)中始終無(wú)法得出正確的結(jié)果，最終在指導(dǎo)老師的幫助下才完成。在程序?qū)懞煤螅x擇用來(lái)測(cè)試的數(shù)據(jù)也很重要，否則體現(xiàn)不出一些問(wèn)題。在這個(gè)程序中，如果排序的數(shù)據(jù)太少，則無(wú)法體現(xiàn)時(shí)間排名。通過(guò)這次課程設(shè)計(jì)，使我對(duì)數(shù)據(jù)結(jié)構(gòu)有了更進(jìn)一步的認(rèn)識(shí)和了解，要通過(guò)不斷的上機(jī)操作才能更好地學(xué)習(xí)它，我也發(fā)現(xiàn)我的許多不足之處，對(duì)C+語(yǔ)言的一些庫(kù)函

5、數(shù)不太了解，不能熟練掌握各種常用函數(shù)的功能，對(duì)函數(shù)調(diào)用的正確使用不夠熟悉，對(duì)C+中經(jīng)常出現(xiàn)的錯(cuò)誤也不熟悉。通過(guò)這次課程設(shè)計(jì)，我更加體會(huì)到了實(shí)踐的重要性。！排序算法是數(shù)據(jù)結(jié)構(gòu)這門課程核心內(nèi)容之 。它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫(kù)、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)排序算法是為了將實(shí)際問(wèn)題中）聽(tīng)涉及的對(duì)象在計(jì)算機(jī)中對(duì)它們進(jìn)行處理。木文首先介紹排序的一些基木概念和一些常用的排序方法，然后利用 VC + 開(kāi)發(fā) 個(gè)數(shù)據(jù)結(jié)構(gòu)的演示系統(tǒng)；該演示系統(tǒng)可以通過(guò)操作把數(shù)據(jù)結(jié)構(gòu)中的主要排序常見(jiàn)的排序算法（有冒泡排序、選擇排序、直接插入排序、希爾排序、快速排序、堆排序等）

6、表示出來(lái)。該項(xiàng)目在收集各種排序方法的基礎(chǔ)上，對(duì)其特點(diǎn)、效率、適用性等在不同的數(shù)據(jù)集上做全面的分析和比較，并以動(dòng)態(tài)演示的方式展示一些經(jīng)典排序算法運(yùn)行程。所使用的編程環(huán)境為TURBOC2。通過(guò)實(shí)驗(yàn)可知，一般情況下,記錄規(guī)模較小時(shí)，直接插入排序較好；當(dāng)記錄規(guī)模較大且無(wú)序時(shí)，快速排序較好。關(guān)鍵字：直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序；第一章、引言1.1、排序算法的背景21世紀(jì)是“信息”主導(dǎo)的世紀(jì)，是崇尚“創(chuàng)新與個(gè)性”發(fā)展的時(shí)代，體現(xiàn)“以人為本”、構(gòu)建“和諧社會(huì)”是社會(huì)發(fā)展的主流。然而隨著全球經(jīng)濟(jì)一體化進(jìn)程的不斷推進(jìn)，市場(chǎng)與人才的競(jìng)爭(zhēng)日趨激烈。對(duì)于國(guó)家倡導(dǎo)發(fā)展的IT產(chǎn)業(yè)

7、，需要培養(yǎng)大量的、適應(yīng)經(jīng)濟(jì)和科技發(fā)展的計(jì)算機(jī)人才。眾所周知，近年來(lái)，一些用人單位對(duì)部分大學(xué)畢業(yè)生到了工作崗位后，需要12年甚至多年的訓(xùn)練才能勝任工作的“半成品”現(xiàn)象反映強(qiáng)烈。從中反映出單位對(duì)人才的需求越來(lái)越講究實(shí)用，社會(huì)要求學(xué)校培養(yǎng)學(xué)生的標(biāo)準(zhǔn)應(yīng)該和社會(huì)實(shí)際需求的標(biāo)準(zhǔn)相統(tǒng)一。對(duì)于IT業(yè)界來(lái)講，一方面需要一定的科研創(chuàng)新型人才，從事高端的技術(shù)研究，占領(lǐng)技術(shù)發(fā)展的高地；另一方面，更需要計(jì)算機(jī)工程應(yīng)用、技術(shù)應(yīng)用及各類服務(wù)實(shí)施人才，這些人才可統(tǒng)稱“應(yīng)用型”人才。應(yīng)用型專科教育，簡(jiǎn)單地講就是培養(yǎng)高層次應(yīng)用型人才的本科教育。其培養(yǎng)目標(biāo)應(yīng)是面向社會(huì)的高新技術(shù)產(chǎn)業(yè)，培養(yǎng)在工業(yè)、工程領(lǐng)域的生產(chǎn)、建設(shè)、管理、服務(wù)等第

8、一線崗位，直接從事解決實(shí)際問(wèn)題、維持工作正常運(yùn)行的高等技術(shù)應(yīng)用型人才。這種人才，一方面掌握某一技術(shù)學(xué)科的基本知識(shí)和基本技能，另一方面又具有較強(qiáng)的解決實(shí)際問(wèn)題的基本能力，他們常常是復(fù)合性、綜合性人才，受過(guò)較為完整的、系統(tǒng)的、有行業(yè)應(yīng)用背景的“職業(yè)” 項(xiàng)目訓(xùn)練，其最大的特色就是有較強(qiáng)的專業(yè)理論基礎(chǔ)支撐，能快速地適應(yīng)職業(yè)崗位并發(fā)揮作用。因此，可以說(shuō)“應(yīng)用型人才培養(yǎng)既有本科人才培養(yǎng)的一般要求，又有強(qiáng)化崗位能力的內(nèi)涵，它是在本科基礎(chǔ)之上的以工程師層次培養(yǎng)為主的人才培養(yǎng)體系”，人才培養(yǎng)模式必須吸取一般本科教育和職業(yè)教育的長(zhǎng)處，兼蓄并顧?！坝?jì)算機(jī)科學(xué)與技術(shù)”專業(yè)教學(xué)指導(dǎo)委員會(huì)已經(jīng)在研究并指導(dǎo)實(shí)施計(jì)算機(jī)人才的

9、“分類”培養(yǎng)，這需要我們轉(zhuǎn)變傳統(tǒng)的教育模式和教學(xué)方法，明確人才培養(yǎng)目標(biāo)，構(gòu)建課程體系，在保證“基礎(chǔ)的前提”下，重視素質(zhì)的養(yǎng)成，突出“工程性”、“技術(shù)應(yīng)用性”、“適應(yīng)性”概念，突出知識(shí)的應(yīng)用能力、專業(yè)技術(shù)應(yīng)用能力、工程實(shí)踐能力、組織協(xié)調(diào)能力、創(chuàng)新能力和創(chuàng)業(yè)精神，較好地體現(xiàn)與實(shí)施人才培養(yǎng)過(guò)程的“傳授知識(shí)，訓(xùn)練能力，培養(yǎng)素質(zhì)”三者的有機(jī)統(tǒng)一。排序算法是在整個(gè)計(jì)算機(jī)科學(xué)一與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語(yǔ)。排序算法是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫(kù)、操作系統(tǒng)、編譯原理及人一 I 智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)?。怀痰雀鞣N領(lǐng)域。本人在研究各種算法的過(guò)程中，對(duì)其特點(diǎn)、效率、適用性等在不同的數(shù)據(jù)集卜做全面的分析

10、和比較，并以動(dòng)態(tài)演示的方式展示一些經(jīng)典排序算法運(yùn)行過(guò)程，目的有以下五個(gè)方面：做算法的對(duì)比研究，培養(yǎng)研究能力；開(kāi)發(fā)一個(gè)獨(dú)立的軟件，培養(yǎng)程序設(shè)計(jì)和軟件開(kāi)發(fā)能力；初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力；為教學(xué)服務(wù)，研究結(jié)果 nJ 對(duì)抽象的 算法與數(shù)據(jù)結(jié)構(gòu) 的教學(xué)有一定的輔助作用。排序是計(jì)算機(jī)科學(xué)中最重要的研究問(wèn)題之一, 它在計(jì)算機(jī)圖形、計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人、模式識(shí)別及統(tǒng)計(jì)學(xué)等領(lǐng)域具有廣泛的應(yīng)用。由于它固有的理論上的重要性,2000年它被列為對(duì)科學(xué)和工程計(jì)算的研究與實(shí)踐影響最大的10大問(wèn)題之一。其功能是將一個(gè)

11、數(shù)據(jù)元素的任意序列重新排列成一個(gè)按關(guān)鍵字有序的序列。1.2、排序算法研究現(xiàn)狀隨著計(jì)一算湘 L 技術(shù)的口益發(fā)展，其應(yīng)用旱已不局限于簡(jiǎn)單的數(shù)值運(yùn)算。而涉及到問(wèn)題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì)以及插入、刪除、排序、查找等復(fù)雜的非數(shù)值處理和操作。排序算法的學(xué)習(xí)就是為以后利川計(jì)算機(jī)資源高效地開(kāi)發(fā)非數(shù)值處理的計(jì)算機(jī)程序打下堅(jiān)實(shí)的理論、方法和技術(shù)基礎(chǔ)。近來(lái)國(guó)內(nèi)外專家學(xué)者們對(duì)排序算法又有了新的研究和發(fā)現(xiàn)。例如：我國(guó)山東大學(xué)的張峰和張金屯兩位教授共同研究了 我國(guó)植被數(shù)量分類和排序研究進(jìn)展 這課題。很值得有關(guān)部門去學(xué)習(xí)和研究。1.3、排序算法的意義排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作。它的功能是將一個(gè)數(shù)據(jù)元素的任意序

12、列，重新排列成一個(gè)按關(guān)鍵字有序的序列。排序的方法很多，但是就其全面性能而言，很難提出一種被認(rèn)為是最好的方法，每一種方法都有各自的優(yōu)缺點(diǎn)，適合在不同的環(huán)境下使用。如果按排序過(guò)程中依據(jù)的不同原則對(duì)內(nèi)部排序方法進(jìn)行分類，則大致可分為直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序等六類。此實(shí)驗(yàn)通過(guò)對(duì)直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序這幾種內(nèi)部排序算法進(jìn)行比較，能使我們更好的掌握這些排序的基本思想及排序算法。通過(guò)該題目的設(shè)計(jì)過(guò)程，可以加深理解各種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)上運(yùn)算的實(shí)現(xiàn)，進(jìn)一步理解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，學(xué)會(huì)如

13、何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題，培養(yǎng)我們的動(dòng)手能力1.4、排序算法設(shè)計(jì)目標(biāo)本課程設(shè)計(jì)對(duì)以下排序算法進(jìn)行比較：直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序待排序表的元素關(guān)鍵字為整數(shù)，用不同的測(cè)試數(shù)據(jù)做測(cè)試比較。比較的指標(biāo)為關(guān)鍵字的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)。最后用圖、表格數(shù)據(jù)匯總數(shù)據(jù)，以便對(duì)這些內(nèi)部排序算法進(jìn)行性能分析。本課程設(shè)計(jì)首先介紹排序的一些基本概念和一些常用的排序方法，然后利用 VC 十開(kāi)發(fā)一個(gè)數(shù)據(jù)結(jié)構(gòu)的演示系統(tǒng)；該演示系統(tǒng)可以通過(guò)操作把數(shù)據(jù)結(jié)構(gòu)中的主要排序常見(jiàn)的排序算法（直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序）表示出來(lái)。該項(xiàng)目在

14、收集齊種排序方法的基礎(chǔ)上，對(duì)其特點(diǎn)、效率、適用性等在不同的數(shù)據(jù)集上做全面的分析和比較，并以動(dòng)態(tài)演示的方式展示一些經(jīng)典排序算法運(yùn)行程。第二章、排序算法概要設(shè)計(jì)2.1、原始數(shù)據(jù)用戶輸入記錄的個(gè)數(shù)，數(shù)據(jù)由隨機(jī)數(shù)產(chǎn)生器生成。2.2、輸出數(shù)據(jù)產(chǎn)生的隨機(jī)數(shù)分別用直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序這些排序方法進(jìn)行排序，輸出關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)。2.3、數(shù)據(jù)處理主程序產(chǎn)生1組隨機(jī)數(shù)起泡排序Shell排序快速排序直接選擇排序堆排序記錄關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)將隨機(jī)數(shù)保存在數(shù)組中循環(huán)20次輸出關(guān)鍵字的比較次數(shù)、移動(dòng)次數(shù)的平均值直接選擇排序 2.4、排序算法數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)本

15、程序中，考慮的內(nèi)容就是待排序?qū)ο?，排序的依?jù)是關(guān)鍵字之間的大小比較，故在每個(gè)節(jié)點(diǎn)的類型定義中，至少得包含關(guān)鍵字key一項(xiàng)。不失一般性，這里就使用關(guān)鍵詞這一項(xiàng)，其他都省略，具體應(yīng)用加上其他數(shù)據(jù)項(xiàng)即可。被排序?qū)ο笫怯梢粋€(gè)個(gè)節(jié)點(diǎn)夠成，一個(gè)排序?qū)ο竽匕幌盗兄赶蛞淮?jié)點(diǎn)的指針，排序?qū)ο蟮拈L(zhǎng)度。本程序功能簡(jiǎn)單。typedef structint key; /*關(guān)鍵字*/RecordNode; /*排序節(jié)點(diǎn)的類型*/typedef structRecordNode *record;int n; /*排序?qū)ο蟮拇笮?/SortObject; /*排序節(jié)點(diǎn)的類型*/2 .5排序算法的性能評(píng)價(jià) ( 1 ）執(zhí)行

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

17、.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

18、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.快速排序

19、*/G排序主調(diào)用函數(shù)void SortMethod(void)2.7、模塊的測(cè)試數(shù)據(jù)以關(guān)鍵字的數(shù)目分別為20，100，500為例,作為測(cè)試數(shù)據(jù)第三章、排序基本算法3.1、直接插入排序函數(shù)3.1.1基本原理假設(shè)待排序的n個(gè)記錄R0,R1,Rn順序存放在數(shù)組中，直接插入法在插入記錄Ri（i=1,2,n-1）時(shí)，記錄的集合被劃分為兩個(gè)區(qū)間R0,Ri-1和Ri+1,Rn-1,其中，前一個(gè)子區(qū)間已經(jīng)排好序，后一個(gè)子區(qū)間是當(dāng)前未排序的部分，將關(guān)鍵碼Ki與Ki-1Ki-2，K0依次比較，找出應(yīng)該插入的位置，將記錄Ri插，然后將剩下的i-1個(gè)元素按關(guān)鍵詞大小依次插入該有序序列，沒(méi)插入一個(gè)元素后依然保持該序列有

20、序，經(jīng)過(guò)i-1趟排序后即成為有序序列。每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。3.1.2排序過(guò)程關(guān)鍵字： 10 3 25 20 8 第一趟： 3 10 25 20 8 （將前兩個(gè)數(shù)據(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ù)奈恢茫?.1.3直接插入排序算法void InsertSort(SortObject *p,unsigned long *compare,unsigne

21、d long *exchange)int i,j;RecordNode temp; SortObject *pvector;if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL)printf(OverFollow!);getchar();exit(1);for(i=0;in;i+)/* 復(fù)制數(shù)組*/pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;for(i=1;in;i+) temp=pvector-recordi; (*exchange)+; j=i-1;

22、while(temp.keyrecordj.key)&(j=0) (*compare)+; (*exchange)+; pvector-recordj+1=pvector-recordj; j-; if(j!=(i-1) pvector-recordj+1=temp; (*exchange)+; free(pvector);哨兵（監(jiān)視哨）有兩個(gè)作用：一是作為臨變量存放Ri（當(dāng)前要進(jìn)行比較的關(guān)鍵字）的副本；二是在查找循環(huán)中用來(lái)監(jiān)視下標(biāo)變量j是否越界。當(dāng)文件的初始狀態(tài)不同時(shí)，直接插入排序所耗費(fèi)的時(shí)間是有很大差異的。最好情況是文件初態(tài)為正序，此時(shí)算法的時(shí)間復(fù)雜度為O(n)，最壞情況是文件初態(tài)為反序，

23、相應(yīng)的時(shí)間復(fù)雜度為O(n2)，算法的平均時(shí)間復(fù)雜度是O(n2)。算法的輔助空間復(fù)雜度是O(1)，是一個(gè)就地排序。3.1.4時(shí)間復(fù)雜度分析直接插入排序算法必須進(jìn)行n-1趟。最好情況下，即初始序列有序，執(zhí)行n-1趟，但每一趟只比較一次，移動(dòng)元素兩次，總的比較次數(shù)是(n-1)，移動(dòng)元素次數(shù)是2(n-1)。因此最好情況下的時(shí)間復(fù)雜度就是O(n)。最壞情況(非遞增)下，最多比較i次，因此需要的比較次數(shù)是：所以，時(shí)間復(fù)雜度為O(n2)。 3.2、直接選擇排序函數(shù)3.2.1基本原理待排序的一組數(shù)據(jù)元素中，選出最小的一個(gè)數(shù)據(jù)元素與第一個(gè)位置的數(shù)據(jù)元素交換；然后在剩下的數(shù)據(jù)元素當(dāng)中再找最小的與第二個(gè)位置的數(shù)據(jù)元

24、素交換，循環(huán)到只剩下最后一個(gè)數(shù)據(jù)元素為止，依次類推直到所有記錄。第一趟從 n 個(gè)記錄中找出關(guān)鍵碼最小的記錄與第個(gè)記錄交換；第二趟，從第二個(gè)記錄開(kāi)始的， 2 一 1 個(gè)記錄中再選出關(guān)鍵碼最小的記錄與第二個(gè)記錄交換；如此，第 i 趟，則從第 i 個(gè)記錄開(kāi)始的 n 一 i + l 個(gè)記錄中選出關(guān)鍵碼最小的記錄一與第 i 個(gè)記錄交換，占到招個(gè)序列按關(guān)鍵碼有序。3.2.2排序過(guò)程【示例】：初始關(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 7

25、6 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最后排序結(jié)果 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

26、(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL) printf(OverFollow!);getchar();exit(1); for(i=0;in;i+)/*復(fù)制數(shù)組*/ pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) (*compare)+; if(pvector-recordj.keyrecordk.key) k=j; if(k!=i) temp=pvector-record

27、i; pvector-recordi=pvector-recordk; pvector-recordk=temp; ( *exchange)+=3; free(pvector);選擇排序法的第一層循環(huán)從起始元素開(kāi)始選到倒數(shù)第二個(gè)元素,主要是在每次進(jìn)入的第二層循環(huán)之前,將外層循環(huán)的下標(biāo)賦值給臨時(shí)變量,接下來(lái)的第二層循環(huán)中,如果發(fā)現(xiàn)有比這個(gè)最小位置處的元素更小的元素,則將那個(gè)更小的元素的下標(biāo)賦給臨時(shí)變量,最后,在二層循環(huán)退出后,如果臨時(shí)變量改變,則說(shuō)明,有比當(dāng)前外層循環(huán)位置更小的元素,需要將這兩個(gè)元素交換.3.2.4 時(shí)間復(fù)雜度分析該算法運(yùn)行時(shí)間與元素的初始排列無(wú)關(guān)。不論初始排列如何，該算法都必須

28、執(zhí)行n-1趟，每趟執(zhí)行n-i-1次關(guān)鍵字的比較，這樣總的比較次數(shù)為：所以，簡(jiǎn)單選擇排序的最好、最壞和平均情況的時(shí)間復(fù)雜度都為O(n2)。3.3冒泡排序函數(shù)3.3.1基本原理在每一趟冒泡排序中，依次比較相鄰的兩個(gè)關(guān)鍵字大小，若為反序咋交換。經(jīng)過(guò)一趟起泡后，關(guān)鍵詞大的必須移到最后。按照這種方式進(jìn)行第一趟在序列（I0In-1）中從前往后進(jìn)行兩個(gè)相鄰元素的比較，若后者小，則交換，比較n-1次；第一趟排序結(jié)束，最大元素被交換到In-1中，下一趟只需在子序列（I0In-2）中進(jìn)行；如果在某一趟排序中未交換元素，則不再進(jìn)行下一趟排序。將被排序的記錄數(shù)組J1.n垂直排列，每個(gè)記錄Ji看作是重量為Ji.key的

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

30、)，(Rn-1，Rn-2)，(R2，R1)；對(duì)于每對(duì)氣泡(Rj+1，Rj)，若Rj+1.keyRj.key，則交換Rj+1和Rj的內(nèi)容。 第一趟掃描完畢時(shí)，最輕的氣泡就飄浮到該區(qū)間的頂部，即關(guān)鍵字最小的記錄被放在最高位置R1上。（3）第二趟掃描 掃描R2.n。掃描完畢時(shí)，次輕的氣泡飄浮到R2的位置上 最后，經(jīng)過(guò)n-1趟掃描可得到有序區(qū)R1.n 第i趟掃描時(shí)，R1.i-1和Ri.n分別為當(dāng)前的有序區(qū)和無(wú)序區(qū)。掃描仍是從無(wú)序區(qū)底部向上直至該區(qū)頂部。掃描完畢時(shí)，該區(qū)中最輕氣泡飄浮到頂部位置Ri上，結(jié)果是R1.i變?yōu)樾碌挠行騾^(qū)。49 13 13 13 13 13 13 13 38 49 27 27 2

31、7 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; /置未排序的標(biāo)志/ For J := N - 1 DownTo 1

32、 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; Sort

33、Object *pvector; if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL) printf(OverFollow!); getchar(); exit(1); for(i=0;in;i+)/* 復(fù)制數(shù)組*/ pvector-recordi=p-recordi; 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(pvector-recordj+1.keyrecordj.key

34、) temp=pvector-recordj; pvector-recordj=pvector-recordj+1; pvector-recordj+1=temp; (*exchange)+=3; noswap=0; if(noswap) break; free(pvector);起泡排序的結(jié)束條件為：最后一趟沒(méi)有進(jìn)行“交換”。從起泡排序的過(guò)程可見(jiàn)，起泡排序是一個(gè)增加有序序列長(zhǎng)度的過(guò)程，也是一個(gè)縮小無(wú)序序列長(zhǎng)度的過(guò)程，每經(jīng)過(guò)一趟起泡，無(wú)序序列的長(zhǎng)度只縮小1。 算法思想：將被排序的記錄數(shù)組R1.n垂直排列，每個(gè)記錄Ji看作是重量為Ji.key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描

35、數(shù)組J：凡掃描到違反本原則的輕氣泡，就使其向上飄浮。如此反復(fù)進(jìn)行，直到最后任何兩個(gè)氣泡都是輕者在上，重者在下為止3.3.4 時(shí)間復(fù)雜度分析當(dāng)原始數(shù)據(jù)正向有序時(shí)，冒泡排序出現(xiàn)最好情況。此時(shí)，只需進(jìn)行一趟排序，作n-1次關(guān)鍵字比較，因此最好情況下的時(shí)間復(fù)雜度是O(n)。當(dāng)原始數(shù)據(jù)反向有序時(shí)，冒泡排序出現(xiàn)最壞情況。此時(shí)，需進(jìn)行n-1趟排序，第i趟需作(n-i)次關(guān)鍵字間的比較，并且需執(zhí)行(n-i)次元素交換，所以，比較次數(shù)為：因此,最壞情況下的時(shí)間復(fù)雜度為O(n2)。3.4 Shell排序函數(shù)3.4.1基本原理Shell排序又稱縮小增量排序,Shell排序法是以創(chuàng)建者Donald Shell的名字命

36、名的.Shell排序法是對(duì)相鄰指定距離(稱為間隔)的元素進(jìn)行比較,已知到使用當(dāng)前間隔進(jìn)行比較的元素都按順序排序?yàn)橹?Shell把間隔縮小一半,然后繼續(xù)處理,當(dāng)間隔最終變?yōu)?,并且不再出現(xiàn)變化時(shí),Shell排序也就完成了其處理過(guò)程.先取一個(gè)整數(shù)d1n,把全部記錄分成d1個(gè)組，所有距離為d1倍數(shù)的記錄放在一組中，先在各組內(nèi)排序；然后去d2d1重復(fù)上訴分組和排序工作；直至所取的增量dt=1(dtdt-ld2d1)，即所有記錄放在同一組中進(jìn)行直接插入，直到di=1，即所有記錄放在一組中為止3.4.2排序過(guò)程先取一個(gè)正整數(shù)d1n，把所有序號(hào)相隔d1的數(shù)組元素放一組，組內(nèi)進(jìn)行直接插入排序；然后取d2d1，

37、重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹?初始：d5 49 38 65 97 76 13 27 49* 55 04 49 13 |-| 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 04 65 |-|-| 49* 49 97 |-|-| 二趟結(jié)果 13 04 49* 38 27 49 55 65 97 76 d=1 13 04 49* 38 27

38、 49 55 65 97 76 |-|-|-|-|-|-|-|-|-| 三趟結(jié)果 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!

39、); getchar(); exit(1); for(i=0;in;i+)/* 復(fù)制數(shù)組*/ pvector-recordi=p-recordi; pvector-n=p-n; *compare=0; *exchange=0; for(increment=d;increment0;increment/=2) for(i=increment;in;i+) temp=pvector-recordi; (*exchange)+; j=i-increment; while(j=0&temp.keyrecordj.key) (*compare)+; pvector-recordj+increment=p

40、vector-recordj; (*exchange)+;j-=increment; pvector-recordj+increment=temp; (*exchange)+; free(pvector);當(dāng)增量d=1時(shí)，ShellPass和InsertSort基本一致，只是由于沒(méi)有哨兵而在內(nèi)循環(huán)中增加了一個(gè)循環(huán)判定條件j0，以防下標(biāo)越界。3.4.4時(shí)間復(fù)雜度分析希爾排序是按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序，當(dāng)剛開(kāi)始元素很無(wú)序的時(shí)候，步長(zhǎng)最大，所以插入排序的元素個(gè)數(shù)很少，速度很快；當(dāng)元素基本有序了，步長(zhǎng)很小，插入排序?qū)τ谟行虻男蛄行屎芨摺Ｋ?，希爾排序的時(shí)間復(fù)雜度會(huì)比o(n2)好一些。由于多次插

41、入排序，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過(guò)程中，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以shell排序是不穩(wěn)定的。所以希爾排序是不穩(wěn)定的，其時(shí)間復(fù)雜度為O(n 2)。3.5堆排序函數(shù)3.5.1基本原理堆排序思想很簡(jiǎn)單，就是每次把關(guān)鍵詞調(diào)整為堆，取出堆頂元素與堆中最后一個(gè)元素交換，同時(shí)令堆得大小減一，把剩余的一些元素重新調(diào)整為堆，重復(fù)此過(guò)程，直到堆中只剩一個(gè)元素，n 個(gè)關(guān)鍵字序列 kl , k2 ， ， kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)（簡(jiǎn)稱為堆性質(zhì)） : ( l ) ki= k2i 且 ki= k2i 且 ki=k2i

42、+1。若將此序列所存儲(chǔ)的向量 R 1n 看做是一棵完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹(shù)：樹(shù)中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于（或不小于）其左右孩子（若存在）結(jié)點(diǎn)的關(guān)鍵字。根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為小根堆。根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大根堆。注意： 堆中任一子樹(shù)亦是堆。 以上討論的堆實(shí)際上是人叉堆，類似地可定義 k 叉堆。3.5.2排序過(guò)程堆排序是一樹(shù)形選擇排序。堆排序的特點(diǎn)是：在排序過(guò)程中，將 R 1 n 看成是一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之問(wèn)的內(nèi)在關(guān)系，在當(dāng)前無(wú)序區(qū)中

43、選抒關(guān)鍵字最大（或最?。┑挠涗?。下面將從實(shí)際數(shù)據(jù)中演示其排序中的各個(gè)操作。原始數(shù)組： 22 53 72 1 1 34 44 11 15 28 3 10 65 第一步，從樹(shù)頂?shù)綐?shù)葉把數(shù)填充進(jìn)入，建立堆。紅色為卜一次交換的兩個(gè)數(shù)日宇列）。使記錄遞增有序，進(jìn)一步排序。第一次交換：第二次交換：第三次交換：第四次交換：第五次交換：第六次交換：第七次交換：第八次交換：第九次交換：全程交換完成，得到最小值為 3 并且輸出它。從序列中刪除 3 ，重新建立堆。以次循環(huán)，直到全部輸出完成為止。3.5.3堆排序算法void HeapSort(SortObject *p,unsigned long *compare,

44、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ù)組*/ pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;n=pvector-n;for(i=n/2-1;i=0;i-)Sif

45、tHeap(pvector,n,i,compare,exchange);/*首先構(gòu)造第一個(gè)堆*/for(i=n-1;i0;i-) temp=pvector-record0; pvector-record0=pvector-recordi; pvector-recordi=temp; (*exchange)+=3; SiftHeap(pvector,i,0,compare,exchange);/*重建新堆*/free(pvector);當(dāng)增量d=1時(shí)，ShellPass和InsertSort基本一致，只是由于沒(méi)有哨兵而在內(nèi)循環(huán)中增加了一個(gè)循環(huán)判定條件j0，以防下標(biāo)越界。3.5.4時(shí)間復(fù)雜度分析堆

46、排序的時(shí)間，主要由建立初始堆和反復(fù)重建堆這兩部分的時(shí)間開(kāi)銷構(gòu)成，它們均是通過(guò)調(diào)用Heapify實(shí)現(xiàn)的。堆排序的最壞時(shí)間復(fù)雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是不穩(wěn)定的，算法時(shí)間復(fù)雜度O(nlog n)。3.6快速排序函數(shù)3.6.1基本原理首先我們選擇一個(gè)中間值 middle （程序中我們可使用數(shù)組中間值），把比中問(wèn)值小的放在其左邊，比中問(wèn)值大的放在其右邊。由于這個(gè)排序算法較復(fù)雜，我們先給出其進(jìn)行一次排序的程序框架。在待排序的個(gè)記錄中任意取一個(gè)記錄（通常取第一個(gè)記錄）為區(qū)分標(biāo)準(zhǔn)，把所有小于該排序的記錄移

47、到左邊，把所有大于該排序碼的記錄移到右邊，中級(jí)放所選記錄，為一趟快速排序。然后對(duì)前后兩個(gè)子序列分別重新上述過(guò)程，直到所有記錄都排好序。對(duì)任意給定的序列中某個(gè)元素，經(jīng)過(guò)一趟排序后，將原序列分割成兩個(gè)子序列(Rp(0),Rp(1),Rp(s-1)和(Rp(s+1),Rp(s+2),Rp(n-1)，其中前一個(gè)子序列中的所有元素的關(guān)鍵詞均小于或等于該元素的關(guān)鍵詞值Kp(s)，后一個(gè)子序列中元素的關(guān)鍵詞均大于或等于Kp(s)。稱該元素Rp(s)為分割元素，子序列(Rp(0),Rp(1),Rp(s-1)為其低端序列，(Rp(0),Rp(1),Rp(s-1)為其高端序列。很明顯，以后只需對(duì)低端和高端序列分別

48、進(jìn)行快速排序，直到子序列為空或只有一個(gè)元素時(shí)結(jié)束，最后得到有序序列。總之，每趟使表的第一個(gè)元素放在適當(dāng)位置，將表兩分，再對(duì)兩子表進(jìn)行同樣的遞歸劃分，直至劃分的子表長(zhǎng)度為1！3.6.2排序過(guò)程假設(shè)要排序的數(shù)組是A1AN，首先任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱為一躺快速排序。一躺快速排序的算法是： 1）、設(shè)置兩個(gè)變量I、J，排序開(kāi)始的時(shí)候I：=1，J：=N； 2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A1； 3）、從J開(kāi)始向前搜索，即由后開(kāi)始向前搜索（J：=J-1），找到第一個(gè)小于X的值，兩者交換；

49、 4）、從I開(kāi)始向后搜索，即由前開(kāi)始向后搜索（I：=I+1），找到第一個(gè)大于X的值，兩者交換； 5）、重復(fù)第3、4步，直到I=J； 例如：待排序的數(shù)組A的值分別是：（初始關(guān)鍵數(shù)據(jù)X：=49） A1 A2 A3 A4 A5 A6 A7： 49 38 65 97 76 13 27進(jìn)行第一次交換后： 27 38 65 97 76 13 49 ( 按照算法的第三步從后面開(kāi)始找進(jìn)行第二次交換后： 27 38 49 97 76 13 65 ( 按照算法的第四步從前面開(kāi)始找X的值，6549,兩者交換，此時(shí)I：=3 )進(jìn)行第三次交換后： 27 38 13 97 76 49 65( 按照算法的第五步將又一次執(zhí)行

50、算法的第三步從后開(kāi)始找進(jìn)行第四次交換后： 27 38 13 49 76 97 65( 按照算法的第四步從前面開(kāi)始找大于X的值，9749,兩者交換，此時(shí)J：=4 ) 此時(shí)再執(zhí)行第三不的時(shí)候就發(fā)現(xiàn)I=J，從而結(jié)束一躺快速排序，那么經(jīng)過(guò)一躺快速排序之后的結(jié)果是：27 38 13 49 76 97 65，即所以大于49的數(shù)全部在49的后面，所以小于49的數(shù)全部在49的前面。 快速排序就是遞歸調(diào)用此過(guò)程在以49為中點(diǎn)分割這個(gè)數(shù)據(jù)序列，分別對(duì)前面一部分和后面一部分進(jìn)行類似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個(gè)有序的序列，根據(jù)這種思想對(duì)于上述數(shù)組A的快速排序的全過(guò)程如圖6所示：

51、初始狀態(tài) 49 38 65 97 76 13 27 進(jìn)行一次快速排序之后劃分為 27 38 13 49 76 97 65分別對(duì)前后兩部分進(jìn)行快速排序 13 27 38 結(jié)束 結(jié)束 49 65 76 97 49 65 結(jié)束 結(jié)束1）、設(shè)有N（假設(shè)N=10）個(gè)數(shù)，存放在S數(shù)組中；2）、在S1。N中任取一個(gè)元素作為比較基準(zhǔn)，例如取T=S1，起目的就是在定出T應(yīng)在排序結(jié)果中的位置K，這個(gè)K的位置在：S1。K-1=SK=right) return; i=left; j=right; temp=pvector-recordi; (*exchange)+; while(i!=j) while(pvector-recordj.key=temp.key)&(ji) (*compare)+; j-;