數(shù)據(jù)結(jié)構(gòu)課程設(shè)計十種排序算法比較教材

1、合肥學(xué)院計算機科學(xué)與技術(shù)系課程設(shè)計報告20142015學(xué)年第 學(xué)期課程數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計名稱內(nèi)部排序算法比較學(xué)生姓名學(xué)號專業(yè)班級指導(dǎo)教師2015 年1 月課題 22、】內(nèi)部排序算法比較一、問題分析和任務(wù)定義 各種內(nèi)部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時 間。試通過隨機的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。 根據(jù)對本設(shè)計任務(wù)要求的理解和分析，按以下兩點問題進行分析： 題目要求對十種排序算法進行比較，比較的主要內(nèi)容是關(guān)鍵字的比較次數(shù)和移動次數(shù)， 其中待排序數(shù)用。二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計為了實現(xiàn)十種排序算法， 產(chǎn)生的隨機數(shù)用順序表存儲

2、比較方便。 順序表數(shù)據(jù)類型 (存儲結(jié)構(gòu)) 描述如下： typedef int KeyType;struct recKeyType key;typedef rec sqlistN;2.主程序與各模塊之間的關(guān)系是：(1) void gensort(int b,int n) 起泡排序(2) void insertsort(sqlist b,int n) 插入排序(3) void so(sqlist num,int n) 折半插入排序(4) void shellsort(sqlist b,int n) 希爾排序(5) void gentsort(int b,int n) 選擇排序(6) void ou

3、tput(sqlist b,int n) 快速排序(7) void sort3(sqlist nu,int n) /2- 路插入排序(8) void Merge(sqlist a, sqlist b, int low, int mid, int high) 二路歸并排序(9) void MergePass(sqlist a, sqlist b, int n, int lenth) 一趟歸并排序(10) void MergeSort(sqlist a, int n) / 進行二路歸并(11) void sift(sqlist r,int s,int m) 堆排序(12) void init(in

4、t a)/ 隨機生成 N 個整數(shù)三、詳細設(shè)計和編碼在整個課程設(shè)計中， 要求實現(xiàn)要求的功能， 必須要有主函數(shù)， 并通過主函數(shù)調(diào)用各功能子模 塊，以上展示各個模塊的功能，以下將分析主函數(shù)和各個模塊中的具體算法和實現(xiàn)。1. 起泡排序函數(shù)的實現(xiàn)函數(shù)聲明： void gensort(int b,int n) 起泡排序的基本思想是將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進行 比較，若為逆序， 則將兩個記錄交換， 然后比較第二個記錄和第三個記錄的關(guān)鍵字。依次類推，直至第 n-1 個記錄和第 n 個記錄的關(guān)鍵字進行比較為止。起泡排 序是一種穩(wěn)定的排序方法，在隨機產(chǎn)生數(shù)的情況下，總的時間復(fù)雜度為O(n2)。2.

5、 選擇排序函數(shù)的實現(xiàn)函數(shù)聲明： void gentsort(int b,int n)選擇排序法的基本思想是：第 i 趟排序通過 n-i 次關(guān)鍵碼的比較，在 n-1+i(1 = i right ，然后再把第 i 個元素前 1 位與目標(biāo)位 置之間的所有元素后移，再把第 i 個元素放在目標(biāo)位置上。6. 快速排序函數(shù)的實現(xiàn)函數(shù)聲明： void output(sqlist b,int n)/ 輸出元素值 首先選一個軸值(即比較的基準(zhǔn)) ，將待排序記錄分割成獨立的兩部分，左 側(cè)記錄的關(guān)鍵碼均小于或等于軸值， 右側(cè)記錄的關(guān)鍵碼均大于或等于軸值， 然后 分別對這兩部分重復(fù)上述過程， 直到整個序列有序。 快速排

6、序是一種不穩(wěn)定的排序方法，時間復(fù)雜度為 O( nlog2n)7. 堆排序函數(shù)的實現(xiàn) 函數(shù)聲明： void sift(sqlist r,int s,int m) 首先將待排序的記錄序列構(gòu)造成一個堆， 此時，選出了堆中所有記錄的最大 者即堆頂記錄， 然后將它們從堆中移走 (通常將堆頂記錄和堆中最后一個記錄交 換)，并將剩余的記錄再調(diào)整成堆，這樣又找出了次大的記錄，依此類推，直到 堆中只有一個記錄為止。堆排序是一種不穩(wěn)定的排序方法，總的時間復(fù)雜度為 O(nlog2n)。8. 二路歸并排序函數(shù)的實現(xiàn)函數(shù)聲明： void Merge(sqlist a, sqlist b, int low, int mi

7、d, int high) void MergePass(sqlist a, sqlist b, int n, int lenth) void MergeSort(sqlist a, int n) 合并排序：這里的合并排序和下邊要描述的快速排序都采用了分而治之的思想， 但兩者仍然有很大差異。合并排序是將一個無序數(shù)組n1r分成兩個數(shù)組n1r/2與nr/2+1r，分別對這兩個小數(shù)組進行合并排序，然后再將這兩個數(shù) 組合并成一個大數(shù)組。 由此我們看出合并排序時一個遞歸過程 (非遞歸合并排序 這里不做討論)。合并排序的主要工作便是 “合并”，兩個小規(guī)模數(shù)組合并成大的， 兩個大的再合并成更大的，當(dāng)然元素比較

8、式在合并的過程中進行的。9.2-路插入函數(shù)的實現(xiàn) 9.2-路插入排序是在折半插入排序的基礎(chǔ)上發(fā)展。其目的是減少排序過程中 記錄移動的次數(shù)，但為此需要 n 個記錄的輔助空間。具體做法是：另設(shè)一個和 L.r同類型的數(shù)組d,首先將L.r1賦值給的d1,將d1看成是排好序的序列中處 與中間位置的記錄，然后從 L.r 中第 2 個記錄起依次插入到的 d 1 之前或之后的 有序序列中。先將待排序記錄的關(guān)鍵字和d1的關(guān)鍵字比較，若L.ri.key數(shù)_/花花結(jié)79一仃75-7 85-4亍上丁吃亍占結(jié)21序61序46排 L L運=5運=2運-6運=2運=5行-9排=2排=1的 序聲聲聲隼數(shù)運費費數(shù) 泡臭杲動當(dāng)速

9、75半動舅路tnni2結(jié)果分析實驗結(jié)果與我們對這十種種算法的性能理論分析基本吻合：插入排序與冒泡排序的時間復(fù)雜度為O(n*n)，而后三種排序算法的時間復(fù)雜度為 0(nlogn)。實驗結(jié)果 還顯示出雖然冒泡排序和插入排序的時間復(fù)雜度相同， 但插入排序的性能仍然比冒泡排序好，尤其在排序時間方面。七、參考文獻1 王昆侖，李紅 . 數(shù)據(jù)結(jié)構(gòu)與算法 . 北京：中國鐵道出版社， 2006年 5 月2王立柱，C語言與數(shù)據(jù)結(jié)構(gòu)北京：清華大學(xué)出版社，2003年6月第1版八、附錄 以上是對本設(shè)計的實現(xiàn)功能和算法等的全面分析，以下是帶注釋的源代碼算法 #include#include#include#include

10、#include#define N 100int p,q;int g=0;int h=0;/起泡排序void gensort(int b,int n)int i,j;int s=0,t=0;for(i=0;in-1;i+)for(j=i+1;jbj)int temp=bi;bi=bj;bj=temp;s+=3;cout 移動次數(shù) =s, 比較次數(shù) =tendl;/插入排序typedef int KeyType;struct recKeyType key;typedef rec sqlistN;void insertsort(sqlist b,int n)int i,j;int s=0,t=0;

11、 for(i=2;in;i+) b0.key=bi.key; s+; j=i-1; t+;while(b0.keybj.key) bj+1=bj;j-;s+;t+;bj+1=b0;s+;cout 移動次數(shù) =s, 比較次數(shù) =tendl; /折半插入排序void so(sqlist num,int n)int s=0;int low,high,m;/ 分別指向低、高、中的位置int i,j,k=0,t;/i,j 循環(huán) k 交換次數(shù) t 哨兵for(i=1;in;i+)t=numi.key ;low=0;high=i-1;while(low=high)m=(low+high)/2;if(t=hi

12、gh+1;j-)numj+1.key=numj.key;s+;numhigh+1.key=t;cout 移動次數(shù) =s, 比較次數(shù) =k0)for(i=gap+1;i0)t+;if(bj.keybj+gap.key) x=bj;bj=bj+gap; bj+gap=x;j=j-gap;s+=3;else j=0;gap=gap/2;cout 移動次數(shù) =s, 比較次數(shù) =tendl; /選擇排序void gentsort(int b,int n)int i,j,k;int s=0,t=0;for(i=0;in-1;i+)k=i;for(j=i+1;jbj)k=j;if(k!=i)int temp

13、=bk;bk=bi;bi=temp;s+=3;cout 移動次數(shù) =s, 比較次數(shù) =tendl;/快速排序void output(sqlist b,int n)/ 輸出元素值 for(int i=0;in;i+)coutsetw(4)bi.key;coutendl;void display(int n,int m)/ 輸出計數(shù)cout 移動次數(shù) =n, 比較次數(shù) =mendl; void BeforeSort()/ 初始化計數(shù)器 p=0;q=0;void quicksort(sqlist r,int s,int t)int i=s,j=t; if(st) r0=rs;p+;while(ij)

14、 p+;while(i=r0.key) j-;ri=rj;q+;p+; p+;while(ij&ri.key=r0.key) i+;rj=ri;q+;p+; ri=r0;p+; else return; quicksort(r,s,j-1); quicksort(r,j+1,t);void sort(sqlist r,int s,int t) BeforeSort();quicksort(r,s,t);display(p,q); /2-路插入排序void sort3(sqlist nu,int n)/int max=n;#define max 20int first,final;/ 頭尾指針i

15、nt cachemax+1;/ 中轉(zhuǎn)站int i,j,s=0;/i,j 循環(huán)變量 k 計數(shù)器int t=0;for(i=0;i=cachefinal)t+;final+;cachefinal=nui.key;s+;else if(nui.keycachej;)if(0=j)cachen-1=cache0;elsecachej-1=cachej;s+;j+;if(j=n)j=0;if(0=first)first=n-1;else first-;if(0=j)j=n;cachej-1=nui.key;s+;for(i=first,j=0;jn;j+)nuj.key=cachei;i+;if(i=n

16、)i=0;cout 移動次數(shù) =s, 比較次數(shù) =tendl;/二路歸并void Merge(sqlist a, sqlist b, int low, int mid, int high)int i= low, j = mid + 1,k = low; while (i = mid) & (j = high) if(ai.key = aj.key) h+;bk+ = ai+; g+;elseh+;bk+ = aj+;g+;+j;+k;/ if(i = mid)while(i = mid)bk+ = ai+;g+;/else while(j = high) bk+=aj+; g+;/進行一趟歸并

17、void MergePass(sqlist a, sqlist b, int n, int lenth) int i = 0, k=0;while(i = n - 2*lenth)Merge(a, b, i, i + lenth -1, i + 2*lenth -1); i += 2*lenth;if(i n - lenth )Merge(a, b, i, i + lenth -1, n-1);elsefor(k = i; k = n-1; k+)bk = ak;g+;/進行二路歸并void MergeSort(sqlist a, int n)sqlist b;/int* b=(int*)ma

18、lloc(n*sizeof(int); int lenth = 1; while(lenth n/2+1) MergePass(a, b,n, lenth); lenth = 2*lenth; MergePass(b, a, n, lenth); lenth = 2*lenth;cout 移動次數(shù) =g, 比較次數(shù) =hendl;/堆排序void sift(sqlist r,int s,int m) int j; rec x; x=rs;for(j=2*s;j=m;j*=2) q+;if(jm&(rj.keyrj+1.key) +j;q+;if(!(x.key0;-i)sift(r,i,m);for(i=m;i1;-i)w=ri;ri=r1;r1=w;p+=3;sift(r,1,i-1);void sorting(sqlist &r,int t)BeforeSort();heapsort(r,t); display(p,q); void init(int a)/ 隨機生成 N 個整數(shù)并 int i;/#define N 100;srand ( ( unsigned int ) time ( NULL ) );for(i=0;iN;i+)ai=rand()%99+1;