數(shù)據(jù)結(jié)構(gòu)各種排序算法的時間性能(已修改)
2025-07-07 07:23 本頁面
【正文】 HUNAN UNIVERSITY課程實習報告題 目： 排序算法的時間性能 學生姓名 學生學號 專業(yè)班級 指導老師 李曉鴻 完 成 日 期 設(shè)計一組實驗來比較下列排序算法的時間性能 快速排序、堆排序、希爾排序、冒泡排序、歸并排序(其他排序也可以作為比較的對象） 要求 (1)時間性能包括平均時間性能、最好情況下的時間性能、最差情況下的時間性能等。 (2)實驗數(shù)據(jù)應具有說服力，包括：數(shù)據(jù)要有一定的規(guī)模（如元素個數(shù)從100到10000）；數(shù)據(jù)的初始特性類型要多，因而需要具有隨機性；實驗數(shù)據(jù)的組數(shù)要多，即同一規(guī)模的數(shù)組要多選幾種不同類型的數(shù)據(jù)來實驗。實驗結(jié)果要能以清晰的形式給出，如圖、表等。 (3)算法所用時間必須是機器時間，也可以包括比較和交換元素的次數(shù)。 (4)實驗分析及其結(jié)果要能以清晰的方式來描述，如數(shù)學公式或圖表等。(5)要給出實驗的方案及其分析。說明 本題重點在以下幾個方面：理解和掌握以實驗方式比較算法性能的方法；掌握測試實驗方案的設(shè)計；理解并實現(xiàn)測試數(shù)據(jù)的產(chǎn)生方法；掌握實驗數(shù)據(jù)的分析和結(jié)論提煉；實驗結(jié)果匯報等。一、需求分析 (1) 輸入的形式和輸入值的范圍：本程序要求實現(xiàn)各種算法的時間性能的比較，由于需要比較的數(shù)目較大，不能手動輸入，于是采用系統(tǒng)生成隨機數(shù)。用戶輸入隨機數(shù)的個數(shù)n，然后調(diào)用隨機事件函數(shù)產(chǎn)生n個隨機數(shù)，對這些隨機數(shù)進行排序。于是數(shù)據(jù)為整數(shù) (2) 輸出的形式：輸出在各種數(shù)目的隨機數(shù)下，各種排序算法所用的時間和比較次數(shù)?！ ?3) 程序所能達到的功能：該程序可以根據(jù)用戶的輸入而產(chǎn)生相應的隨機數(shù)，然后對隨機數(shù)進行各種排序，根據(jù)排序進行時間和次數(shù)的比較。（4）測試數(shù)據(jù)：略二、概要設(shè)計 ADT List 數(shù)據(jù)對象 D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }數(shù)據(jù)關(guān)系 R1＝{ ai1 ,ai |ai1 ,ai∈D, i=2,...,n }基本操作 virtual void clear() = 0。 bool insert(const Elemamp。) = 0。 bool append(const Elemamp。) = 0。 lbool remove(Elemamp。) = 0。void setStart() = 0。 void setEnd() = 0。 void prev() = 0。 void next() = 0。 int leftLength() const = 0。 int rightLength() const = 0。 bool setPos(int pos) = 0。 bool getValue(Elemamp。) const = 0。 void print() const = 0。（1） 輸入模塊：輸入要排序的數(shù)的數(shù)量n（2） 處理模塊：系統(tǒng)產(chǎn)生n個隨機數(shù)，對隨機數(shù)進行排序（3） 輸出模塊：將排序的結(jié)果輸出 隨機數(shù)的產(chǎn)生：利用srand()產(chǎn)生隨機數(shù)。 快速排序：選定一記錄R，將所有其他記錄關(guān)鍵字k’與記錄R的關(guān)鍵字k比較, 若 k’k則將記錄換至R之前,若k’ k 則將記錄換至R之后，繼續(xù)對R前后兩部分記錄進行快速排序，直至排序范圍為1 插入排序：逐個處理待排序的記錄，每個新記錄與前面已排序的子序列進行比較，將它插入到子序列中正確的位置 冒泡排序：比較并交換相鄰的元素對，直到所有元素都被放到正確的地方為止。 歸并排序：將兩個或者多個有序表歸并成一個有序表 堆排序：首先將數(shù)組轉(zhuǎn)化為一個滿足堆定義的序列，然后將堆頂?shù)淖畲笤厝〕?，再將剩下的?shù)排成堆，再取堆頂數(shù)值，…。如此下去，直到堆為空。到最后結(jié)束時，就排出了一個由小到大排列的數(shù)組。三、詳細設(shè)計（1）產(chǎn)生隨機數(shù)：直接調(diào)用函數(shù)srand(),以時間作為隨機種子進行選擇，并把隨機數(shù)裝入數(shù)組中 unsigned long int *Sort::setRan(unsigned long int num){ unsigned long int *ra。 ra=(unsigned long int*)malloc(num*sizeof(unsigned long int))。 srand(time(NULL))。 for(unsigned long int m=0。mnum。m++){ ra[m]=rand()。 } coutendl。 return ra。}（2）快速排序：要實現(xiàn)快速排序首先選擇一個軸值，這里選取數(shù)組第一個為軸值。定義兩個標識low,high。high標識最后一個元素的位置，從后向前，將關(guān)鍵字與軸
化學相關(guān)推薦
鄂ICP備17016276號-1