1、數據結構課程設計設計說明書內部堆排序算法的實現學生姓名 金少偉 學 號 1121024029 班 級 信管1101 成 績 指導教師 曹陽 數學與計算機科學學院2013年3月15日 課程設計任務書20122013學年第二學期課程設計名稱： 數據結構課程設計 課程設計題目： 內部堆排序算法的實現 完 成 期 限：自 2013年 3 月4日至 2013年 3 月 15 日共 2 周設計內容： 堆排序（heap sort）是直接選擇排序法的改進，排序時，需要一個記錄大小的輔助空間。n個關鍵字序列K1，K2，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)： kiK2i且kiK2i+1 或(2)

2、KiK2i且kiK2i+1(1i n) 若將此序列所存儲的向量R1.n看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在)結點的關鍵字。 （即如果按照線性存儲該樹，可得到一個不下降序列或不上升序列）。 本課程設計中主要完成以下內容： 1.設計堆排序算法并實現該算法。 2.對堆排序的時間復雜度及空間復雜度進行計算與探討。 3.尋找改進堆排序的方法。 基本要求如下： 1.程序設計界面友好；2.設計思想闡述清晰；3.算法流程圖正確；4.軟件測試方案合理、有效。指導教師：曹陽 教研室負責人：申靜課程設計評閱評語： 指導教

3、師簽名： 年 月 日摘 要堆排序是直接選擇排序法的改進。本課設以VC+6.0作為開發環境，C語言作為編程語言，編程實現了堆排序算法。程序運行正確，操作簡單，易于為用戶接受。關鍵詞：堆排序；C語言；時間復雜度目 錄1課題描述12. 算法描述22.1 堆排序描述22.2 堆排序算法的圖示22.3 堆排序算法53算法流程圖64代碼實現75. 算法分析106. 測試11總結12參考文獻131 課題描述查找是計算機的一項主要功能，為了查找方便，通常希望計算機中的表是按關鍵字是有序的。因為有序的順序表可采用查找效率較高的折半查找法，而無序的表只能進行順序查找。因此排序也就是計算機程序設計中的一種重要操作，

4、它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個按關鍵字有序的序列。因此，學習和研究各種排序方法是計算機工作者的重要課題之一。本課題利用簡單選擇排序中的堆排序方法，通過對用戶輸入的可以組成堆的數據元素建立大、小根堆，并將其進行排序輸出，使其成為一個按關鍵字排序的有序序列，從而有效地提高了查找的效率。開發工具：vc+6.02. 算法描述2.1 堆排序描述堆排序只需要一個記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。堆的定義如下：n個元素的序列（k1,k2,kn）當且僅當滿足下關系時，稱之為堆。kiK2i且kiK2i+1 或(2)KiK2i且kiK2i+1(1i n) 若將和

5、此程序對應的一維數組看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結點的值均不大于（或小不于）其左、右孩子結點的值。由此，若序列k1,k2,kn是堆，則堆頂元素必須為序列中n 的元素的最大值。例如，下列一個序列為堆，對應的完全二叉樹如圖2.1所示。96,83,27,38,11,9 98278338119圖2.1序列96,83,27,38,11,9對應的堆若再輸出堆頂的最大值之后，使得剩余n-1個元素的序列重又建成一個堆，則得到n元素中的最大值。如此反復執行，便能得到一個有序序列，這個過程稱之為堆排序。2.2 堆排序算法的圖示 一組無序序列：49,38,65,97,76,13,27

6、,49 堆排序算法的演示過程如圖2.2.和圖2.3所示： 499381376652797494938657613274997 (a) (b)49976576132749384997657613274938(c) (d)9776654913274938(e)圖2.2 建初始堆過程示例 49766549132797387649654913279738 （a） (b)27496549137697386549274913769738 (c) (d)13492749657697384913274965769738(e) (f)491327494965769738381327494965769749(g)

7、 (h) 271338494965769749132738494965769749（l） (m)圖2.3輸出對元素并調整建新堆的過程2.3 堆排序算法堆排序算法代碼如下：Typedef Sqlist HeapType;Void HeapAdjust( HeapType &H,int s,int m)/j建大頂堆函數 RC=H.rs; for(j=2*s;j=m;j*=2) if(j0;-i) HeapAdjust( H, i, H.length) for (i=H.length;i1;-i) t=H.r1; /交換堆頂元素與堆中最后一個元素 H.r1 =H.ri; H.ri=t; HeapAd

8、just(H,1 ,i-1);3算法流程圖建堆過程流程圖如圖3.1所示：圖3.1建堆流程圖堆排序流程圖如圖3.2所示： 圖3.2堆排序流程圖4代碼實現程序源代碼：#include#include#include#define MAX 50/數據輸入子函數void InputData(int list) int i=1;printf(請輸入要排序的數據（以-1結束）:n);/用-1表示數據輸入結束，-1不包括在排序數據中scanf(%d,&listi); while(listi!=-1)i+;scanf(%d,&listi); list0=i-1;/list0用來放list數組的長度/void

9、panduan(int list,int n) int i=1; for(i=1;in;i+) if(isdigit(listi)=0) printf(序列為非完全數字序列，無法排序。n); exit(0); /數據輸出子函數void OutputData(int list,int n) int i=1;printf(排序后的數列是:n);for(i=1;i=n;i+) if(i%4=0) printf(n); printf(%dt,listi); printf(n); /創建大頂堆子函數void HeapAdjust(int list,int s, int m)int j, rc;rc=li

10、sts;for(j=2*s;jm;j*=2)if(j=m&(listj=listj)break;lists=listj;s=j;lists=rc;/堆排序子函數void HeapSort(int list,int n) int i,t;for(i=n/2;i0;i-)HeapAdjust(list,i,n); for(i=n;i1;i-)t=list1;list1=listi;listi=t;HeapAdjust(list,1,i-1);/界面子函數void UI () printf(*內部堆排序程序*n); printf(程序操作如下n); printf(*n);/主函數void main(

11、) UI ();int n;int listMAX;InputData(list); n=list0; panduan(list,n); HeapSort(list,n);OutputData(list,n);5.算法分析對深度為h的堆，篩選算法中進行的關鍵字比較次數至多為2(h-1)次，則在建立含n個元素、深度為h的堆時，總共進行的關鍵字比較次數不超過4n。而n個結點的完全二叉樹的深度為log2n+1，則調整建新堆時調用Heapadjust過程n-1次，總共進行的比較次數由此，在最壞的情況下，堆排序的時間復雜度為 理論上已經證明任何一種比較排序算法在最壞的情況下所需做的鍵比較次數至少是故堆排

12、序算法的任何改進已不可能降低數量級，而只能設法降低復雜度因子。因此，對算法的改進應從降低 t ( n)開始。6. 測試運行以上程序，輸入合法數據，得到運行界面如圖6.1所示：圖6.1輸入合法數據得到運行界面輸入不合法數據，得到運行界面如圖6.2所示：圖6.2輸入不合法數據得到運行界面 總結 課設過程是一個痛苦并且快樂的過程，痛苦的是在完成他的過程是異常艱苦的，快樂是完成它后的欣慰與喜悅。通過兩周的課程設計，我收獲了很多東西，在課程設計的過程中我不僅復習了原來學過的知識，而且我對學過知識的應用以及如何操作也有了一個較全面的理解。本次課設我主要是應用了所學習的C編程語言和軟件，以及數據結構的相關知

13、識，并參考相關書籍以及請教老師和同學，綜合起來才完成了這次課程設計。在課設的過程中我遇到了許多問題，每次當覺得自己多的程序無發進行下去時，同組的伙伴都會鼓勵我堅持，后來的事實證明堅持就是勝利，再難的問題只要你勇敢的向他挑戰，堅持下去，問題總會被解決的，這也是我在這次課設中收獲最大的。排序是計算機程序設計中極其重要的一部分，是計算機程序設計中的一個重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個按關鍵字有序的序列。學習和研究各種排序方法是計算機工作者的重要課題之一。堆排序是選擇排序中的一種，它只需要一個記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。堆排序方法對記錄較少的文件不值得提倡，但對于較大的文件是很有效的。堆排序在最壞的情況下，其時間復雜度也為O（nlogn）。相對于快速排序來說，這是最大的優點。這次課程設計我主要應用所學，通過在C環境下，實現了對符合堆的無序序列進行排序