1、合肥學院計算機科學與技術系課程設計報告2017 2018 學年第一學期課程 數據結構與算法課程設計名稱內部排序算法比較學生姓名操彥 學號1504012027 專業班級計算機科學與技術系15級 2 班1 / 28指導教師2017 年 9 月1、問題分析和任務定義各種內部排序算法的時間復雜度分析結果只給出了算法執行時間的階，或大概執行時間，存在一定的卻缺陷。我們將通過隨機的數據比較各算法的關鍵字比較次數和關鍵字移動次數，以取得直觀感受。所設計的程序應能夠將產生的隨機數據同時用不同的內部排序算法排序，并列出關鍵字比較次數與移動次數，方便比較。待排序表的表長不少于100，為方便起見，我們令表長等于10

2、0，用5組隨機的數據排序的結果作比較。2、 數據結構的選擇和概要設計一可能排序表的抽象數據類型定義：ADT OrderableList數據對象：D=|IntegerSet，i=1，2，n，n0數據關系：R1=<,|,D,i=2,n基本操作：InitList（n）操作結果：構造一個長度為n，元素值依次為1，2，n的有序表。RandomizeList(d,isInverseOrder)操作結果：首先根據isInverseOrder為True或False，將表置為逆序或正序，然后將表進行d（0d8）級隨機打亂。d為0時表不打亂，d越大，打亂程度越高。RecallList（）操作結果：恢復最后一

3、次用RandomizeList隨機大亂的可排序表。ListLength（）操作結果：返回可排序的長度。ListEmpty（）操作結果：若可排序表為空表，則返回True，否則返回False。BubbleSort（&c，&s）操作結果：進行冒泡排序，返回關鍵字比較次數c和移動次數s。InsertSort（&c，&s）操作結果：進行插入排序，返回關鍵字比較次數c和移動次數s。SelectSort（&c，&s）操作結果：進行選擇排序，返回關鍵字比較次數c和移動次數s。QuickSort（&c，&s）操作結果：進行快速排序，返回關鍵字比較次

4、數c和移動次數s。ShellSort（&c，&s）操作結果：進行希爾排序，返回關鍵字比較次數c和移動次數s。HeapSort（&c，&s）操作結果：進行堆排序，返回關鍵字比較次數c和移動次數s。ListTraveres（visit()）操作結果：依次對L中的每個元素調用函數visit（）。ADT OrderableList二概要設計：1.冒泡排序：冒泡排序的基本概念是：依次比較相鄰的兩個數，將小數放在前面，大數放在后面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放后。然后比較第2個數和第3個數，將小數放前，大數放后，如此繼續，直至比較最后兩個數，將小

5、數放前，大數放后。至此第一趟結束，將最大的數放到了最后。在第二趟：仍從第一對數開始比較（因為可能由于第2個數和第3個數的交換，使得第1個數不再小于第2個數），將小數放前，大數放后，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數（其實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。2.直接插入排序：直接插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄插入到已牌號序的有序表中，從而得到一個新的、記錄數增1的有序表。3. 簡單選擇排序：在要排序的一組數中，選出最小的一個數與第一個位置的數交換；然后在剩下的數當中再

6、找最小的與第二個位置的數交換，如此循環。4. 希爾排序：希爾排序又稱“縮小增量排序”，它也是一種屬插入排序類的方法，但在時間效率上較前述集中排序方法有較大的改進。它的基本思想是：先將整個待排序記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。5. 堆排序：由二叉堆的定義可知，堆頂元素（即二叉堆的根節點）一定為堆中的最大值或最小值，因此如果我們輸出堆頂元素后，將剩余的元素再調整為二叉堆，繼而再次輸出堆頂元素，再將剩余的元素調整為二叉堆，反復執行該過程，這樣便可輸出一個有序序列，這個過程我們就叫做堆排序。6. 歸并排序：歸并的含義很

7、明顯就是將兩個或者兩個以上的有序表組合成一個新的有序表。歸并排序中一般所用到的是2-路歸并排序，即將含有n個元素的序列看成是n個有序的子序列，每個子序列的長度為1，而后兩兩合并，得到n/2個長度為2或1的有序子序列，再進行兩兩合并。直到最后由兩個有序的子序列合并成為一個長度為n的有序序列。2-路歸并的核心操作是將一維數組中前后相鄰的兩個有序序列歸并為一個有序序列。7. 快速排序：快速排序的基本實現思想就是將當前待排序列分成兩個部分、一個值。一個值：就是選定出一個值作為被比較的元素。兩個部分：所有比該被選定元素大的部分都去該元素的右邊，所有比被選定元素小的部分都去該元素的左邊。這樣我們就確定了該

8、元素在這個待排序列中的位置，其實也就是我們已經將這個元素“排好了”。3、 詳細設計和編碼1.冒泡排序：void gensort(int b,int n)int i,j;int s=0,t=0;for(i=0;i<n-1;i+) for(j=i+1;j<n;j+) t+; if(bi>bj) int temp=bi; bi=bj; bj=temp; s+=3; cout<<"移動次數="<<s<<","<<"比較次數="<<t<<endl;2.直接

9、插入排序：void insertsort(sqlist b,int n)int i,j;int s=0,t=0;for(i=2;i<n;i+) b0=bi; s+; j=i-1; t+; while(b0.key<bj.key) bj+1=bj; j-; s+; t+; bj+1=b0; s+; cout<<"移動次數="<<s<<","<<"比較次數="<<t<<endl;3.簡單選擇排序：void gentsort(int b,int n)int

10、i,j,k;int s=0,t=0;for(i=0;i<n-1;i+) k=i; for(j=i+1;j<n;j+) t+; if(bk>bj) k=j; if(k!=i) int temp=bk; bk=bi; bi=temp; s+=3; cout<<"移動次數="<<s<<","<<"比較次數="<<t<<endl;4.希爾排序：void shellsort(sqlist b,int n)int i,j,gap;rec x;int s=0,

11、t=0;gap=n/2;while(gap>0) for(i=gap+1;i<n;i+) j=i-gap; while(j>0) t+; if(bj.key>bj+gap.key) x=bj;bj=bj+gap; bj+gap=x;j=j-gap; s+=3; else j=0; gap=gap/2; cout<<"移動次數="<<s<<","<<"比較次數="<<t<<endl;5.堆排序：void sift(sqlist r,int s

12、,int m)int j;rec x;x=rs;for(j=2*s;j<=m;j*=2)q+;if(j<m&&(rj.key<rj+1.key) +j;q+;if(!(x.key<rj.key) break;rs=rj;s=j;p+;rs=x;p+;void heapsort(sqlist &r,int m)int i;rec w;for(i=m/2;i>0;-i) sift(r,i,m);for(i=m;i>1;-i) w=ri;ri=r1; r1=w; p+=3; sift(r,1,i-1);void sorting(sqlist

13、 &r,int t)BeforeSort();heapsort(r,t);display(p,q);void init(int a)/隨機生成N個整數并 int i; srand ( ( unsigned int ) time ( NULL ) ); for(i=0;i<N;i+) ai=rand()%99+1;6.歸并排序：#include <stdio.h>void cutTwo(int sourceArr,int *tempArr,int start,int end);void merge(int sourceArr,int *tempArr,int start

14、,int mid,int end);int main(int argc, char *argv) int a8= 50, 10, 20, 30, 70, 40, 80, 60 ; int *b8= ; int i; cutTwo(a,b,0,8); for(i=0;i<8;i+) printf("%d ",ai); return 0;/*歸并排序算法： */void merge(int sourceArr,int *tempArr,int start,int mid,int end) /當前我們有一個源數組，我們在比較時將這個源數組一分為二進行比較歸并排序 /* 因為

15、我們要進行歸并排序，所以我們需要兩個指針分別指向兩個子序列的開始位置，即start指向左邊部分的開始位置， mid+1指向右邊部分的開始位置，我們還需要一個k的下標，用于存儲我們交換過來的數組到臨時數組tempArr */ int i=start; /定義一個i下標，用于表示左邊部分開始的位置下標 int j=mid+1; /定義一個j下標，用于表示右邊部分開始的位置下標 int k=0; /* 因為我們在比較時是不斷的比較，直到一個子序列到達最后，所以我們應該用while循環來做，結束條件：無非就是左邊序列到頭了 或者是右邊序列到頭了，即：i<=mid&&j<=e

16、nd 只有在這兩個條件都成立的條件下說明兩個子序列都沒有到頭 */ while(i<=mid&&j<=end) /當i=mid+1或者j=end+1時說明子序列中有一個到頭了，則跳出循環 if(sourceArri<=sourceArrj) /表示當前i比較小，那么我們就將小的值賦給k tempArrk=sourceArri; k=k+1; i=i+1; else tempArrk=sourceArrj; k=k+1; j=j+1; /* 不能將k,i,j的加1操作放在if else判斷的外面，因為我們在進行比較的時候，只是將下標所指的數字小的放在左邊，將下標

17、所指的數字 大的不動，因為我們小的下標加1后還要和剛才下標所指的數字再次進行比較，如果放在外面，那么我們的比較的對象不對了（ 因為的大的數字的下標加1了，前面的一個數字沒有進行比較） */ /* 當有一個子序列到頭以后，我們就要將剩余沒到頭的子序列的剩余元素放到k的右邊，因為剩余的肯定是已經有序的，且肯定比已經 到頭的子序列的全部元素都要大的。 */ while(j<=end) /i=mid+1&& 因為左邊序列i跳出循環的條件肯定是當前i=mid+1了，則我們移動右邊j的子序列就好了 tempArrk=sourceArrj; k+; j+; while(i<=mi

18、d) / &&j=end+1 則此時表示當前跳出循環的是j右邊的子序列，則我們移動左邊的i的子序列 tempArrk=sourceArri; k+; i+; int m; for(m=0;m<k;m+) sourceArrstart+m=tempArrm; /*上述操作完成僅僅是完成了對一個大的序列中一部分的排列，因為我們的做法是對整個的序列進行二分，二分之后對子序列進行歸并排序 */void cutTwo(int sourceArr,int *tempArr,int start,int end) if(start<end) int mid; /設置一個取中間的變量

19、 mid=(start+end)/2; cutTwo(sourceArr,tempArr,start,mid); cutTwo(sourceArr,tempArr,mid+1,end); merge(sourceArr,tempArr,start,mid,end); 7.快速排序：void output(sqlist b,int n)/輸出元素值for(int i=0;i<n;i+) cout<<setw(4)<<bi.key;cout<<endl;void display(int n,int m)/輸出計數cout<<"移動次數

20、="<<n<<","<<"比較次數="<<m<<endl;void BeforeSort()/初始化計數器p=0;q=0;void quicksort(sqlist r,int s,int t)int i=s,j=t;if(s<t) r0=rs;p+; while(i<j) p+; while(i<j&&rj.key>=r0.key) j-; ri=rj; q+; p+; p+; while(i<j&&ri.key<=

21、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);4、 上機調試過程編程過程中出現了各種各樣的錯誤,如輸錯代碼,未定義變量,數組下標越界,產生隨機數據的程序不工作等等,導致編譯沒能通過沒有結果.最后和組員討論,又請教一些同學,終于把所有問題都解決掉,運行出了結果.5、 測試結果及其分析下圖是自動產生的五組隨機產生的100個數據的

22、排序結果，由圖可知希爾排序、快速排序的關鍵字移動次數和比較次數都相對較少。起泡排序、選擇排序中關鍵字比較次數很大，起泡排序、插入排序移動次數很大。這樣方便我們快捷的看出排序優缺點。圖1圖2圖3圖4圖56、 用戶使用說明內部排序算法比較用戶使用說明本系統采用Visual C+語言編寫,運用軟件工程的思想, 采用面向對象分析、設計的方法學完成。本程序主要用于人們比較排序算法，從直觀感受各種排序的優缺點。7、 參考文獻1 嚴蔚敏，吳偉民. 數據結構(C語言版) M. 北京：清華大學出版社，1997.042 嚴蔚敏，吳偉民. 數據結構題集(C語言版) M. 北京：清華大學出版社，1997.043 汪杰

23、等，數據結構經典算法實現與習題解答M. 北京：人民郵電出版社，20044 陳媛，何波，涂曉紅等，算法與數據結構M. 北京：清華大學出版社，20055李春葆.數據結構習題與解析(第二版) M.北京：清華大學出版社，2004.078、 附錄#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include<stdio.h>#include<time.h>#define N 100int p,q;/起泡排序void gensort(int b,int n)int i,j;int

24、 s=0,t=0;for(i=0;i<n-1;i+) for(j=i+1;j<n;j+) t+; if(bi>bj) int temp=bi; bi=bj; bj=temp; s+=3; cout<<"移動次數="<<s<<","<<"比較次數="<<t<<endl;/插入排序typedef int KeyType;struct rec KeyType key;typedef rec sqlistN;void insertsort(sqlist

25、b,int n)int i,j;int s=0,t=0;for(i=2;i<n;i+) b0=bi; s+; j=i-1; t+; while(b0.key<bj.key) bj+1=bj; j-; s+; t+; bj+1=b0; s+; cout<<"移動次數="<<s<<","<<"比較次數="<<t<<endl;/希爾排序void shellsort(sqlist b,int n)int i,j,gap;rec x;int s=0,t=0;ga

26、p=n/2;while(gap>0) for(i=gap+1;i<n;i+) j=i-gap; while(j>0) t+; if(bj.key>bj+gap.key) x=bj;bj=bj+gap; bj+gap=x;j=j-gap; s+=3; else j=0; gap=gap/2; cout<<"移動次數="<<s<<","<<"比較次數="<<t<<endl;/選擇排序 void gentsort(int b,int n)int

27、i,j,k;int s=0,t=0;for(i=0;i<n-1;i+) k=i; for(j=i+1;j<n;j+) t+; if(bk>bj) k=j; if(k!=i) int temp=bk; bk=bi; bi=temp; s+=3; cout<<"移動次數="<<s<<","<<"比較次數="<<t<<endl;/快速排序void output(sqlist b,int n)/輸出元素值for(int i=0;i<n;i+) co

28、ut<<setw(4)<<bi.key;cout<<endl;void display(int n,int m)/輸出計數cout<<"移動次數="<<n<<","<<"比較次數="<<m<<endl;void BeforeSort()/初始化計數器p=0;q=0;void quicksort(sqlist r,int s,int t)int i=s,j=t;if(s<t) r0=rs;p+; while(i<j)

29、p+; while(i<j&&rj.key>=r0.key) j-; ri=rj; q+; p+; p+; while(i<j&&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);/堆排序void sift(sqlist r,int s,int m)int j;rec x;x=rs;for(j=2*s;j<=m;j*=2)q+;if(j<m&&(rj.key<rj+1.key) +j;q+;if(!(x.key<rj.key) break;rs=rj;s=j;p+;rs=x;p+;void