數(shù)據(jù)結構課程設計報告各種排序算法性能比較

1、EAST CHINA INSTITUTE OF TECHNOLOGY課程設計報告課程設計題目：各種排序算法性能比較學生姓名：學 號：專 業(yè)：信息管理與信息系統(tǒng)班級：指導教師：2012年06月23日目錄CONTENTS一、課程設計目的 2二、課程設計題目概述 2三、數(shù)據(jù)定義 2四、各種排序的基本原理及時間復雜度分析 3五、程序流程圖 6六、程序源代碼 6七、程序運行與測試 15八、實驗體會九、參考文獻、 課 程設計目的課程設計為學生提供了一個既動手又動腦， 獨立實踐的機會， 將課本上的理 論知識和實際有機的結合起來， 鍛煉學生的分析解決實際問題的能力。 提高學生 適應實際，實踐編程的能力。二、課

2、程設計題目概述排序的方法很多， 但是就其全面性能而言， 很難提出一種被認為是最好的方 法，每一種方法都有各自的優(yōu)缺點， 適合在不同的環(huán)境下使用。 如果排序中依據(jù) 的不同原則對內部排序方法進行分類， 則大致可分為直接插入排序、 直接選擇排 序、起泡排序、Shell排序、快速排序、堆排序等六類排序算法。本實驗是對直接插入排序、直接選擇排序、起泡排序、Shell排序、快速排序、 堆排序這幾種內部排序算法進行比較， 用不同的測試數(shù)據(jù)做測試比較。 比較的指 標為關鍵字的比較次數(shù)和關鍵字的移動次數(shù)。 最后用圖表數(shù)據(jù)匯總， 以便對這些 內部排序算法進行性能分析。三、數(shù)據(jù)定義輸入數(shù)據(jù)： 由于大多數(shù)排序算法的時

3、間開銷主要是關鍵字之間的比較和記錄的移動， 算 法的執(zhí)行時間不僅依賴于問題的規(guī)模， 還取決于輸入實例中數(shù)據(jù)的狀態(tài)。 所以對 于輸入數(shù)據(jù)， 我們采用由用戶輸入記錄的個數(shù) （以關鍵字的數(shù)目分別為 20，100， 500 為例），測試數(shù)據(jù)由隨機數(shù)產生器生成。輸出數(shù)據(jù)：產生的隨機數(shù)分別用直接插入排序；直接選擇排序；起泡排序；Shell排序；快速排序；堆排序這些排序方法進行排序，輸出關鍵字的比較次數(shù)和移動次數(shù)。四、各種排序的基本原理及時間復雜度分析1、直接插入排序( InsertSort)1.1 、基本原理：假設待排序的n個記錄RO, R1,，Rn順序存放在數(shù)組中，直接插入法在 插入記錄Ri(i=1 ,

4、2,，n-1)時，記錄被劃分為兩個區(qū)間R0,Ri-1和Ri+1,Rn-1, 其中，前一個子區(qū)間已經排好序， 后一個子區(qū)間是當前未排序的部分， 將關鍵碼 Ki與Ki-1Ki-2，K0依次比較，找出應該插入的位置，將記錄 Ri插，然后 將剩下的 i-1 個元素按關鍵詞大小依次插入該有序序列， 沒插入一個元素后依然 保持該序列有序， 經過 i-1 趟排序后即成為有序序列。 每次將一個待排序的記錄， 按其關鍵字大小插入到前面已經排好序的子文件中的適當位置， 直到全部記錄插 入完成為止。1.2 、時間復雜度分析：直接插入排序算法必須進行 n-1 趟。最好情況下，即初始序列有序，執(zhí)行 n-1 趟，但每一趟

5、只比較一次，移動元素兩次，總的比較次數(shù)是 (n-1) ，移動元 素次數(shù)是2(n-1)。因此最好情況下的時間復雜度就是 0(n)。最壞情況(非遞增) 下，最多比較 i 次，因此需要的比較次數(shù)是：所以，時間復雜度為O(n2)。2、直接選擇排序( SelectSort)2.1 、基本原理：待排序的一組數(shù)據(jù)元素中， 選出最小的一個數(shù)據(jù)元素與第一個位置的數(shù)據(jù)元 素交換；然后在剩下的數(shù)據(jù)元素當中再找最小的與第二個位置的數(shù)據(jù)元素交換， 循環(huán)到只剩下最后一個數(shù)據(jù)元素為止， 依次類推直到所有記錄。 第一趟第 n 個記 錄中找出關鍵碼最小的記錄與第 n個記錄交換；第二趟，從第二個記錄開始的， 2 -1 個記錄中再

6、選出關鍵碼最小的記錄與第二個記錄交換； 如此，第 i 趟，則從 第 i 個記錄開始的 n - i + l 個記錄中選出關鍵碼最小的記錄與第 i 個記錄交換， 直到所有記錄排好序。2.2、時間復雜度分析：3 / 21該算法運行時間與元素的初始排列無關。 不論初始排列如何， 該算法都必須 執(zhí)行 n-1 趟，每趟執(zhí)行 n-i-1 次關鍵字的比較，這樣總的比較次數(shù)為：所以，簡 單選擇排序的最好、最壞和平均情況的時間復雜度都為O(n2) 。3、冒泡排序( BubbleSort)3.1 、基本原理在每一趟冒泡排序中，依次比較相鄰的兩個關鍵字大小，若為反序咋交換。 經過一趟起泡后，關鍵詞大的必須移到最后。按

7、照這種方式進行第一趟在序列 ( I0In-1 )中從前往后進行兩個相鄰元素的比較，若后者小，則交換，比 較 n-1 次；第一趟排序結束，最大元素被交換到 In-1 中，下一趟只需在子序 列( I0In-2)中進行；如果在某一趟排序中未交換元素，則不再進行下一趟排序。將被排序的記錄數(shù)組 J1n垂直排列，每個記錄Ji看作是重量為 Ji.key 的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上 "飄浮"。如此反復進行，直到最后任 何兩個氣泡都是輕者在上，重者在下為止，最后可完成 。3.2 、時間復雜度分析當原始數(shù)據(jù)正向有序時，

8、冒泡排序出現(xiàn)最好情況。 此時，只需進行一趟排序， 作n-1次關鍵字比較，因此最好情況下的時間復雜度是0(n)。當原始數(shù)據(jù)反向有序時，冒泡排序出現(xiàn)最壞情況。此時，需進行n-1趟排序，第i趟作(n-i)次關鍵字間的比較，并且需執(zhí)行 (n-i) 次元素交換，所以，比較次數(shù)為：因此 , 最壞 情況下的時間復雜度為 0(n2) 4、Shell 排序( ShellSort )4.1 、基本原理Shell 排序又稱縮小增量排序 ,Shell 排序法是以創(chuàng)建者 Donald Shell 的名 字命名的 .Shell 排序法是對相鄰指定距離 (稱為間隔 ) 的元素進行比較 ,已知到使 用當前間隔進行比較的元素都

9、按順序排序為止 .Shell 把間隔縮小一半 , 然后繼續(xù) 處理, 當間隔最終變?yōu)?1 ,并且不再出現(xiàn)變化時 ,Shell 排序也就完成了其處理過 程.先取一個整數(shù)d1<n,把全部記錄分成di個組，所有距離為di倍數(shù)的記錄放 在一組中，先在各組內排序； 然后去 d2<d1 重復上訴分組和排序工作；直至所取 的增量dt=1(dt<dt- l<<d2<d1)，即所有記錄放在同一組中進行直接插入，直 到 dt=i ，即所有記錄放在一組中為止。4.2 、時間復雜度分析希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時 候，步長最大，所以插入排序的元素個

10、數(shù)很少，速度很快；當元素基本有序了， 步長很小，插入排序對于有序的序列效率很高。所以， 希爾排序的時間復雜度會2比 o(n2) 好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改 變相同元素的相對順序， 但在不同的插入排序過程中， 相同的元素可能在各自的 插入排序中移動，最后其穩(wěn)定性就會被打亂， 所以 shell 排序是不穩(wěn)定的。所以 希爾排序是不穩(wěn)定的，其時間復雜度為 o(n2) 。5、快速排序( QuickSort)5.1 基本原理首先我們選擇一個中間值 middle (程序中我們可使用數(shù)組中間值)，把比 中問值小的放在其左邊，比中問值大的放在其右邊。由于這個排序算法較復雜，

11、我們先給出其進行一次排序的程序框架。在待排序的個記錄中任意取一個記錄 (通常取第一個記錄) 為區(qū)分標準，把所有小于該排序的記錄移到左邊，把所有 大于該排序碼的記錄移到右邊，中級放所選記錄，為一趟快速排序。 然后對前后 兩個子序列分別重新上述過程， 直到所有記錄都排好序。 對任意給定的序列中某 個元素，經過一趟排序后，將原序列分割成兩個子序列(Rp(°),Rp(i),Rp(i )和(Rp(s+1) ,Rp(s+2),Rp(n-1)，其中前一個子序列中的所有元素的關鍵詞均小于或等于 該元素的關鍵詞值 $s),后一個子序列中元素的關鍵詞均大于或等于Kp(s)。稱該元素&s)為分割元

12、素，子序列(Rp(0),Rp(i),Rp(s-i)為其低端序列，(Rp(o),Rp(i),Rp(s-i)為其咼端序列。很明顯，以后只需對低端和咼端序列分別進 行快速排序， 直到子序列為空或只有一個元素時結束， 最后得到有序序列。 總之， 每趟使表的第一個元素放在適當位置， 將表兩分，再對子表進行同樣的遞歸劃分， 直至劃分的子表長度為 1。5.2 、時間復雜度分析如果每一次分劃操作后， 左、右兩個子序列的長度基本相等，則快速排序的 效率最咼，其最好情況時間復雜度為O(nlog 2n) ；反之，如果每次分劃操作所產生的兩個子序列，其中之一為空序列，此時，快速排序效率最低，其最壞情況時 間復雜度為

13、O(n2) 。如果選擇左邊第一個元素為主元，則快速排序的最壞情況發(fā) 生在原始序列正向有序或反向有序時。快速排序的平均情況時間復雜度為 O(nlog 2n) 。6、堆排序（ Heapsort ）6.1 、基本原理堆排序思想很簡單， 就是每次把關鍵詞調整為堆， 取出堆頂元素與堆中最后 一個元素交換，同時令堆的大小減一， 把剩余的一些元素重新調整為堆， 重復此 過程，知道堆中只剩下一個元素，n個關鍵字序列K1,K2,K3, 稱為堆，當且僅當該序列滿足如下性質（簡稱為堆性質）：（1 ） Ki<=K2i 且 Ki<=K2i+1或（2） Kiv=K2i且Ki>=K2i+1.。若將此序列所

14、存儲的向量 R1n看作是一棵 完全二叉樹的存儲結構， 則堆實質上是滿足如下性質的完全二叉樹： 樹中非葉子 結點的關鍵字均不大于（或不小于）其左右孩子（若存在）結點的關鍵字。根結 點（亦稱為堆頂） 的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。 根 結點（亦稱為堆頂）的關鍵字是堆里所有結點關鍵字中的最大者，稱為大根堆。注意：堆中任一子樹亦是堆。以上討論的實際上是二叉堆，類似的可以定義K叉堆6.2 時間復雜度分析堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成， 它們均是通過調用 Heapify 實現(xiàn)的。堆排序的最壞時間復雜度為 O（nlogn） 。堆 排序的平均性能較接近于

15、最壞性能。 由于建初始堆所需的比較次數(shù)較多， 所以堆 排序不適宜于記錄數(shù)較少的文件。 堆排序是不穩(wěn)定的， 算法時間復雜度 O（nlogn） 。五、程序流程圖六、程序源代碼#in clude<stdio.h>#in clude<stdlib.h> typedef structint key; /* 關鍵字 */RecordNode; /*排序節(jié)點的類型*/typedef structRecordNode *record;int n; /* 排序對象的大小 */SortObject; /* 排序節(jié)點的類型 */void InsertSort(SortObject *p,un

16、signed 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;*exc

17、hange=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);void SelectSort(Sor

18、tObject *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

19、;*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);void Bu

20、bbleSort(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;pve

21、ctor->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;nos

22、wap=0;if(noswap) break;free(pvector);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

23、;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)+;

24、pvector->recordj+increment=pvector->recordj;(*exchange)+;j-=increment;pvector->recordj+increment=temp;(*exchange)+;free(pvector);longVoid SiftHeap(SortObject *pvector,int size,int p,unsigned long *compare,unsigned *exchange)RecordNode temp;int i,child;temp=pvector->recordp;(*exchange)+;i

25、=p;child=2*i+1;while(child<size)if(child<size-1&&pvector->recordchild.key<pvector->recordchild+1.key)(*compare) +;child+;if(temp.key<pvector->recordchild.key)(*compare)+;pvector->recordi=pvector->recordchild;(*exchange)+;i=child;child=2*i+1;else break;pvector->r

26、ecordi=temp;(*exchange)+;void HeapSort(SortObject *p,unsigned long *compare,unsigned long *exchange) 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+)pvector->recordi=p-&g

27、t;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); temp=pvector->record0;pvector->record0=pvector->recordi;pvector->recordi=temp;(*exchange)+=3;SiftHeap(pvector,i,0,compare,exchange);free(pvector);void Qui

28、ckSort(SortObject *pvector,int left,int right,unsigned long*compare,unsigned long *exchange) 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-;if(i<j)pvecto

29、r->recordi+=pvector->recordj;(*exchange)+;while(pvector->recordi.key<=temp.key)&&(j>i)(*compare)+;i+;if(i<j)pvector->recordj-=pvector->recordi;(*exchange)+;pvector->recordi=temp;(*exchange)+;QuickSort(pvector,left,i-1,compare,exchange);QuickSort(pvector,i+1,right,c

30、ompare,exchange);void SortMethod(void) int i,j;unsigned long num312=0;SortObject *pvector=(SortObject *)malloc(sizeof(SortObject);int random;randomize();for(j=0;j<3;j+) for(i=0;i<MAXSORTNUMj;i+)pvector->recordi.key=random(5000);pvector->n=MAXSORTNUMj;InsertSort(pvector,&numj0,&nu

31、mj1);SelectSort(pvector,&numj2,&numj3);BubbleSort(pvector,&numj4,&numj5);ShellSort(pvector,4,&numj6,&numj7);Heapsort(pvector,&numj8,&numj9);QuickSort(pvector,0,MAXSORTNUMj-1,&numj10,&numj11);printf("nSort Method Compare As Follows:");for(j=0;j<3;j

32、+)printf("nnWhen The max num is %d,the result is:n",MAXSORTNUMj);printf("1.InsertSort Method:Compared->%-7ldExchanged->%-7ldn",numj0,numj1);printf("2.SelectSort Method:Compared->%-7ldExchanged->%-7ldn",numj2,numj3);printf("3.BubbleSort Method:Compared-&

33、gt;%-7ld Exchanged->%-7ldn",numj4,numj5);printf("4.ShellSort Method:Compared->%-7ldExchanged->%-7ldn",numj6,numj7);printf("5.HeapSort Method:Compared->%-7ldExchanged->%-7ldn",numj8,numj9);printf("6.QuickSortMethod:Compared->%-7ldExchanged->%-7ldn&qu

34、ot;,numj10,numj11);if(j!=2)printf("Press Enter to continue.n");sgetchar();void mai n()SortMethod();七、程序運行與測試C: .'i'll1132 u->d. -eXfSorjt Method Conpar« Rs Follows:Mhcr Th吐 lux 1.InsertSort 2.SelectScrt p.BubbleScrt 4+SliellSQrl 5.HeapSort b. (Quicksort Press Enternuu i.s 2

35、0,the result isHcthad:Compared一>100Method:Compared >190 Nethcd：CoMpctrecl ->167 Mclhod; Conoctred一>52 Hethod:Corapnred->6H Hethcd:Compared->17 to Coniinue.Exchanged >/i8 Exchanged- >300 匚xchancd一一>15S Exclianaed一>48 Fxchnnjed一一>3b圖7.1數(shù)據(jù)長度為20時算法運行界面When Tlie radx nun is 100, the reuul I is :1.InsertSort ? SclcctSort3.BubhleSort 4.Shell Sort !i. HeripSort 右.Qu:irkSor t Press EnterMelliod: Comwred>24 /8 Hc!thod Co»p