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

畢業(yè)論文各種排序算法性能比較 系 專業(yè) 姓名 班級 學(xué)號 指導(dǎo)教師 職稱 設(shè)計(jì)時間 各種排序算法性能比較1目錄摘要 .2第一章 緒論 .31.1 研究的背景及意義 .31.2 研究現(xiàn)狀 .31.3 本文主要內(nèi)容 .4第二章 排序基本算法 .52.1 直接插入排序 .52.1.1 基本原理 .52.1.2 排序過程 .52.1.3 時間復(fù)雜度分析 .52.2 直接選擇排序 .62.2.1 基本原理 .62.2.2 排序過程 .62.2.3 時間復(fù)雜度分析 .62.3 冒泡排序 .72.3.1 基本原理 .72.3.2 排序過程 .72.3.3 時間復(fù)雜度分析 .82.4 Shell 排序 .82.4.1 基本原理 .82.4.2 排序過程 .92.4.3 時間復(fù)雜度分析 .92.5 堆排序 .92.5.1 基本原理 .92.5.2 排序過程 .102.5.3 時間復(fù)雜度分析 .132.6 快速排序 .132.6.1 基本原理 .132.6.2 排序過程 .142.6.3 時間復(fù)雜度分析 .15第三章 系統(tǒng)設(shè)計(jì) .163.1 數(shù)據(jù)定義 .163.2 程序流程圖 .163.3 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) .173.4 系統(tǒng)的模塊劃分及模塊功能實(shí)現(xiàn) .173.4.1 系統(tǒng)模塊劃分 .173.4.2 各排序模塊功能實(shí)現(xiàn) .18第四章 運(yùn)行與測試 .29第五章 總結(jié) .31參考文獻(xiàn) .32致謝 .3335 江蘇信息職業(yè)技術(shù)學(xué)院畢業(yè)論文2摘要排序算法是數(shù)據(jù)結(jié)構(gòu)這門課程核心內(nèi)容之一。它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)排序算法是為了將實(shí)際問題中涉及的對象在計(jì)算機(jī)中進(jìn)行處理。本畢業(yè)論文對直接插入排序、直接選擇排序、起泡排序、Shell排序、快速排序以及堆排序算法進(jìn)行比較。我們設(shè)置待排序表的元素為整數(shù)，用不同的測試數(shù)據(jù)做測試比較，長度取固定的三種，對象由隨機(jī)數(shù)生成，無需人工干預(yù)來選擇或者輸入數(shù)據(jù)。比較的指標(biāo)為關(guān)鍵字的比較次數(shù)和關(guān)鍵字的移動次數(shù)。經(jīng)過比較可以看到，當(dāng)規(guī)模不斷增加時，各種算法之間的差別是很大的。這六種算法中，快速排序比較和移動的次數(shù)是最少的。也是最快的一種排序方法。堆排序和快速排序差不多，屬于同一個數(shù)量級。直接選擇排序雖然交換次數(shù)很少，但比較次數(shù)較多。關(guān)鍵字：直接插入排序；直接選擇排序；起泡排序；Shell 排序；快速排序；堆排序；各種排序算法性能比較3第一章 緒論1.1 研究的背景及意義排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作。它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關(guān)鍵字有序的序列。排序算法是在整個計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。排序算法是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。本人在研究各種算法的過程中，對其特點(diǎn)、效率、適用性等在不同的數(shù)據(jù)集上做全面的分析和比較，并以動態(tài)演示的方式展示一些經(jīng)典排序算法運(yùn)行過程，目的有以下五個方面：做算法的對比研究，培養(yǎng)研究能力；開發(fā)一個獨(dú)立的軟件，培養(yǎng)程序設(shè)計(jì)和軟件開發(fā)能力；初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；為教學(xué)服務(wù)，研究結(jié)果對抽象的 算法與數(shù)據(jù)結(jié)構(gòu) 的教學(xué)有一定的輔助作用。排序是計(jì)算機(jī)科學(xué)中最重要的研究問題之一, 它在計(jì)算機(jī)圖形、計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人、模式識別及統(tǒng)計(jì)學(xué)等領(lǐng)域具有廣泛的應(yīng)用。由于它固有的理論上的重要性,2000 年它被列為對科學(xué)和工程計(jì)算的研究與實(shí)踐影響最大的 10 大問題之一。其功能是將一個數(shù)據(jù)元素的任意序列重新排列成一個按關(guān)鍵字有序的序列。1.2 研究現(xiàn)狀隨著計(jì)算機(jī)技術(shù)的日益發(fā)展，其應(yīng)用早已不局限于簡單的數(shù)值運(yùn)算。而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì)以及插入、刪除、排序、查找等復(fù)雜的非數(shù)值處理和操作。排序算法的學(xué)習(xí)就是為以后利用計(jì)算機(jī)資源高效地開發(fā)非數(shù)值處理的計(jì)算機(jī)程序打下堅(jiān)實(shí)的理論、方法和技術(shù)基礎(chǔ)。近來國內(nèi)外專家學(xué)者們對排序算法又有了新的研究和發(fā)現(xiàn)。例如：我國山東大學(xué)的張峰和張金屯兩位教授共同研究了 我國植被數(shù)量分類和排序研究進(jìn)展 這課題。很值得有關(guān)部門去學(xué)習(xí)和研究。35 江蘇信息職業(yè)技術(shù)學(xué)院畢業(yè)論文41.3 本文主要內(nèi)容排序的方法很多，但是就其全面性能而言，很難提出一種被認(rèn)為是最好的方法，每一種方法都有各自的優(yōu)缺點(diǎn)，適合在不同的環(huán)境下使用。如果排序中依據(jù)的不同原則對內(nèi)部排序方法進(jìn)行分類，則大致可分為直接插入排序、直接選擇排序、起泡排序、Shell排序、快速排序、堆排序六類。本文編寫一個程序?qū)χ苯硬迦肱判?、直接選擇排序、起泡排序、Shell排序、快速排序及堆排序這幾種內(nèi)部排序算法進(jìn)行比較，用不同的測試數(shù)據(jù)做測試比較。比較的指標(biāo)為關(guān)鍵字的比較次數(shù)和關(guān)鍵字的移動次數(shù)。最后用圖表數(shù)據(jù)匯總，以便對這些內(nèi)部排序算法進(jìn)行性能分析。各種排序算法性能比較5第二章 排序基本算法2.1 直接插入排序2.1.1 基本原理假設(shè)待排序的 n 個記錄R0，R1，Rn 順序存放在數(shù)組中，直接插入法在插入記錄 Ri(i=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)位置，直到全部記錄插入完成為止。2.1.2 排序過程初始數(shù)據(jù)： 10 3 25 20 8 第一趟： 3 10 25 20 8 （將前兩個數(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 時間復(fù)雜度分析直接插入排序算法必須進(jìn)行 n-1 趟。最好情況下，即初始序列有序，執(zhí)行 n-1趟，但每一趟只比較一次，移動元素兩次，總的比較次數(shù)是(n-1)，移動元素次數(shù)是 2(n-1)。因此最好情況下的時間復(fù)雜度就是 O(n)。最壞情況(非遞增)下，最多比較 i 次，因此需要的比較次數(shù)是：所以，時間復(fù)雜度為 O(n2)。35 江蘇信息職業(yè)技術(shù)學(xué)院畢業(yè)論文62.2 直接選擇排序2.2.1 基本原理待排序的一組數(shù)據(jù)元素中，選出最小的一個數(shù)據(jù)元素與第一個位置的數(shù)據(jù)元素交換；然后在剩下的數(shù)據(jù)元素當(dāng)中再找最小的與第二個位置的數(shù)據(jù)元素交換，循環(huán)到只剩下最后一個數(shù)據(jù)元素為止，依次類推直到所有記錄。第一趟第 n 個記錄中找出關(guān)鍵碼最小的記錄與第 n 個記錄交換；第二趟，從第二個記錄開始的，2 -1 個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換；如此，第 i 趟，則從第 i 個記錄開始的 n - i + l 個記錄中選出關(guān)鍵碼最小的記錄與第 i 個記錄交換，直到所有記錄排好序。2.2.2 排序過程初始數(shù)據(jù) 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最后排序結(jié)果 13 27 38 49 49 76 76 972.2.3 時間復(fù)雜度分析該算法運(yùn)行時間與元素的初始排列無關(guān)。不論初始排列如何，該算法都必須執(zhí)行 n-1 趟，每趟執(zhí)行 n-i-1 次關(guān)鍵字的比較，這樣總的比較次數(shù)為：所以，簡單選擇排序的最好、最壞和平均情況的時間復(fù)雜度都為 O(n2)。各種排序算法性能比較72.3 冒泡排序2.3.1 基本原理在每一趟冒泡排序中，依次比較相鄰的兩個關(guān)鍵字大小，若為反序咋交換。經(jīng)過一趟起泡后，關(guān)鍵詞大的必須移到最后。按照這種方式進(jìn)行第一趟在序列（I0In-1）中從前往后進(jìn)行兩個相鄰元素的比較，若后者小，則交換，比較 n-1 次；第一趟排序結(jié)束，最大元素被交換到 In-1中，下一趟只需在子序列（I0In-2）中進(jìn)行；如果在某一趟排序中未交換元素，則不再進(jìn)行下一趟排序。將被排序的記錄數(shù)組 J1 n垂直排列，每個記錄 Ji看作是重量為 Ji.key 的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組 R：凡掃描到違反本原則的輕氣泡，就使其向上“飄浮“ 。如此反復(fù)進(jìn)行，直到最后任何兩個氣泡都是輕者在上，重者在下為止，最后可完成。2.3.2 排序過程將被排序的記錄數(shù)組 R1 n垂直排列，每個記錄 Ri看作是重量為 Ri.key 的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組 R：凡掃描到違反本原則的輕氣泡，就使其向上“飄浮“。如此反復(fù)進(jìn)行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。（1）初