資源描述:
《實(shí)驗(yàn)五 內(nèi)部排序算法比較 》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、內(nèi)部排序算法比較北京郵電大學(xué)05117班楊登鋒內(nèi)部排序算法比較問(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ù)要用偽隨機(jī)數(shù)函數(shù)產(chǎn)生;至少要用5組不同的輸入數(shù)據(jù)作比較;比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)(其中關(guān)鍵字交換計(jì)為3次移動(dòng))。(
2、3)最后要對(duì)結(jié)果做出簡(jiǎn)單分析,包括對(duì)各組數(shù)據(jù)得出結(jié)果波動(dòng)大小的解釋。測(cè)試數(shù)據(jù)由隨機(jī)數(shù)產(chǎn)生函數(shù)生成。第21頁(yè)共21頁(yè)內(nèi)部排序算法比較北京郵電大學(xué)05117班楊登鋒實(shí)現(xiàn)關(guān)鍵主要工作是設(shè)法在已知算法中的適當(dāng)位置插入對(duì)關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)的計(jì)數(shù)操作。程序還可以考慮幾組數(shù)據(jù)的典型性;如正序、逆序和不同程度的亂序。程序的運(yùn)行圖如下程序設(shè)計(jì)如下:Sort.h:第21頁(yè)共21頁(yè)內(nèi)部排序算法比較北京郵電大學(xué)05117班楊登鋒#ifndefsort_h#definesort_h#include#include
3、ream>#include#include#includeusingnamespacestd;templateclassSeqList{public:SeqList(constintsize=100);~SeqList();SeqList&operator=(SeqList&);voidBubble();//冒泡排序voidInsertSort();//插入排序voidSelectSort();//選擇排序voidQuickSort();//快速排序v
4、oidShell();//希爾排序voidHalfInsertSort();//折半插入排序voidMergeSort();//歸并排序的非遞歸算法voidHeapSort();//堆排序voidBidirInsert();//二路插入排序voidDel();//刪除線型表里的元素intLength()const;//線形表長(zhǎng)度intFind(constT&x)const;//查找值為x的位置intInsert(T&x,inti);//將x插入位置iboolIsEmpty()const;//判空boolIsFull()co
5、nst;//判滿TGet(inti);//查找i位置的元素voidPrint();//打印T*data;//線型表的表頭指針private:intmaxsize;//線型表的最大容納元素個(gè)數(shù)intlast;//線型表表尾指針};第21頁(yè)共21頁(yè)內(nèi)部排序算法比較北京郵電大學(xué)05117班楊登鋒templateSeqList::SeqList(constintsize){assert(size>=0);//TestsastringtoseeifitisNULL,empty,orlongerthan0char
6、actersif(size>0){maxsize=size;last=0;data=newT[maxsize];if(data==NULL)cout<<"內(nèi)存申請(qǐng)錯(cuò)誤!"<SeqList::~SeqList(){delete[]data;}templateSeqList&SeqList::operator=(SeqList&s){if(s.last>0){delete[]data;maxsize=s.maxsize;last=s.la
7、st;data=newT[maxsize];for(inti=1;i<=last;i++){data[i]=s.data[i];}}return*this;}templatevoidSeqList::Bubble()第21頁(yè)共21頁(yè)內(nèi)部排序算法比較北京郵電大學(xué)05117班楊登鋒{inta=1;inti=0;//inttemp;intx=0;inty=0;while(a){a=0;for(i=1;idata[i+1]){data[0]=data[i];data
8、[i]=data[i+1];data[i+1]=data[0];a++;x+=3;}y++;}}cout<<"比較次數(shù)為:"<voidSeqList::InsertSort(){/*SeqList<