內(nèi)部排序算法比較課程設(shè)計報告(7種基本排序)

1、合肥學(xué)院計算機科學(xué)與技術(shù)系課程設(shè)計報告2017 2018 學(xué)年第一學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計名稱內(nèi)部排序算法比較學(xué)生姓名操彥 學(xué)號1504012027 專業(yè)班級計算機科學(xué)與技術(shù)系15級 2 班指導(dǎo)教師2017 年 9 月1、問題分析和任務(wù)定義各種內(nèi)部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間，存在一定的卻缺陷。我們將通過隨機的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。所設(shè)計的程序應(yīng)能夠?qū)a(chǎn)生的隨機數(shù)據(jù)同時用不同的內(nèi)部排序算法排序，并列出關(guān)鍵字比較次數(shù)與移動次數(shù)，方便比較。待排序表的表長不少于100，為方便起見，我們令表長等于100，用5組隨

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

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

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

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

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

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

8、排序列中的位置，其實也就是我們已經(jīng)將這個元素“排好了”。3、 詳細設(shè)計和編碼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<<"移動次數(shù)="<<s<<","<<"比較次數(shù)="<<t<<endl;2.直接插入排序：v

9、oid 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<<"移動次數(shù)="<<s<<","<<"比較次數(shù)="<<t<<endl;3.簡單選擇排序：void gentsort(int b,int n)int i,j,k;

10、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<<"移動次數(shù)="<<s<<","<<"比較次數(shù)="<<t<<endl;4.希爾排序：void shellsort(sqlist b,int n)int i,j,gap;rec x;int s=0,t=0;ga

11、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<<"移動次數(shù)="<<s<<","<<"比較次數(shù)="<<t<<endl;5.堆排序：void sift(sqlist r,int s,int m

12、)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個整數(shù)并 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,int m

14、id,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) /當前我們有一個源數(shù)組，我們在比較時將這個源數(shù)組一分為二進行比較歸并排序 /* 因為我們要進行歸

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

16、這兩個條件都成立的條件下說明兩個子序列都沒有到頭 */ while(i<=mid&&j<=end) /當i=mid+1或者j=end+1時說明子序列中有一個到頭了，則跳出循環(huán) 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判斷的外面，因為我們在進行比較的時候，只是將下標所指的數(shù)字小的放在左邊，將下標所指的數(shù)字

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

18、amp;&j=end+1 則此時表示當前跳出循環(huán)的是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; /設(shè)置一個取中間的變量 mid=(

19、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)/輸出計數(shù)cout<<"移動次數(shù)="

20、;<<n<<","<<"比較次數(shù)="<<m<<endl;void BeforeSort()/初始化計數(shù)器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<=r0.key

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

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

23、經(jīng)典算法實現(xiàn)與習(xí)題解答M. 北京：人民郵電出版社，20044 陳媛，何波，涂曉紅等，算法與數(shù)據(jù)結(jié)構(gòu)M. 北京：清華大學(xué)出版社，20055李春葆.數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析(第二版) M.北京：清華大學(xué)出版社，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 s=0,t

24、=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<<"移動次數(shù)="<<s<<","<<"比較次數(shù)="<<t<<endl;/插入排序typedef int KeyType;struct rec KeyType key;typedef rec sqlistN;void insertsort(sqlist b,int

25、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<<"移動次數(shù)="<<s<<","<<"比較次數(shù)="<<t<<endl;/希爾排序void shellsort(sqlist b,int n)int i,j,gap;rec x;int s=0,t=0;gap=n/2;

26、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<<"移動次數(shù)="<<s<<","<<"比較次數(shù)="<<t<<endl;/選擇排序 void gentsort(int b,int n)int i,j,k;

27、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<<"移動次數(shù)="<<s<<","<<"比較次數(shù)="<<t<<endl;/快速排序void output(sqlist b,int n)/輸出元素值for(int i=0;i<n;i+) cout<

28、<setw(4)<<bi.key;cout<<endl;void display(int n,int m)/輸出計數(shù)cout<<"移動次數(shù)="<<n<<","<<"比較次數(shù)="<<m<<endl;void BeforeSort()/初始化計數(shù)器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+; wh

29、ile(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