數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中國(guó)海洋大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目：內(nèi)部排序算法的比較姓名：李吉倩學(xué)號(hào)：020332010046 系年級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)2010級(jí)完成時(shí)間：2012.8-2012.911數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中國(guó)海洋大學(xué)實(shí)驗(yàn)報(bào)告1、 需求分析1. 本程序?qū)σ韵铝N常用的內(nèi)部排序進(jìn)行實(shí)測(cè)比較：起泡排序、直接插入排序、簡(jiǎn)單選擇排序、快速排序、希爾排序、堆排序。2.待排序表的元素的關(guān)鍵字為整數(shù)，雍正徐、逆序和隨機(jī)數(shù)產(chǎn)生器產(chǎn)生的隨機(jī)數(shù)做測(cè)試比較。比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換記為3次移動(dòng)）。3.程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”下，用戶可由鍵盤輸入產(chǎn)生隨機(jī)數(shù)的種子，計(jì)算機(jī)終端顯示各內(nèi)部排序的比較參數(shù)。4.最終對(duì)結(jié)果做出簡(jiǎn)單分析，包括對(duì)各組數(shù)據(jù)得出結(jié)果波動(dòng)大小給予解釋。二、概要設(shè)計(jì)1.可排序表的抽象數(shù)據(jù)類型定義：ADT OrderableList數(shù)據(jù)對(duì)象：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é)果：打印提示信息，請(qǐng)用戶選擇待排序表的類型，順序型、 逆序型還是隨機(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é)果：打印提示信息，請(qǐng)用戶選擇排序方法，起泡排序、插入排序、選擇排序、快速排序、希爾排序還是堆排序 OutPut(L)操作結(jié)果：打印排序中關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù) ADT OrderableList2. 本程序包含兩個(gè)模塊：1）.主程序模塊 int mian()初始化； 用戶選擇待測(cè)表的類型； 輸入選擇，用switch語(yǔ)句判斷； While（“命令” ！= “退出”） 接受命令； 處理命令； ）可排序表單元模塊-實(shí)現(xiàn)可排序表的抽象數(shù)據(jù)類型 各模塊之間的調(diào)用關(guān)系： 主程序模塊 可排序表單元模塊三、詳細(xì)設(shè)計(jì)1.根據(jù)題目要求何可排序表的基本操作特點(diǎn)，可排序表采用證書順序表存儲(chǔ)結(jié)構(gòu)，并實(shí)現(xiàn)在頭文件SqList.H。/*基本操作的函數(shù)原型*#define MAXSIZE 20 /用作示例的順序表的最大長(zhǎng)度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; /順序表長(zhǎng)度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) /對(duì)順序表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) /對(duì)順序表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對(duì)順序表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/*簡(jiǎn)單選擇排序*/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) /對(duì)順序表做簡(jiǎn)單選擇排序for(int i = 1;i L.length; +i) /選擇第i小的記錄，并交換到位int j = SelectMinKey(L,i); /令j為L(zhǎng).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) /對(duì)順序表L中的子序列L.rlowhigh做快速排序if(low 1int pivotloc = Partition(L,low,high); /將L.rlowhigh一分為二QSort(L,low,pivotloc - 1); /對(duì)低子表遞歸排序，pivotloc是樞軸位置QSort(L,pivotloc + 1,high); /對(duì)高子表遞歸排序/QSortvoid QuickSort(SqList &L) /對(duì)順序表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è)大頂對(duì)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ù)所需的庫(kù)函數(shù)/*主函數(shù)*/int main() int arryMAXSIZE + 1; /存放排序前數(shù)組 int typeChoice; /根據(jù)提示鍵入的類型選擇序號(hào) int methodChoice; /根據(jù)提示鍵入的方法選擇序號(hào) 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ù)組的長(zhǎng)度 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); /簡(jiǎn)單選擇排序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é)果比較測(cè)試直接插入排序希爾排序起泡排序簡(jiǎn)單選擇排序快速排序堆排序表長(zhǎng)順序表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各種表長(zhǎng)和測(cè)試組數(shù)進(jìn)行了測(cè)試，程序運(yùn)行正常。分析實(shí)測(cè)得到的數(shù)值，六種排序算法的特點(diǎn)小結(jié)如下