排序綜合數(shù)據結構課程設計論文

1、排序綜合成都吃喝網 00 0 0 0二10 年 6 月1題 目 ） N 44第 3天 年月日年月日年月日遵守各項紀律，工作刻苦努力，具有良好的科學工作態(tài)度。6作表通過實驗、試驗、查閱文獻、深入生產實踐等渠道獲取與課程設計有關的材料。能運用所學知識和技能去發(fā)現(xiàn)與解決實際問題，能正確處理實驗數(shù)據，能對課題進行理論分析，得出有價值的結論。能獨立查閱相關文獻和從事其他調研；能提出并較好地論述課題的實施方案；有收集、加工各種信息及獲取新知識的能力。能力操作等實驗工作，數(shù)據正確、可靠；研究思路清晰、完整。水平55具有較強的數(shù)據運算與處理能力；能運用計算機進行資料搜集、加工、處理和輔助設計等。 符合本專業(yè)相

2、關規(guī)范或規(guī)定要求；規(guī)范化符合本文件第五條要求。成果質量綜述簡練完整，有見解；立論正確，論述充分，結論嚴謹合理；實驗正確，分析處理科學。 對前人工作有改進或突破，或有獨特見解。指導教師評語年 月 日- 2 -2摘 要數(shù)據結構是由數(shù)據元素依據某種邏輯聯(lián)系組織起來的。對數(shù)據元素間邏輯關系的描述稱為數(shù)據的邏輯結構；數(shù)據必須在計算機內存儲，數(shù)據的存儲結構是數(shù)據結構的實現(xiàn)形式，是其在計算機內的表示；此外討論一個數(shù)據結構必須同時討論在該類數(shù)據上執(zhí)行的運算才有意義。在許多類型的程序的設計中，數(shù)據結構的選擇是一個基本的設計考慮因素。許多大系統(tǒng)的構造經驗表明，系統(tǒng)實現(xiàn)的困難程度和系統(tǒng)構造的質量都嚴重的依賴于是否選

3、擇了最優(yōu)的數(shù)據結構。許多時候，確定了數(shù)據結構后，算法就容易得到了。有些時候事情也會反過來，我們根據特定算法來選擇數(shù)據結構與之適應。不論哪種情況，選擇合適的數(shù)據結構都是非常重要的。排序算型泡排序，直接插入排序，簡單選擇排序，希爾排序，快速排序，堆排序等，各有情況而定。在下面的討論中我們主要考慮用比較的次數(shù)作為復雜性的度量。關鍵字 數(shù)據結構；算法比較；比較次數(shù)；時間復雜度- 3 -3目錄摘要. 11概要. 4 4 52排序算法 . 7 8 8 9 9 9 9 9 3流程圖及詳細算法. 10 4運行結果 . 18 5結束語 . 25參考文獻. 24- 4 -41 1.1 設計目的數(shù)據結構與算法課程主

4、要是研究非數(shù)值計算的程序設計問題中所出現(xiàn)的機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設計、數(shù)據庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎，廣泛的應用于信息學、進學生的綜合應用能力和專業(yè)素質的提高。1）本演示程序對以下 6 種常用的內部排序算法進行實測比較：冒泡排序，直接插入排序，簡單選擇排序，快速排序，希爾排序，堆排序；2）待排序表的元素的關鍵字為整數(shù)。比較的指標為有關鍵字參加的比較次數(shù)和關鍵字的移動次數(shù)（關鍵字交換記為 3 次移動）；3）演示程序以以用戶和計算機的對話方式執(zhí)行，在計算機終端上顯示提示信息，對隨機數(shù)組進行排序，并輸出比較指標值；4）最后對結果作出簡單分析

5、。1.2 預期目標到對各算法進行比較的目的。通過此次課程設計主要達到以下目的了解并掌握數(shù)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能；提高綜合運用發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法和作風。- 5 -52 2.1 各排序算法的特點1）冒泡排序 1 2 2 第 3 2 3 1 2 2）直接插入排序 , ; 3）簡單選擇排序（1）在一組元素ViVn-12）若它不是這3素中剔除這個具有最小排序碼的元素，在剩下的元素 Vi+1Vn-1中重復執(zhí)行第（12）步，直到剩余元素只有一個為止。4）快速排序放在一組，其余的放在另一組，然后分別對兩組數(shù)據排序；5） 希爾排序先取

6、一個正整數(shù) d1n，把所有序號相隔d1 的數(shù)組元素放一組，組內進行直接插入排序；然后取d2d1，重復上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止；6) 堆排序- 6 -6堆排序是一樹形選擇排序，在排序過程中，將 R1.N看成是一顆完全二叉擇最小的元素；堆的定義: N 個元素的序列 K1K2K3.，Kn.稱為堆，當且僅當該序列滿足特性：KiK2i Ki K2i+1(1 IN/2)2.2各算法的比較方法1.穩(wěn)定性比較插入排序、冒泡排序、簡單選擇排序及其他線形排序是穩(wěn)定的希爾排序、快速排序、堆排序是不穩(wěn)定的2.時間復雜性比較插入排序、冒泡排序、選擇排序的時間復雜性為 O(n2)其

7、它非線形排序的時間復雜性為 O(nlog2n)線形排序的時間復雜性為 O(n);3.輔助空間的比較線形排序的輔助空間為 O(n),其它排序的輔助空間為 O(1);4.其它比較序能達到較快的速度。反而在這種情況下，快速排序反而慢了。當 n 入或冒泡排序。若待排序的記錄的關鍵字在一個明顯有限范圍內時 ,且空間允許是用桶排序。當 n 較大時，關鍵字元素比較隨機，對穩(wěn)定性沒要求宜用快速排序。當 n 允許的情況下，宜用歸并排序。當 n 堆排序- 7 -73 3.1流程圖函數(shù)的調用關系圖反映了演示程序的層次結構：strandBubbleSortInsertSortSelectSortQuickSortSh

8、ellSortHeapSorInitLinkListRandomNuLTDisplay圖 3.21）Main 為主函數(shù)模塊2bubblesortinsertsortselectsortquicksortshellsortheansort分別對應冒泡排序，直接插入排序，簡單選擇排序，快速排序，希爾排序，堆排序的各函數(shù)模塊3）在初始化數(shù)據之后，選擇對應的排序模塊進行排序，并對排序做出比較3.3 可排序表的抽象數(shù)據類型定義：typedef structint key;/定義一個RedType型結構體，存放關鍵字/關鍵字為整型 RedType;class LinkList/定義一個順序表- 8 -8p

9、ublic:RedType rMAXSIZE+1;為RedType/長度為MAXSIZE+1的數(shù)組r，數(shù)組里每個元素均int Length;/數(shù)組長度int CmpNum, ChgNum;LinkList();/關鍵字的比較次數(shù)，移動次數(shù)/構造函數(shù)bool LT(int i, int j);void Display();void Insert( int dk);void ShellSort();/比較i和j的大小/輸出數(shù)組元素/插入排序/希爾排序int Partition( int low, int high); /比基準小的數(shù)放左邊，比起大的數(shù)放右邊，返回基準位置void QSort( in

10、t low, int high); /從low到high位置進行快速排序void QuickSort();/對有序表進行快速排序void HeapAdjust( int s, int m); /將無序堆調整為大頂堆void HeapSort();/堆排序，將大頂堆轉換為小頂堆/冒泡排序void BubbleSort();int SelectMinKey( int k);void SelSort();/找到數(shù)組中最小值，返回最小值位置/對順序表進行選擇排序void SelectSort();void AllAbove();/界面設計/統(tǒng)計以上所有排序關鍵字的比較次數(shù)、移動次數(shù)及所消耗的時間;3.

11、4 程序代碼3.4.1 函數(shù)聲明- 9 -910 = i =- 10 -10 4.3.2 六種排序算法代碼/插入排序 = i - =i- j0 j + + - 11 -11/希爾排序 /快速排序 = = - + - 12 -12 -/堆排序 j= - =2* j j - - i-/冒泡排序 = i = j- +- 13 -13 + + /選擇排序 = k = = i j= 4.3.3 排序算法的選擇 - 14 -14 = - = - = - = - 15 -15 = - = -4.3.4主函數(shù)程序代碼 = = = - - 16 -16 = - = - = - =- 17 -17= - = -

12、4 4.1 調試分析1對正序、逆序和若干不同程度隨機打亂的可排序表，進行各種排序方法定程序的隨機亂序算法，對偽隨機數(shù)序列的產生有了具體的認識和實踐。2將排序算法中的關鍵字比較和交換分別由 Less 和 Swap 兩個內部操作實- 18 -18圖 1圖 2圖 3圖 4圖 5圖 6圖 74.3 排序算法的評價對各種表長和測試組數(shù)進行了測試，程序運行正常。分析實測得到的數(shù)值，6插入排序 希爾排序 快速排序 堆排序 冒泡排序 選擇排序第三多第二多 亂否差異 亂否差異 亂否差異 與亂否無很小稍多移動次數(shù) 排序的兩 亂否差異 亂否差異 正和逆序越多 較小 很小 越多(1)若n較小(如n50)，可采用直接插

13、入或直接選擇排序。倍少于直接插人，應選直接選擇排序為宜。(2)若文件初始狀態(tài)基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；(3)若n較大，則應采用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。在一個學期后的基礎理論知識的學習后進入實踐的操作雖然仍就有些困難會通過實習我的收獲如下1、鞏固和加深了對數(shù)據結構的理解，提高綜合運用本課程所學知識的能力。2、培養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。培養(yǎng)獨立思考，深入研究，分析問題、解決問題的能力。3、通過實際編譯系統(tǒng)- 23 -23的分析設計、編程調試，掌握應用軟件的分析方法和工程設計方法。4、通過課全局觀念。

14、根據我在實習中遇到得問題，我將在以后的學習過程中注意以下幾點： 1、認真上好專業(yè)實驗課，多在實踐中鍛煉自己。2、寫程序的過程中要考慮周到，嚴密。3、在做設計的時候要有信心，有耐心，切勿浮躁。4、認真的學習課本知識，掌握課本中的知識點，并在此基礎上學會靈活運用。5、在課余時程序的能力，學習文檔編寫規(guī)范，培養(yǎng)獨立學習、吸取他人經驗，樹立團隊協(xié)作得深入了解剖析它以便得到提高。細心、耐心、團結、求知，是我這次課程設計最大的收獲。同時要感謝老師這幾天的悉心教導。1 寧正元，王秀麗.算法與數(shù)據的結構，2006：29322 楊輝.楊輝的縱橫圖論，2003：12143 唐王希.太乙金鏡式經，2000：35374 王力柱。與數(shù)據結構。棧，2003（81