數(shù)據結構課程設計內部排序算法比較

1、 數(shù)據結構課程設計 題目：內部排序算法比較 學 院 計算機工程學院 班 級 計算1311 姓 名 學 號 成 績 指導老師 評語：一：目的1 進一步掌握和利用c語言進行程設計的能力；2 進一步理解和運用結構化程設計的思想和方法；3 學會調試一個較長程序的基本方法；4 掌握書寫程設計開發(fā)文檔的能力（書寫課程設計報告）。二：問題描述 排序是數(shù)據結構中重要的一個部分，也是在實際開發(fā)中易遇到的問題，所以研究各種排算法的時間消耗對于在實際應用當中很有必要通過分析實際結合算法的特性進行選擇和使用哪種算法可以使實際題得到更好更充分的解決！該系統(tǒng)通過對各種內部排序算法如直接插入排序，冒泡排序，簡單選擇排序，快

2、速排序，希爾排序，堆排序、二路歸并排序等，以關鍵碼的比較次數(shù)和移動次數(shù)分析其特點，并進行比較，估算每種算法的時間消耗，從而比較各種算法的優(yōu)劣和使用情況！三：基本要求（1） 從以下常用的內部排序算法至少選取5種進行比較：直接插入排序；折半折入排序；希爾排序；冒泡排序；快速排序；簡單選擇排序；堆排序；歸并排序。（2） 待排序表的表長為20000；其中的數(shù)據要用偽隨機數(shù)產生程序產生；至少要用5組不同的輸入數(shù)據作比較；比較的指標為有關鍵字參加的比較次數(shù)和關鍵字移動次數(shù)（關鍵字交換計為3次移動）。四：實驗內容 對各種內部排序算法的時間復雜度有一個比較直觀的感受，包括關鍵字比較次數(shù)和關鍵字移動次數(shù)。五：程

3、序調試與結果第一組數(shù)據：5個隨機產生數(shù) 第二組數(shù)據：10個手動輸入第三組數(shù)據 ： 8個隨機產生第四組數(shù)據：50個隨機產生數(shù)第五組數(shù)據：25個手動輸入數(shù)六：調試分析（一）時間估算排序方法平均時間復雜度最好時間復雜度最壞時間復雜度直接插入排序o(n2)o(n)o(n2) 簡單選擇排序o(n2)o(n)o(n2)冒泡排序o(n2)o(n)o(n2)堆排序o(nlog2 n)o(nlog2 n)o(nlog2 n)歸并排序o(nlog2 n) o(nlog2 n)o(nlog2 n)快速排序o(nlog2 n)o(nlog2 n)o(nlog2 n)希爾排序o(n3/2)o(nlogn)o(n2)（2

4、） 影響排序的因素1：待排序的記錄數(shù)目n 的大??；2：記錄本身數(shù)據量的大小，也就是記錄中除關鍵字外的其他信息量的大??；3：關鍵字的結構及其分布情況；4：對排序穩(wěn)定性的要求。（3） 分析 對于一般的排序，比較次數(shù)多，而交換次數(shù)相對較少；而快速排序比較次數(shù)和交換次數(shù)都較少，兩者相差不如前者大。其中冒泡排序比較和交換次數(shù)都很大。七：數(shù)據結構 typedef struct int key; datatype; extern datatype rmaxnum;/定義結構體數(shù)組八：總結與體會 老實說，通過這一星期對數(shù)據結構的課程設計我對數(shù)據排序這章的理解加深了很多,也讓我對編程更加的熱愛，更感興趣了。當一

5、個程序從你手中成功時，那種愉悅是無法形容的。不過慚愧的是程序并不是我自己完完全全獨立編出來的，期間借助了同學的幫助及查詢了一些資料。九：源程序清單（主要代碼） #include #include #include#define maxnum 20000extern long cnmaxnum,mnmaxnum;typedef struct int key; datatype;extern datatype rmaxnum;/定義結構體數(shù)組void d_insertsort(datatype r,int n);/直接插入排序 void select_sort(datatype r,int n);

6、/簡單選擇排序 void bubble_sort(datatype r,long n);/冒泡排序 void heapadjust(datatype r,long s,long t);/堆排序 void heapsort(datatype r,int n);void merge(datatype r,datatype r1,long s,long m,long t);/歸并排序 void msort(datatype r,datatype r1,long s,long t);void mergesort(datatype r,datatype r1,int n);long partition(

7、datatype r,long low,long high);/快速排序 void quick_sort(datatype r,long s,long t);void shellinsert(datatype r,int gap,int n);/希爾排序 void shellsort(datatype r, int n);void prin(datatype r,long n);#includexu.hlong cnmaxnum,mnmaxnum;datatype rmaxnum;/直接插入排序：void d_insertsort(datatype r,int n)int i,j;for(i=

8、2;i=n;i+)cn0+;if(ri.keyri-1.key)r0=ri;mn0+;for(j=i-1;r0.keyrj.key;j-)rj+1=rj;mn0+;cn0+;cn0+;rj+1=r0; mn0+;/簡單選擇排序void select_sort(datatype r,int n)/k記錄第一次比較結果最小的下標int i,j,k;for(i=1;in;i+)k=i;for(j=i+1;j=n;j+)cn1+;if(rj.keyrk.key)k=j;if(i!=k)r0=rk;rk=ri;ri=r0;mn1+=3;/冒泡排序void bubble_sort(datatype r,l

9、ong n)long i,j;for(i=1;in-1;i+)for(j=2;j=n-i+1;j+)cn2+;if(rj.keyrj-1.key)r0=rj;rj=rj-1;rj-1=r0;mn2+=3;/堆排序void heapadjust(datatype r,long s,long t)datatype rc;long i,j;rc=rs;i=s;for(j=2*i;j=t;j=2*j)cn3+;if(jt&rj.keyrj.key)break;ri=rj;mn3+;i=j;ri=rc;mn3+;void heapsort(datatype r,int n)int i;for(i=n/2

10、;i0;i-)heapadjust(r,i,n);for(i=n;i1;i-)r0=r1;r1=ri;ri=r0;mn3+=3;heapadjust(r,1,i-1);/歸并排序void merge(datatype r,datatype r1,long s,long m,long t)long i,j,k;i=s; j=m+1; k=s;while(i=m&j=t)cn4+;if(ri.keyrj.key)r1k+=ri+;mn4+;elser1k+=rj+;mn4+;while(i=m)r1k+=ri+;mn4+;while(j=t)r1k+=rj+;mn4+;void msort(dat

11、atype r,datatype r1,long s,long t)long m;datatype r2maxnum;if(s=t)r1s=rs;mn4+;elsem=(s+t)/2;msort(r,r2,s,m);msort(r,r2,m+1,t);merge(r2,r1,s,m,t);void mergesort(datatype r,datatype r1,int n)msort(r,r,1,n);/快速排序long partition(datatype r,long low,long high)r0=rlow;mn5+;while(lowhigh)while(low=r0.key)cn

12、5+;high-;if(lowhigh)rlow.key=rhigh.key;mn5+;low+;while(lowhigh&rlow.key=r0.key)cn5+; low+;if(lowhigh)rhigh.key=rlow.key;mn5+; high-;rlow=r0;mn5+;return low;void quick_sort(datatype r,long s,long t)long i;if(st)i=partition(r,s,t);quick_sort(r,s,i-1);quick_sort(r,i+1,t);/希爾排序void shellinsert(datatype

13、r,int gap,int n)int i, j;for (i = gap + 1; i = n; i+)if (ri.key0 & r0.keyrj.key; j = j - gap)rj + gap = rj;mn6+;cn6+;rj + gap = r0;mn6+;void shellsort(datatype r, int n)int gaps = 5, 3, 1 ;int k;for (k = 0; k3; +k)shellinsert(r, gapsk, n);void prin(datatype r,long n)/結果輸出函數(shù) long i;printf(排序的結果為：);fo

14、r(i=1;i20000)printf(超出輸入個數(shù)范圍，請重新輸入！n);goto a;printf(請選擇輸入方式，1.手動輸入 2.電腦產生隨機數(shù)：);scanf(%d,&k);if(k=1) for(i=1;in+1;i+)scanf(%d,&ri.key);else srand(int)time(0);for(i=1;in+1;i+) ri.key=rand();printf(排序前元素順序為：);for(i=1;in+1;i+)printf(%d ,ri.key);printf(n);for(i=1;i=n;i+)r3i.key=ri.key;r4i.key=ri.key;r5i.

15、key=ri.key;r6i.key=ri.key;r7i.key=ri.key;r8i.key=ri.key;printf(排序前的序列為：);for(i=1;i=n;i+)printf(%d ,ri);shellsort(r,n);/希爾排序d_insertsort(r3,n);/直接插入排序 select_sort(r4,n);/簡單選擇排序bubble_sort(r5,n);/冒泡排序heapsort(r6,n);/堆排序mergesort(r7,r2,n);/歸并排序quick_sort(r8,1,n);/快速排序printf(n*比較結果*n);printf(n 排序方式 比較次數(shù) 移動次數(shù)n);printf(n 直接插入排序 %d %d n,cn0,mn0);prin(r3,n);printf(n 簡單選擇 %d %d n,cn1