數(shù)據(jù)結(jié)構(gòu)各種排序算法的時(shí)間性能-全文預(yù)覽
【正文】 組，將數(shù)組大小和柵欄置0.void clear() { delete [] listArray。 listSize = fence = 0。 thisSortNum++。 r。 thisSortNum++。 p++。 key=s[p]。 Merge(s, left, i, right)。void Sort::mergeSort(unsigned long int *s,int left,int right){ int i。} (6) 合并排序：這里的合并排序和下邊要描述的快速排序都采用了分而治之的思想，但兩者仍然有很大差異。//獲取時(shí)間Count2 d=(double)()/(double)*。 s1[1]=s1[num]。 thisheapCreat(s1,thisRanNum)。Freg)。 num=thisRanNum。num=1。 } thisSortNum=thisSortNum+2。 } else { ma=s[i]。(s[i]min(s[2*i],s[2*i+1]))) { if(s[2*i]s[2*i+1]) { ma=s[i]。依次類(lèi)推，直至最后一個(gè)節(jié)點(diǎn)輸出，此時(shí)堆排序完成。堆是一種完全二叉樹(shù)，并且根節(jié)點(diǎn)不大于左右子樹(shù)中的所有節(jié)點(diǎn)，n[i]=n[2*i]amp。//計(jì)算時(shí)間差，d的單位為ms. cout冒泡排序算法對(duì)thisRanNum個(gè)隨機(jī)數(shù)排序時(shí)間為d ms.endl。 thisSortNum++。j(thisRanNum)。 unsigned long int temp。Freg)。趟掃描可得到有序區(qū)R[1..n] void Sort::bubbleSort(unsigned long int *s){ thissetNum()。即依次比較(R[n]，R[n1])，(R[n1]，R[n2])，…，(R[2]，R[1])；對(duì)于每對(duì)氣泡(R[j+1]，R[j])，若R[j+1].keyR[j].key，則交換R[j+1]和R[j]的內(nèi)容。 }(4) 冒泡排序（bubble sort）：將被排序的記錄數(shù)組R[1..n]垂直排列，每個(gè)記錄R[i]看作是重量為R[i].key的氣泡。//獲取時(shí)間Count2 d=(double)()/(double)*。 } if(j1) thisSortNum++。amp。ithisgetRanNum()。Count1)。 LARGE_INTEGER Count1,Count2。以此類(lèi)推，到第i個(gè)元素時(shí)，前i1個(gè)元素已經(jīng)是有序的，此時(shí)只需將第i個(gè)元素插入到有序數(shù)組中并使之保持有序。 qsort(a,pivotloc+1,high)。 return low。amp。amp。對(duì)軸值左邊（即low到pivotkey1的數(shù)）和右邊的子列（pivotkey+1到high的數(shù)）分別進(jìn)行上述遞歸快速排序，直到范圍為1結(jié)束。定義兩個(gè)標(biāo)識(shí)low,high。m++){ ra[m]=rand()。 ra=(unsigned long int*)malloc(num*sizeof(unsigned long int))。 歸并排序：將兩個(gè)或者多個(gè)有序表歸并成一個(gè)有序表 堆排序：首先將數(shù)組轉(zhuǎn)化為一個(gè)滿(mǎn)足堆定義的序列，然后將堆頂?shù)淖畲笤厝〕?，再將剩下的?shù)排成堆，再取堆頂數(shù)值，…。) const = 0。 int leftLength() const = 0。void setStart() = 0。 bool append(const Elemamp?！ ?3) 程序所能達(dá)到的功能：該程序可以根據(jù)用戶(hù)的輸入而產(chǎn)生相應(yīng)的隨機(jī)數(shù)，然后對(duì)隨機(jī)數(shù)進(jìn)行各種排序，根據(jù)排序進(jìn)行時(shí)間和次數(shù)的比較。說(shuō)明 本題重點(diǎn)在以下幾個(gè)方面：理解和掌握以實(shí)驗(yàn)方式比較算法性能的方法；掌握測(cè)試實(shí)驗(yàn)方案的設(shè)計(jì)；理解并實(shí)現(xiàn)測(cè)試數(shù)據(jù)的產(chǎn)生方法；掌握實(shí)驗(yàn)數(shù)據(jù)的分析和結(jié)論提煉；實(shí)驗(yàn)結(jié)果匯報(bào)等。實(shí)驗(yàn)結(jié)果要能以清晰的形式給出，如圖、表等。 (2)實(shí)驗(yàn)數(shù)據(jù)應(yīng)具有說(shuō)服力，包括：數(shù)據(jù)要有一定的規(guī)模（如元素個(gè)數(shù)從100到10000）；數(shù)據(jù)的初始特性類(lèi)型要多，因而需要具有隨機(jī)性；實(shí)驗(yàn)數(shù)據(jù)的組數(shù)要多，即同一規(guī)模的數(shù)組要多選幾種不同類(lèi)型的數(shù)據(jù)來(lái)實(shí)驗(yàn)。(5)要給出實(shí)驗(yàn)的方案及其分析。于是數(shù)據(jù)為整數(shù) (2) 輸出的形式：輸出在各種數(shù)目的隨機(jī)數(shù)下，各種排序算法所用的時(shí)間和比較次數(shù)。) = 0。) = 0。 void next() = 0。 bool getValue(Elemamp。 快速排序：選定一記錄R，將所有其他記錄關(guān)鍵字k’與記錄R的關(guān)鍵字k比較, 若 k’k則將記錄換至R之前,若k’ k 則將記錄換至R之后，繼續(xù)對(duì)R前后兩部分記錄進(jìn)行快速排序，直至排序范圍為1 插入排序：逐個(gè)處理待排序的記錄，每個(gè)新記錄與前面已排序的子序列進(jìn)行比較，將它插入到子序列中正確的位置 冒泡排序：比較并交換相鄰的元素對(duì)，直到所有元素都被放到正確的地方為止。三、詳細(xì)設(shè)計(jì)（1）產(chǎn)生隨機(jī)數(shù)：直接調(diào)用函數(shù)srand(),以時(shí)間作為隨機(jī)種子進(jìn)行選擇，并把隨機(jī)數(shù)裝入數(shù)組中 unsigned long int *Sort::setRan(unsigned long int num){ unsigned long int *ra。mnum。}（2）快速排序：要實(shí)現(xiàn)快速排序首
化學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1