數(shù)據(jù)結(jié)構(gòu)各種排序算法的時間性能..doc

《數(shù)據(jù)結(jié)構(gòu)各種排序算法的時間性能..doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、HUNANUNIVERSITY課程實(shí)習(xí)報告題目：排序算法的時間性能學(xué)生姓名學(xué)生學(xué)號專業(yè)班級指導(dǎo)老師李曉鴻完成日期設(shè)計一組實(shí)驗(yàn)來比較下列排序算法的時間性能快速排序、堆排序、希爾排序、冒泡排序、歸并排序(其他排序也可以作為比較的對象）要求(1)時間性能包括平均時間性能、最好情況下的時間性能、最差情況下的時間性能等。(2)實(shí)驗(yàn)數(shù)據(jù)應(yīng)具有說服力，包括：數(shù)據(jù)要有一定的規(guī)模（如元素個數(shù)從100到10000）；數(shù)據(jù)的初始特性類型要多，因而需要具有隨機(jī)性；實(shí)驗(yàn)數(shù)據(jù)的組數(shù)要多，即同一規(guī)模的數(shù)組要多選幾種不同類型的數(shù)據(jù)來實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果要能以清晰的

2、形式給出，如圖、表等。(3)算法所用時間必須是機(jī)器時間，也可以包括比較和交換元素的次數(shù)。(4)實(shí)驗(yàn)分析及其結(jié)果要能以清晰的方式來描述，如數(shù)學(xué)公式或圖表等。(5)要給出實(shí)驗(yàn)的方案及其分析。說明本題重點(diǎn)在以下幾個方面：理解和掌握以實(shí)驗(yàn)方式比較算法性能的方法；掌握測試實(shí)驗(yàn)方案的設(shè)計；理解并實(shí)現(xiàn)測試數(shù)據(jù)的產(chǎn)生方法；掌握實(shí)驗(yàn)數(shù)據(jù)的分析和結(jié)論提煉；實(shí)驗(yàn)結(jié)果匯報等。一、需求分析　　(1)輸入的形式和輸入值的范圍：本程序要求實(shí)現(xiàn)各種算法的時間性能的比較，由于需要比較的數(shù)目較大，不能手動輸入，于是采用系統(tǒng)生成隨機(jī)數(shù)。用戶輸入隨機(jī)數(shù)的個數(shù)n，然后

3、調(diào)用隨機(jī)事件函數(shù)產(chǎn)生n個隨機(jī)數(shù)，對這些隨機(jī)數(shù)進(jìn)行排序。于是數(shù)據(jù)為整數(shù)　　(2)輸出的形式：輸出在各種數(shù)目的隨機(jī)數(shù)下，各種排序算法所用的時間和比較次數(shù)?！　?3)程序所能達(dá)到的功能：該程序可以根據(jù)用戶的輸入而產(chǎn)生相應(yīng)的隨機(jī)數(shù)，然后對隨機(jī)數(shù)進(jìn)行各種排序，根據(jù)排序進(jìn)行時間和次數(shù)的比較。（4）測試數(shù)據(jù)：略二、概要設(shè)計1.抽象數(shù)據(jù)類型ADTList數(shù)據(jù)對象D＝{ai

4、ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系R1＝{

5、ai-1,ai∈D,i=2,...,n}基本操作virtualvoidclear(

6、)=0;boolinsert(constElem&)=0;boolappend(constElem&)=0;lboolremove(Elem&)=0;voidsetStart()=0;voidsetEnd()=0;voidprev()=0;voidnext()=0;intleftLength()const=0;intrightLength()const=0;boolsetPos(intpos)=0;boolgetValue(Elem&)const=0;voidprint()const=0;2.程序的流程（1）輸入模塊：輸入要排

7、序的數(shù)的數(shù)量n（2）處理模塊：系統(tǒng)產(chǎn)生n個隨機(jī)數(shù)，對隨機(jī)數(shù)進(jìn)行排序（3）輸出模塊：將排序的結(jié)果輸出3.算法的基本思想1、隨機(jī)數(shù)的產(chǎn)生：利用srand()產(chǎn)生隨機(jī)數(shù)。2、快速排序：選定一記錄R，將所有其他記錄關(guān)鍵字k’與記錄R的關(guān)鍵字k比較,若k’k則將記錄換至R之后，繼續(xù)對R前后兩部分記錄進(jìn)行快速排序，直至排序范圍為13、插入排序：逐個處理待排序的記錄，每個新記錄與前面已排序的子序列進(jìn)行比較，將它插入到子序列中正確的位置4、冒泡排序：比較并交換相鄰的元素對，直到所有元素都被放到正確的地方為止。5

8、、歸并排序：將兩個或者多個有序表歸并成一個有序表6、堆排序：首先將數(shù)組轉(zhuǎn)化為一個滿足堆定義的序列，然后將堆頂?shù)淖畲笤厝〕?，再將剩下的?shù)排成堆，再取堆頂數(shù)值，…。如此下去，直到堆為空。到最后結(jié)束時，就排出了一個由小到大排列的數(shù)組。三、詳細(xì)設(shè)計（1）產(chǎn)生隨機(jī)數(shù)：直接調(diào)用函數(shù)srand(),以時間作為隨機(jī)種子進(jìn)行選擇，并把隨機(jī)數(shù)裝入數(shù)組中unsignedlongint*Sort::setRan(unsignedlongintnum){unsignedlongint*ra;ra=(unsignedlongint*)malloc(nu

9、m*sizeof(unsignedlongint));srand(time(NULL));for(unsignedlongintm=0;m

10、gh相遇后第一趟排序結(jié)束。調(diào)整數(shù)列，軸值左邊的為比軸值小的，右邊為比軸值大的。對軸值左邊（即low到pivotkey-1的數(shù)）和右邊的子列（pivotkey+1到high的數(shù)）分別進(jìn)行上述遞歸快速排序，直到范圍為1結(jié)束。intpartition(inta[],intlow,i