數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--內(nèi)部排序算法的比較.doc

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中國海洋大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目：內(nèi)部排序算法的比較姓名：李吉倩學(xué)號：020332010046 系年級：計(jì)算機(jī)科學(xué)與技術(shù)2010級完成時(shí)間：2012.8-2012.911數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中國海洋大學(xué)實(shí)驗(yàn)報(bào)告1、 需求分析1. 本程序?qū)σ韵铝N常用的內(nèi)部排序進(jìn)行實(shí)測比較：起泡排序、直接插入排序、簡單選擇排序、快速排序、希爾排序、堆排序。2.待排序表的元素的關(guān)鍵字為整數(shù)，雍正徐、逆序和隨機(jī)數(shù)產(chǎn)生器產(chǎn)生的隨機(jī)數(shù)做測試比較。比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換記為3次移動(dòng)）。3.程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”下，用戶可由鍵盤輸入產(chǎn)生隨機(jī)數(shù)的種子，計(jì)算機(jī)終端顯示各內(nèi)部排序的比較參數(shù)。4.最終對結(jié)果做出簡單分析，包括對各組數(shù)據(jù)得出結(jié)果波動(dòng)大小給予解釋。二、概要設(shè)計(jì)1.可排序表的抽象數(shù)據(jù)類型定義：ADT OrderableList數(shù)據(jù)對象：D = ai |ai IntegerSet,i = 1,2,n,n = 0數(shù)據(jù)關(guān)系：R1 = |ai-1,ai D.i = 2,n基本操作：SelectListType(c)操作結(jié)果：打印提示信息，請用戶選擇待排序表的類型，順序型、 逆序型還是隨機(jī)數(shù)組。BubbleSort(&L)操作結(jié)果：進(jìn)行起泡排序，返回排序后的順序表InsertSort(&L)操作結(jié)果：進(jìn)行插入排序，返回排序后的順序表SelectSort(&L)操作結(jié)果：進(jìn)行選擇排序，返回排序后的順序表QuickSort(&L)操作結(jié)果：進(jìn)行快速排序，返回排序后的順序表ShellSort(&L)操作結(jié)果：進(jìn)行希爾排序，返回排序后的順序表HeapSort(&L)操作結(jié)果：進(jìn)行堆排序，返回排序后的順序表SelectSortMethod(&L,c1)操作結(jié)果：打印提示信息，請用戶選擇排序方法，起泡排序、插入排序、選擇排序、快速排序、希爾排序還是堆排序 OutPut(L)操作結(jié)果：打印排序中關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù) ADT OrderableList2. 本程序包含兩個(gè)模塊：1）.主程序模塊 int mian()初始化； 用戶選擇待測表的類型； 輸入選擇，用switch語句判斷； While（“命令” ！= “退出”） 接受命令； 處理命令； ）可排序表單元模塊-實(shí)現(xiàn)可排序表的抽象數(shù)據(jù)類型 各模塊之間的調(diào)用關(guān)系： 主程序模塊 可排序表單元模塊三、詳細(xì)設(shè)計(jì)1.根據(jù)題目要求何可排序表的基本操作特點(diǎn)，可排序表采用證書順序表存儲結(jié)構(gòu)，并實(shí)現(xiàn)在頭文件SqList.H。/*基本操作的函數(shù)原型*#define MAXSIZE 20 /用作示例的順序表的最大長度typedef int KeyType; /定義關(guān)鍵字為整數(shù)類型typedef int InfoType; /定義其他數(shù)據(jù)項(xiàng)也為整數(shù)類型int time_key_compare = 0; /定義全局變量，關(guān)鍵字比較次int time_key_move = 0; /數(shù)和移動(dòng)次數(shù)均為0typedef structKeyType key; /關(guān)鍵字項(xiàng)InfoType otherinfo; /其他數(shù)據(jù)項(xiàng)RedType; /記錄類型typedef structRedType rMAXSIZE + 1; /r0閑置或用做哨兵int length; /順序表長度SqList; /順序表類型/*基本操作*bool LT(KeyType a,KeyType b)/比較兩個(gè)KeyType類型變量的大小time_key_compare +; /比較次數(shù)+1if(a b)return true; /,返回trueelse return false; /否則，返回false /LTvoid copyKey(RedType &a,RedType &b) /將RedType類型變量b復(fù)制給a a = b;time_key_move +; /關(guān)鍵字移動(dòng)次數(shù)+1/copyKeyvoid swap(RedType &a,RedType &b) /將RedType型變量a和b進(jìn)行交換操作RedType c; /定義RedType型變量cc = a;a = b;b = c;time_key_move += 3; /關(guān)鍵字移動(dòng)次數(shù)+3/swap/*直接插入排序*void InsertSort(SqList &L) /對順序表L做直接插入排序for(int i = 2; i = L.length; +i)if(LT(L.ri.key,L.ri - 1.key) /“”，需將L.ri插入有序子表 copyKey(L.r0 ,L.ri); /復(fù)制為哨兵copyKey(L.ri ,L.ri - 1);for(int j = i - 2;LT(L.r0.key,L.rj.key); -j) copyKey(L.rj + 1 ,L.rj); /記錄后移copyKey(L.rj + 1 ,L.r0); /插入到正確的位置/InsertSort/*希爾排序*void shellInsert(SqList &L,int dk) /對順序表L做一希爾插入排序。/1.前后記錄位置的增量式是dk，而不是1；/2.r0只是暫存單元，不是哨兵。當(dāng) j= 0時(shí)，插入位置已找到for(int i = dk + 1;i 0 & LT(L.r0.key,L.rj.key); j-= dk) copyKey(L.rj + dk ,L.rj); /記錄后移copyKey(L.rj + dk ,L.r0); /插入/ShellInsertvoid ShellSort(SqList &L,int dlta,int t) /按增量序列dlta0t - 1對順序表L作希爾排序for(int k = 0;k 1)int lastExchangeIndex = 1;for(int j = 1;j i ;j +)if(LT(L.rj + 1.key,L.rj.key) /小于成立進(jìn)行交換swap(L.rj + 1,L.rj);lastExchangeIndex = j;i = lastExchangeIndex;/BubbleSort/*簡單選擇排序*/int SelectMinKey(SqList L,int i) /在L.ri.L.length中選擇key最小的記錄 for(int j = i ;j = L.length; +j) if(LT(L.rj.key,L.ri.key)i = j;return i; /返回最小記錄下標(biāo)void SelectSort(SqList &L) /對順序表做簡單選擇排序for(int i = 1;i L.length; +i) /選擇第i小的記錄，并交換到位int j = SelectMinKey(L,i); /令j為L.ri.L.length中選擇key最小的記錄if(i != j)swap(L.rj,L.ri); /與第i記錄進(jìn)行交換/SelecteSort/*快速排序*/int Partition(SqList &L,int low,int high) /交換順序表L中字表rlowhigh的記錄，樞軸記錄到位 ，并 /返回其所在位置，此時(shí)在他之前（后）的記錄均不大（?。┡c它。 copyKey(L.r0,L.rlow);/用字表的第一個(gè)紀(jì)錄作樞軸記錄 KeyTypepivotkey=L.rlow.key; /樞軸記錄關(guān)鍵字 while(low high) /從表的兩端交替向中間掃描while(lowhigh& !LT(L.rhigh.key,pivotkey) -high; copyKey(L.rlow,L.rhigh); /將比樞軸記錄小的記錄移到低端while(lowhigh & !LT(pivotkey,L.rlow.key)+low; copyKey(L.rhigh,L.rlow); /將比樞軸記錄大的記錄移到高端 copyKey(L.rlow,L.r0); /樞軸記錄到位return low; /返回樞軸位置/Partitionvoid QSort(SqList &L,int low,int high) /對順序表L中的子序列L.rlowhigh做快速排序if(low 1int pivotloc = Partition(L,low,high); /將L.rlowhigh一分為二QSort(L,low,pivotloc - 1); /對低子表遞歸排序，pivotloc是樞軸位置QSort(L,pivotloc + 1,high); /對高子表遞歸排序/QSortvoid QuickSort(SqList &L) /對順序表L做快速排序QSort(L,1,L.length);/QuickSort/*堆排序*/void HeapAdjust(SqList &L,int s,int m) /已知L.rs.m中記錄的關(guān)鍵字除L.rs.key之外均滿足定義， /本函數(shù)調(diào)整H.rs的關(guān)鍵字，使H.rs.m成為一個(gè)大頂對RedType rc = L.rs;for(int j = 2 * s;j = m;j *= 2) /沿key較大的孩子結(jié)點(diǎn)向下帥選if(j 0;-i) /把L.r1.H.length建成大頂堆HeapAdjust(L,i,L.length);for( i = L.length;i 1; -i)swap(L.r1,L.ri); /將堆頂記錄和當(dāng)前未經(jīng)排序的子序列 / L.r1i中最后一個(gè)記錄進(jìn)行交換HeapAdjust(L,1,i - 1);/將L.r1.i-1重新調(diào)整為大頂堆/HeapSort2.主函數(shù)和其他輔助函數(shù)的偽碼算法#include /產(chǎn)生隨機(jī)數(shù)所需的庫函數(shù)/*主函數(shù)*/int main() int arryMAXSIZE + 1; /存放排序前數(shù)組 int typeChoice; /根據(jù)提示鍵入的類型選擇序號 int methodChoice; /根據(jù)提示鍵入的方法選擇序號 int seed; /用于產(chǎn)生隨機(jī)數(shù)的種子 PrintArrayMenu(); /打印選擇待排序表的類型菜單 switch(typeChoice) case 1:選擇的是順序表，初始化鏈表并打印 break;case 2:選擇的是逆序表，初始化鏈表并打印 break;case 3:選擇的是隨機(jī)數(shù)表srand(seed); /初始化隨機(jī)數(shù)，并利用rand（）產(chǎn)生隨機(jī)數(shù)并打印break;default:break; cout L.length; /打印待排序數(shù)組的長度 PrintMenu(); /打印排序方法選擇菜單 while(methodChoice!= 7) getChoice(L,choice); /根據(jù)選擇的方法堆表進(jìn)行排序操作并打印相關(guān)信息 for( j = 1;j = MAXSIZE; j +) /將鏈表恢復(fù)至未排序時(shí)狀態(tài) L.rj.key = arryj;return 0;/*根據(jù)選擇排序*/void getChoice(SqList &L,int c) /根據(jù)選擇進(jìn)行排序并輸出相關(guān)信息 int Array3 = 5,3,1; /希爾排序所需增量數(shù)組 switch(c)case 1:InsertSort(L); / 直接插入排序 outPut(L); /輸出關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)break;case 2:ShellSort(L,Array,3); /希爾排序outPut(L); /輸出關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)break;case 3:BublleSort(L); /起泡排序outPut(L); /輸出關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)break;case 4:SelectSort(L); /簡單選擇排序outPut(L); /輸出關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)break;case 5:QuickSort(L); /快速排序outPut(L); /輸出關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)break;case 6:HeapSort(L); /堆排序outPut(L); /輸出關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)break;case 7:排序結(jié)束default:break;3. 函數(shù)的調(diào)用關(guān)系圖反映了程序的層次結(jié)構(gòu) InsertSort 順序表 ShellSort 主程序 BublleSort 逆序表 getTypeChoice getMethodChoice SelectSort 隨機(jī)數(shù)表 QuickSort HeapSortsrand rand4、 排序算法結(jié)果比較測試直接插入排序希爾排序起泡排序簡單選擇排序快速排序堆排序表長順序表19/051/019/0209/0190/76121/11820逆序表209/228110/108190/570209/30200/76105/10020隨即表1134/147105/85184/345209/51105/76115/10920隨即表2106/119119/101174/261209/45114/72118/10920隨即表399/108107/84165/240209/42107/74119/11820隨即表4123/134117/98176/312209/48104/82109/10620隨即表5140/153105/85189/363209/51119/72107/10120隨即表624962887/249728725153988/514622649981281/7485866450004999/29976226064/75760235476即表725067619/250776025161759/515379949952164/7517286050004999/29964225821/76130235408即表824951520/249614935183866/517613149904576/7482456350004999/29970223755/75818235241即表925231354/252413275240599/523273249959846/7566406550004999/29982216797/75786235488即表1024940230/249502195166043/515819849952854/7479069350004999/29967210437/76844235432各種表長和測試組數(shù)進(jìn)行了測試，程序運(yùn)行正常。分析實(shí)測得到的數(shù)值，六種排序算法的特點(diǎn)小結(jié)如下