內(nèi)部排序算法對比

本文格式為Word版，下載可任意編輯——內(nèi)部排序算法對比內(nèi)部排序算法比較

班級：姓名：學(xué)號：完成日期：

題目：試通過隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。一．需求分析

1.對常用的6種內(nèi)部排序算法進(jìn)行比較：冒泡排序，直接插入排序，簡單項選擇擇排序，快速排序，希爾排序，堆排序。

2.待排序表的表長不小于100；其中的數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參與的比較次數(shù)和關(guān)鍵字的移動次數(shù)（關(guān)鍵字交換計為3次移動）

3.最終要對結(jié)果作出簡單分析，包括對各組數(shù)據(jù)得到結(jié)果波動大小的解釋。二．概要設(shè)計1.主界面設(shè)計

對六種內(nèi)部排序算法進(jìn)行比較，可通過隨機(jī)數(shù)程序產(chǎn)生幾組數(shù)，要求用戶手動輸入產(chǎn)生隨機(jī)數(shù)的個數(shù)。運(yùn)行界面如下圖：

選擇1運(yùn)行程序，選擇2退出程序2．存儲結(jié)構(gòu)設(shè)計

本程序采用順序表結(jié)構(gòu)，具體結(jié)構(gòu)定義如下：typedefstruct{

intkey;}ElemType;typedefstruct{

ElemType*elem;intlength;}SqList;

3.系統(tǒng)功能設(shè)計

1）分派內(nèi)存空間。創(chuàng)立順序表

2）利用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生隨機(jī)數(shù)，作為程序運(yùn)行的數(shù)據(jù)3）實現(xiàn)每種排序算法的功能函數(shù)三．模塊設(shè)計1.模塊設(shè)計隨機(jī)數(shù)產(chǎn)生模塊主程序模塊

排序算法模塊

2.系統(tǒng)子程序及功能設(shè)計

本系統(tǒng)共設(shè)置13個函數(shù)，其中包括主函數(shù)。各函數(shù)名及功能說明如下。1）voidaddlist(SqList}ElemType;typedefstruct{

ElemType*elem;intlength;}SqList;

2.全局變量定義

intbj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0;//記錄每種算法的比較，移動次數(shù)intn；//隨機(jī)數(shù)的個數(shù)

2.系統(tǒng)主要子程序詳細(xì)設(shè)計（1）主函數(shù)設(shè)計模塊

主要是輸入數(shù)據(jù)，以及程序界面的設(shè)計，調(diào)用系統(tǒng)的各個子程序，并輸出結(jié)果。（詳見源程序）

（2）隨機(jī)數(shù)產(chǎn)生模塊

利用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生數(shù)據(jù)，并存儲到順序表中。voidrandom(SqList

staticboolfirst=true;if(first){

srand(time(0));first=false;

}//使每次產(chǎn)生的隨機(jī)數(shù)不同for(inti=1;i30000)gotoa;++L.length;}

（3）排序算法模塊實現(xiàn)冒泡排序，直接插入排序，簡單項選擇擇排序，快速排序，希爾排序以及堆排序的算法。（祥見源程序）五．測試分析

運(yùn)行程序后，得到如下圖：

輸入：1

輸入：100

選擇1重復(fù)上述步驟，輸入150，200，250，300得到另外四個結(jié)果：

退出程序，請選擇：2

結(jié)果分析：冒泡排序，直接插入排序以及簡單項選擇擇排序比較次數(shù)較多，快速排序，希爾排序及堆排序比較次數(shù)較少；并可得冒泡排序和直接插入排序相對較穩(wěn)定，其他四種內(nèi)部排序為不穩(wěn)定排序。

六．源程序清單#include\#include\#include\#include\#include%usingnamespacestd;

#defineLIST_INIT_SIZE50000

intbj1=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)鍵字比較和移動的次數(shù)typedefstruct{

intkey;}ElemType;typedefstruct{

ElemType*elem;intlength;}SqList;

voidaddlist(SqList}

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(0);}

voidrandom(SqList

staticboolfirst=true;if(first){

srand(time(0));first=false;

}//使輸入一致個數(shù)時每次產(chǎn)生的隨機(jī)數(shù)不同for(inti=1;i30000)gotoa;++L.length;}}

voidmemory(SqListfor(inti=1;iL.elem[j+1].key){

L.elem[0].key=L.elem[j].key;L.elem[j].key=L.elem[j+1].key;L.elem[j+1].key=L.elem[0].key;yd1+=3;}}}}

voidInsertSort(SqList

for(i=2;iL.elem[j].key){k=j;bj5++;}}

if(i!=k){

L.elem[0].key=L.elem[i].key;L.elem[i].key=L.elem[k].key;L.elem[k].key=L.elem[0].key;yd5+=3;}w++;}

d=d/2;w=1;}}

voidHeapAdjust(SqList

rc.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!rc.elem)exit(0);intj;

rc.elem[0]=L.elem[s];for(j=2*s;j0;--i)HeapAdjust(L,i,L.length);for(i=L.length;i>1;--i)

{L.elem[1]=L.elem[i];yd6+=3;HeapAdjust(L,