實(shí)驗(yàn)五 內(nèi)部排序算法比較

1、內(nèi)部排序算法比較北京郵電大學(xué)05117班楊登鋒第1頁(yè)共21頁(yè)內(nèi)部排序算法比較內(nèi)部排序算法比較問(wèn)題描述問(wèn)題描述在課本中，各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階數(shù)或大概執(zhí)行時(shí)間。試通過(guò)隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受。需求分析需求分析（1）對(duì)以下5種常用的內(nèi)部排序算法進(jìn)行比較：起泡排序、直接插入排序、簡(jiǎn)單選擇排序、快速排序、希爾排序。（2）待排序表的表長(zhǎng)不小于100；其中的數(shù)據(jù)要用偽隨

2、機(jī)數(shù)函數(shù)產(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)大小的解釋。測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)由隨機(jī)數(shù)產(chǎn)生函數(shù)生成。內(nèi)部排序算法比較北京郵電大學(xué)05117班楊登鋒第3頁(yè)共21頁(yè)#ifndefst_h#definest_h#include#include#include#include#includeusingnam

3、espacestdtemplateclassSeqListpublic:SeqList(constintsize=100)~SeqList()SeqListvoidBubble()冒泡排序voidSt()插入排序voidSt()選擇排序voidQuickSt()快速排序voidShell()希爾排序voidHalfSt()折半插入排序voidMergeSt()歸并排序的非遞歸算法voidHeapSt()堆排序voidBidir()二路插