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

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

2、據(jù)排序的結(jié)果作比較。2、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)一.可能排序表的抽象數(shù)據(jù)類型定義：ADT OrderableList 數(shù)據(jù)對象：D= 七I, C IntegerSet , i=1 , 2, ,n, n>0數(shù)據(jù)關(guān)系：R1= 焦_工,出|1_1,/C D,i=2,n基本操作：InitList (n)操作結(jié)果：構(gòu)造一個(gè)長度為n,元素值依次為1, 2,，n的有序表。RandomizeList(d,isInverseOrder)操作結(jié)果：首先根據(jù)isInverseOrder 為True或False ,將表置為逆序或正序，然后將表進(jìn) 行d (0wdw8)級隨機(jī)打亂。d為0時(shí)表不打亂，d越大，打亂程度

3、越高。RecallList ()操作結(jié)果：恢復(fù)最后一次用RandomizeList隨機(jī)大亂的可排序表。ListLength ()操作結(jié)果：返回可排序的長度。ListEmpty ()操作結(jié)果：若可排序表為空表，則返回True,否則返回False。BubbleSort (&c, &s)C和移動次數(shù)SoC和移動次數(shù)SoC和移動次數(shù)SoC和移動次數(shù)SoC和移動次數(shù)SoC和移動次數(shù)So操作結(jié)果：進(jìn)行冒泡排序，返回關(guān)鍵字比較次數(shù)InsertSort(&c, &s)操作結(jié)果：進(jìn)行插入排序，返回關(guān)鍵字比較次數(shù)SelectSort(&c, &s)操作結(jié)果：進(jìn)行選擇

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

5、后比較第2個(gè)數(shù)和第3個(gè)數(shù), 將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對數(shù)開始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第 1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直 比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置 上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過程，直 至最終完成排序。2 .直接插入排序：直接插入排序是一種最簡單的排序方法，它的基本操作是將一個(gè)記錄插入到已牌號序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。3

6、.簡單選擇排序：在要排序的一組數(shù)中， 選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)。4 .希爾排序：希爾排序又稱“縮小增量排序”，它也是一種屬插入排序類的方法，但在時(shí)間效率上較前述集中排序方法有較大的改進(jìn)。它的基本思想是：先將整個(gè)待排序記錄序列分割成為若干子序 列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行一次直 接插入排序。5 .堆排序：由二叉堆的定義可知，堆頂元素（即二叉堆的根節(jié)點(diǎn)）一定為堆中的最大值或最小值，因此如果我們輸出堆頂元素后，將剩余的元素再調(diào)整為二叉堆，繼而再次輸出堆頂元素， 再將剩余的元素調(diào)整為二

7、叉堆，反復(fù)執(zhí)行該過程，這樣便可輸出一個(gè)有序序列，這個(gè)過程我們就叫 做堆排序。6 .歸并排序：歸并的含義很明顯就是將兩個(gè)或者兩個(gè)以上的有序表組合成一個(gè)新的有序表。歸并排序中一般所用到的是2-路歸并排序，即將含有 n個(gè)元素的序列看成是 n個(gè)有序的子序列，每個(gè)子 序列的長度為1,而后兩兩合并，得到n/2個(gè)長度為2或1的有序子序列，再進(jìn)行兩兩合并。直到最后由兩個(gè)有序的子序列合并成為一個(gè)長度為n的有序序列。2-路歸并的核心操作是將一維數(shù)組中前后相鄰的兩個(gè)有序序列歸并為一個(gè)有序序列。7 .快速排序：快速排序的基本實(shí)現(xiàn)思想就是將當(dāng)前待排序列分成兩個(gè)部分、一個(gè)值。一個(gè)值：就是選定出一個(gè)值作為被比較的元素。兩個(gè)

8、部分：所有比該被選定元素大的部分都去該元素的右邊，所有比被選定元素小的部分都去該元素的左邊。這樣我們就確定了該元素在這個(gè)待排序列中的位置，其實(shí)也就是我們已經(jīng)將這個(gè)元素“排好了”。8 、詳細(xì)設(shè)計(jì)和編碼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<<","

9、<<"比較次數(shù)="<<t<<endl;2 .直接插入排序：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<<"移動次數(shù)="<<s<<","<<" 比較次數(shù)="<<t<<

10、endl;3 .簡單選擇排序：void gentsort(int b,int n)(int 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<<"移動次數(shù)="<<s<<","<<"比較次數(shù)="<<t<<endl;4 .希爾排序：void shellsort(sq

11、list b,int n)int i,j,gap;rec x;int s=0,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=gapcout<<"移動次數(shù)="<<s<<","<<"比較次數(shù)="<<t<<endl;5 .堆排

12、序：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 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)

13、;void sorting(sqlist &r,int t)BeforeSort();heapsort(r,t);display(p,q);void init(int a口兒隨機(jī)生成N個(gè)整數(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 *te

14、mpArr,int start,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)/當(dāng)前我們有一個(gè)源數(shù)組，我們在比較時(shí)將這個(gè)源數(shù)組一分為二進(jìn)行比較歸并排序/*因

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

16、兩個(gè)條件都成立的條件下說明兩個(gè)子序列都沒有到頭*/while(i<=mid&&j<=end) / 當(dāng)i=mid+1或者j=end+1時(shí)說明子序列中有一個(gè)到頭了，則跳出循環(huán)if(sourceArri<=sourceArrj) /表示當(dāng)前i比較小，那么我們就將小的值賦給ktempArrk=sourceArri;k=k+1;i=i+1;elsetempArrk=sourceArrj;k=k+1;j=j+1;/*不能將k,i,j 的加1操作放在if else判斷的外面，因?yàn)槲覀冊谶M(jìn)行比較的時(shí)候，只是將下標(biāo)所指的數(shù)字小的放在左邊，將下標(biāo)所指的數(shù)字大的不動，因?yàn)槲覀冃〉南?/p>

17、標(biāo)加1后還要和剛才下標(biāo)所指的數(shù)字再次進(jìn)行比較，如果放在外面，那么我們的比較的對象不對了(因?yàn)榈拇蟮臄?shù)字的下標(biāo)加1 了，前面的一個(gè)數(shù)字沒有進(jìn)行比較)*/*當(dāng)有一個(gè)子序列到頭以后，我們就要將剩余沒到頭的子序列的剩余元素放到k的右邊，因?yàn)槭Ｓ嗟目隙ㄊ且呀?jīng)有序的，且肯定比已經(jīng)到頭的子序列的全部元素都要大的。*/while(j<=end) /i=mid+1&&因?yàn)樽筮呅蛄衖跳出循環(huán)的條件肯定是當(dāng)前i=mid+1 了，則我們移動右邊j的子序列就好了tempArrk=sourceArrj;k+;j+；while(i<=mid) /&&j=end+1則此時(shí)表示當(dāng)前跳

18、出循環(huán)的是j右邊的子序列，則我們移動左邊的i的子序列tempArrk=sourceArri;k+;i+；int m;for(m=0;m<k;m+)sourceArrstart+m=tempArrm;/*上述操作完成僅僅是完成了對一個(gè)大的序列中一部分的排列，因?yàn)槲覀兊淖龇ㄊ菍φ麄€(gè)的序列進(jìn)行二分，二分之后對子序列進(jìn)行歸并排序*/void cutTwo(int sourceArr口,int *tempArr口,int start,int end)if(start<end)int mid; /設(shè)置一個(gè)取中間的變量mid=(start+end)/2;cutTwo(sourceArr,temp

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

20、quot;比較次數(shù)="<<m<<endl;void BeforeSort()/初始化計(jì)數(shù)器p=O；q=O；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)i+；rj=ri；q+；p+；ri=rO；p+；else return;quicksort(r,s

21、,j-1);quicksort(r,j+1,t); void sort(sqlist r,int s,int t)BeforeSort();quicksort(r,s,t); display(p,q);4、上機(jī)調(diào)試過程編程過程中出現(xiàn)了各種各樣的錯(cuò)誤，如輸錯(cuò)代碼，未定義變量，數(shù)組下標(biāo)越界，產(chǎn)生隨機(jī)數(shù)據(jù)的程序不工作等等，導(dǎo)致編譯沒能通過沒有結(jié)果 .最后和組員討論，又請教一些同學(xué)，終于把 所有問題都解決掉，運(yùn)行出了結(jié)果.5、測試結(jié)果及其分析下圖是自動產(chǎn)生的五組隨機(jī)產(chǎn)生的100個(gè)數(shù)據(jù)的排序結(jié)果，由圖可知希爾排序、快速排序的關(guān)鍵字移動次數(shù)和比較次數(shù)都相對較少。起泡排序、選擇排序中關(guān)鍵字比較次數(shù)很大，起泡

22、排序、插入排序移動次數(shù)很大。這樣方便我們快捷的看出排序優(yōu)缺點(diǎn)。-Jnloi -lC ： Dn cn-Heikt-s iuid S o 七七 igf：sA :皿=ftH./oiA 桌面，®學(xué) 4tlpt后基JJtJf 序.exe*圖16?fnLLU13u 1司三廿PE%H沁 車 與.TF 另.丸月匕另電:匕一 吉吉吉.4.上口匕士口七臬卜 nw J-n-i-JJ/一 J LTKE-.- -行19行£4行盧仃0,結(jié)31- 運(yùn)-&運(yùn)-2運(yùn)=3運(yùn)=2運(yùn)=4行=9膽 序數(shù)序數(shù)序數(shù)序數(shù)序等，數(shù)數(shù) 排次蚱灰拌次蚱戮酢仄芹次后 泡動人動爾動冷速動萼序 起修選 4G 51525214

23、 54 GE6 喋 GG GG 66G7 G?= &UaJC：',Ue gch unDe5 klcpPebugCppl exeT圖244S-3 0G 二 2 9_= 4 2數(shù)數(shù)5is-=21i- 果比毛果紂果度果粒二味 結(jié)心結(jié)。結(jié)胃結(jié)匕具 行41行立行/行73行.2«: 運(yùn)4運(yùn)=2運(yùn)=9運(yùn)-2底=5刑-9組序教序露教序整數(shù)運(yùn)圖1 排監(jiān)4麓麓儀層次后 泡?累動音速動1 圖3925ES3 q1 tG匚:、Use邙Wang$hunC*esktopWEbugppljexH7 1- G好岫數(shù)次 濰器相SS6輸-J B 一丁 1 一 Jh一丁 2 一丁 L吐口 7 Z1 2 Z4

24、 61 9 .i 4 *;=1;運(yùn)4運(yùn)=2運(yùn)=6運(yùn)-2底=5刑-9組序教序瞿即序辭效運(yùn)11林監(jiān)麓麓麓儀序次后 泡T勉小成動穢抬唯侔1-787圖434 2797 S799 65Z489 1389 ?3 ' ="U5 巧Wangchun'DesktopT.口 ebutppl 6號'圖54數(shù)數(shù)51-b 4-J 2-T E-Tt-T - T 4n 1 運(yùn)W運(yùn)=2恒=9運(yùn)-2底=5刑-9組電蘋果沙果異果較-fe 結(jié)=J結(jié)心結(jié)雪小結(jié)匕具，序教序整教序,效運(yùn)贊2 井玲麓籍盜次莊次后 泡?累動看速1 出修西海苗滋先二子遂隹5LJ5G 977S 64Q 1517 19 19 S

25、S 20 22 246、用戶使用說明內(nèi)部排序算法比較用戶使用說明本系統(tǒng)采用Visual C+遮言編寫,運(yùn)用軟件工程的思想,采用面向?qū)ο蠓治觥⒃O(shè)計(jì)的方法學(xué) 完成。本程序主要用于人們比較排序算法，從直觀感受各種排序的優(yōu)缺點(diǎn)。7、參考文獻(xiàn)1嚴(yán)蔚敏，吳偉民.數(shù)據(jù)Z勾(C語言版)M.北京：清華大學(xué)出版社，1997.042嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)本題集(C語言版)M.北京：清華大學(xué)出版社，1997.043汪杰等，數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法實(shí)現(xiàn)與習(xí)題解答M.北京：人民郵電出版社，20044陳媛，何波，涂曉紅等，算法與數(shù)據(jù)結(jié)構(gòu)M.北京：清華大學(xué)出版社，20055李春葆.數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析(第二版)M.北京：清華大學(xué)出版社

26、，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=0;for(i=0;i<n-1;i+)for(j=i+1;j<n;j+)t+;if(bi>bj)int temp=bi; bi=bjbj=temp;s+=3;cout<<

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

28、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;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

29、-gap;s+=3;else j=0;gap=gap)cout<<"移動次數(shù)="<<s<<","<<"比較次數(shù)="<<t<<endl;/選擇排序void gentsort(int b,int n)(int 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<&

30、lt;"移動次數(shù)="<<s<<","<<"比較次數(shù)="<<t<<endl;/快速排序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)/輸出計(jì)數(shù)cout<<"移動次數(shù)="<<n<<","<

31、;<"比較次數(shù)="<<m<<endl;void BeforeSort()/初始化計(jì)數(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)i+；rj=ri；q+；p+；ri=rO；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&&(r