




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、內(nèi)部排序算法比較班級(jí): 姓名: 學(xué)號(hào): 完成日期:題目:試通過(guò)隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù),以取得直觀感受。一需求分析1.對(duì)常用的6種內(nèi)部排序算法進(jìn)行比較:冒泡排序,直接插入排序,簡(jiǎn)單選擇排序,快速排序,希爾排序,堆排序。2.待排序表的表長(zhǎng)不小于100;其中的數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生;至少要用5組不同的輸入數(shù)據(jù)作比較;比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)(關(guān)鍵字交換計(jì)為3次移動(dòng))3.最后要對(duì)結(jié)果作出簡(jiǎn)單分析,包括對(duì)各組數(shù)據(jù)得到結(jié)果波動(dòng)大小的解釋。二概要設(shè)計(jì)1.主界面設(shè)計(jì)對(duì)六種內(nèi)部排序算法進(jìn)行比較,可通過(guò)隨機(jī)數(shù)程序產(chǎn)生幾組數(shù),要求用戶手動(dòng)輸入產(chǎn)生隨機(jī)數(shù)的
2、個(gè)數(shù)。運(yùn)行界面如圖所示:選擇1運(yùn)行程序,選擇2退出程序2存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)本程序采用順序表結(jié)構(gòu),具體結(jié)構(gòu)定義如下:typedef struct int key; ElemType;typedef struct ElemType *elem; int length;SqList;3.系統(tǒng)功能設(shè)計(jì)1)分配內(nèi)存空間。創(chuàng)建順序表2)利用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生隨機(jī)數(shù),作為程序運(yùn)行的數(shù)據(jù)3)實(shí)現(xiàn)每種排序算法的功能函數(shù)三模塊設(shè)計(jì)隨機(jī)數(shù)產(chǎn)生模塊1.模塊設(shè)計(jì)主程序模塊排序算法模塊2.系統(tǒng)子程序及功能設(shè)計(jì)本系統(tǒng)共設(shè)置13個(gè)函數(shù),其中包括主函數(shù)。各函數(shù)名及功能說(shuō)明如下。1) void addlist(SqList &
3、;L) /建立個(gè)空順序表2) void random(SqList &L) /隨機(jī)數(shù)產(chǎn)生函數(shù)3) void memory(SqList &M,SqList &L) /記錄L,以保證每個(gè)排序函數(shù)使用一組隨機(jī)數(shù)4) void BubbleSort(SqList &L) /冒泡排序5) void InsertSort(SqList &L) /直接插入排序6) void SelectSort(SqList &L) /選擇排序7) int Partition(SqList &L,int low,int high) /返回快速排序樞軸的位置8) vo
4、id QSort(SqList &L,int low,int high) /對(duì)子序列作快速排序9) void QuickSort(SqList &L) /對(duì)數(shù)序表作快速排序10)void ShellSort (SqList &L) /希爾排序11)void HeapAdjust(SqList &L,int s,int m )/堆排序算法子程序12)void HeapSort(SqList &L) /對(duì)順序表進(jìn)行堆排序13)void main() /主函數(shù),調(diào)用各模塊函數(shù)3.函數(shù)主要調(diào)用關(guān)系913)main()51243211068117四詳細(xì)設(shè)計(jì)1.數(shù)據(jù)
5、類型定義typedef struct int key; ElemType;typedef struct ElemType *elem; int length;SqList;2.全局變量定義int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0;/記錄每種算法的比較,移動(dòng)次數(shù)int n;/隨機(jī)數(shù)的個(gè)數(shù)2.系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)(1)主函數(shù)設(shè)計(jì)模塊主要是輸入數(shù)據(jù),以及程序界面的設(shè)計(jì),調(diào)用系統(tǒng)的各個(gè)子程序,并輸出結(jié)果。(詳見(jiàn)源程序)(2)隨機(jī)數(shù)產(chǎn)生模塊利用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生數(shù)據(jù),并存儲(chǔ)到順序表中。voi
6、d random(SqList &L) L.length=0;static bool first=true;if(first)srand(time(0);first=false;/使每次產(chǎn)生的隨機(jī)數(shù)不同for(int i=1;i<n+1;i+)a: L.elemi.key=rand(); if(L.elemi.key>30000) goto a; +L.length; (3)排序算法模塊實(shí)現(xiàn)冒泡排序,直接插入排序,簡(jiǎn)單選擇排序,快速排序,希爾排序以及堆排序的算法。(祥見(jiàn)源程序)五測(cè)試分析運(yùn)行程序后,得到如圖所示:輸入:1輸入:100選擇1重復(fù)上述步驟,輸入150,200,2
7、50,300得到另外四個(gè)結(jié)果:退出程序,請(qǐng)選擇:2結(jié)果分析:冒泡排序,直接插入排序以及簡(jiǎn)單選擇排序比較次數(shù)較多,快速排序,希爾排序及堆排序比較次數(shù)較少;并可得冒泡排序和直接插入排序相對(duì)較穩(wěn)定,其他四種內(nèi)部排序?yàn)椴环€(wěn)定排序。六源程序清單#include"iostream"#include"stdio.h"#include"stdlib.h"#include"string.h"#include"time.h"using namespace std;#define LIST_INIT_SIZE 500
8、00int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0,n;/yd,bj為記錄關(guān)鍵字比較和移動(dòng)的次數(shù)typedef struct int key; ElemType;typedef struct ElemType *elem; int length;SqList;void addlist(SqList &L)/初始化順序表a: printf("請(qǐng)輸入你要輸入的個(gè)數(shù):"); scanf("%d",&n); if(n>50000) pri
9、ntf("超出范圍重新輸入!n"); goto a; L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem)exit(0);void random(SqList &L)/隨機(jī)數(shù)產(chǎn)生程序 L.length=0;static bool first=true;if(first)srand(time(0);first=false;/使輸入相同個(gè)數(shù)時(shí)每次產(chǎn)生的隨機(jī)數(shù)不同for(int i=1;i<n+1;i+)a: L.elemi.key=rand(); if(L.elemi.key&g
10、t;30000) goto a; +L.length; void memory(SqList &M,SqList &L)/記錄L,使每個(gè)排序算法都用一組相同的隨機(jī)數(shù) M.length=0;for(int i=1;i<n+1;i+)M.elemi.key=L.elemi.key;+M.length;void BubbleSort(SqList &L)/冒泡排序int i,j;for(i=1;i<L.length;i+)for(j=1;j<L.length-i+1;j+)bj1+;if(L.elemj.key>L.elemj+1.key) L.ele
11、m0.key=L.elemj.key; L.elemj.key=L.elemj+1.key; L.elemj+1.key=L.elem0.key; yd1+=3; void InsertSort(SqList &L)/直接插入排序 int i,j; for(i=2;i<=L.length;i+) if(L.elemi.key<L.elemi-1.key) L.elem0.key=L.elemi.key; yd2+; j=i-1; bj2+; while(L.elem0.key<L.elemj.key) L.elemj+1.key=L.elemj.key; j-; yd
12、2+; bj2+; L.elemj+1.key=L.elem0.key; yd2+; void SelectSort(SqList &L)/選擇排序 int i,j,k; for(i=1;i<L.length;i+) k=i; for(j=i+1;j<L.length;j+) bj3+; if(L.elemj.key<L.elemk.key)k=j; if(i!=k) L.elem0.key=L.elemi.key; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key; yd3+=3; int Partition(SqLi
13、st &L,int low,int high)/快速排序 int pivotkey; L.elem0=L.elemlow; yd4+; pivotkey=L.elemlow.key; while (low<high) yd4+; while(low<high&&L.elemhigh.key>=pivotkey) -high; L.elemlow=L.elemhigh; bj4+; yd4+; while (low<high&&L.elemlow.key<=pivotkey) +low; L.elemhigh=L.elemlo
14、w; bj4+; yd4+; L.elemlow=L.elem0; yd4+; return low;void QSort(SqList &L,int low,int high)/對(duì)順序表的子序列作快速排序 int pivotloc; if(low<high) pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); void QuickSort(SqList &L)/對(duì)順序表L作快速排序 QSort(L,1,L.length);void ShellSort(SqL
15、ist &L)/希爾排序 int i,d=L.length/2,j,w=0,k; while(w<d) w=1; for(i=w;i<L.length;i=i+d) k=i; for(j=i+d;j<L.length;j=j+d) if(L.elemi.key>L.elemj.key) k=j; bj5+; if(i!=k) L.elem0.key=L.elemi.key; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key; yd5+=3; w+; d=d/2; w=1; void HeapAdjust(SqLis
16、t &L,int s,int m )/調(diào)整L.elems的關(guān)鍵字,使L.elems.m成為一個(gè)大根堆SqList rc; rc.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!rc.elem)exit(0);int j;rc.elem0=L.elems;for(j=2*s;j<=m;j*=2)bj6+;if(j<m&&L.elemj.key<L.elemj+1.key)+j;bj6+;if(!(rc.elem0.key<L.elemj.key) break;L.elems=L
17、.elemj;s=j;yd6+=3;L.elems=rc.elem0;void HeapSort(SqList &L)/對(duì)順序表L進(jìn)行堆排序int i;for(i=L.length/2;i>0;-i)HeapAdjust(L,i,L.length);for(i=L.length;i>1;-i)L.elem1=L.elemi;yd6+=3;HeapAdjust(L,1,i-1);void main() SqList L,M; int a; M.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!M.elem)
18、exit(0);a:cout<<" -內(nèi)部排序算法比較-n" cout<<"*歡迎使用*n"cout<<"*(1)運(yùn)行程序*n"cout<<"*(2)退出系統(tǒng)*n" cout<<endl; cout<<"請(qǐng)選擇:" scanf("%d",&a);switch(a) case 1:system("cls");addlist(L);break;case 2:cout<<"謝謝使用"exit(0);break; random(L); memory(M,L); BubbleSort(M); memory(M,L); InsertSort(M); memory(M,L); SelectSort(M); memory(M,L); QuickSort(M); memory(M,L); ShellSort(M); memory(M,L); HeapSort(L); cout<<" *比較次數(shù)*移動(dòng)次數(shù)*n" cout<<"冒泡排序:
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 手術(shù)安全核查內(nèi)容及流程
- 安全生產(chǎn)交通事故
- 國(guó)家安全生產(chǎn)監(jiān)督管理查詢網(wǎng)
- 江蘇省連云港市錦屏高級(jí)中學(xué)2025年高一物理第二學(xué)期期末預(yù)測(cè)試題含解析
- 學(xué)校安全知識(shí)培訓(xùn)記錄
- 安全生產(chǎn)事故防范措施完整版
- 園林安全事故應(yīng)急預(yù)案
- 泳池應(yīng)急救援預(yù)案
- 企業(yè)第一季度安全生產(chǎn)工作總結(jié)
- 煤礦事故隱患排查制度
- 市政設(shè)施維護(hù)服務(wù)項(xiàng)目方案
- 橫紋肌溶解癥課件
- GB/T 23806-2009精細(xì)陶瓷斷裂韌性試驗(yàn)方法單邊預(yù)裂紋梁(SEPB)法
- GB/T 23312.1-2009漆包鋁圓繞組線第1部分:一般規(guī)定
- 交通運(yùn)輸行業(yè)建設(shè)工程生產(chǎn)安全事故統(tǒng)計(jì)調(diào)查制度
- SAP聯(lián)產(chǎn)品生產(chǎn)訂單結(jié)算過(guò)程x
- 2021年呼倫貝爾農(nóng)墾集團(tuán)有限公司校園招聘筆試試題及答案解析
- 宮外孕右輸卵管妊娠腹腔鏡下盆腔粘連分解術(shù)、右輸卵管妊娠開(kāi)窗取胚術(shù)手術(shù)記錄模板
- 教科版 科學(xué)小學(xué)二年級(jí)下冊(cè)期末測(cè)試卷及參考答案(基礎(chǔ)題)
- 混凝土重力壩設(shè)計(jì)說(shuō)明書(shū)
- 弱電設(shè)備維護(hù)保養(yǎng)方案
評(píng)論
0/150
提交評(píng)論