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

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

2、機數(shù)函數(shù)產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)（其中關(guān)鍵字交換計為3次移動）。（3）最后要對結(jié)果做出簡單分析，包括對各組數(shù)據(jù)得出結(jié)果波動大小的解釋。測試數(shù)據(jù)測試數(shù)據(jù)由隨機數(shù)產(chǎn)生函數(shù)生成。內(nèi)部排序算法比較北京郵電大學(xué)05117班楊登鋒第3頁共21頁#ifndefst_h#definest_h#include#include#include#include#includeusingnam

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