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

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

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

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

4、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)位置， 直到全部記錄插 入完成為止。1.2 、時間復(fù)雜度分析：直接插入排序算法必須進行 n-1 趟。最好情況下，即初始序列有序，執(zhí)行 n-1 趟，但每一趟

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

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

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

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

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

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

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

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

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

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

15、最壞性能。 由于建初始堆所需的比較次數(shù)較多， 所以堆 排序不適宜于記錄數(shù)較少的文件。 堆排序是不穩(wěn)定的， 算法時間復(fù)雜度 O（nlogn） 。五、程序流程圖六、程序源代碼#in clude<stdio.h>#in clude<stdlib.h> typedef structint key; /* 關(guān)鍵字 */RecordNode; /*排序節(jié)點的類型*/typedef structRecordNode *record;int n; /* 排序?qū)ο蟮拇笮?*/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+)/* 復(fù)制數(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+)/* 復(fù)制數(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+)/* 復(fù)制數(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+)/* 復(fù)制數(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