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

HUNAN UNIVERSITY課程實習報告題 目： 排序算法的時間性能 學生姓名 學生學號 專業(yè)班級 指導老師 李曉鴻 完 成 日 期 設計一組實驗來比較下列排序算法的時間性能 快速排序、堆排序、希爾排序、冒泡排序、歸并排序(其他排序也可以作為比較的對象） 要求 (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)要給出實驗的方案及其分析。說明 本題重點在以下幾個方面：理解和掌握以實驗方式比較算法性能的方法；掌握測試實驗方案的設計；理解并實現(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ù)：略二、概要設計1.抽象數(shù)據(jù)類型ADT List 數(shù)據(jù)對象 D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關系 R1 |ai-1 ,aiD, i=2,.,n 基本操作 virtual void clear() = 0; bool insert(const Elem&) = 0; bool append(const Elem&) = 0; lbool remove(Elem&) = 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(Elem&) const = 0; void print() const = 0;2.程序的流程（1） 輸入模塊：輸入要排序的數(shù)的數(shù)量n（2） 處理模塊：系統(tǒng)產(chǎn)生n個隨機數(shù)，對隨機數(shù)進行排序（3） 輸出模塊：將排序的結(jié)果輸出3.算法的基本思想1、 隨機數(shù)的產(chǎn)生：利用srand()產(chǎn)生隨機數(shù)。2、 快速排序：選定一記錄R，將所有其他記錄關鍵字k與記錄R的關鍵字k比較, 若 kk 則將記錄換至R之后，繼續(xù)對R前后兩部分記錄進行快速排序，直至排序范圍為13、 插入排序：逐個處理待排序的記錄，每個新記錄與前面已排序的子序列進行比較，將它插入到子序列中正確的位置4、 冒泡排序：比較并交換相鄰的元素對，直到所有元素都被放到正確的地方為止。5、 歸并排序：將兩個或者多個有序表歸并成一個有序表6、 堆排序：首先將數(shù)組轉(zhuǎn)化為一個滿足堆定義的序列，然后將堆頂?shù)淖畲笤厝〕觯賹⑹Ｏ碌臄?shù)排成堆，再取堆頂數(shù)值，。如此下去，直到堆為空。到最后結(jié)束時，就排出了一個由小到大排列的數(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+)ram=rand();coutendl;return ra;（2）快速排序：要實現(xiàn)快速排序首先選擇一個軸值，這里選取數(shù)組第一個為軸值。定義兩個標識low,high。high標識最后一個元素的位置，從后向前，將關鍵字與軸值比較，直至遇到小于軸值的關鍵字，前移，low標識在第二個元素的位置，從前向后，將關鍵字與軸值比較，直至遇到大于軸值的關鍵字，后移。當low,high相遇后第一趟排序結(jié)束。調(diào)整數(shù)列，軸值左邊的為比軸值小的，右邊為比軸值大的。對軸值左邊（即low到pivotkey-1的數(shù)）和右邊的子列（pivotkey+1到high的數(shù)）分別進行上述遞歸快速排序，直到范圍為1結(jié)束。int partition(int a,int low,int high)/快速排序中的一趟 int pivotkey; /作為樞軸來使用 pivotkey=alow; while(lowhigh) while(low=pivotkey) -high; alow=ahigh; while(lowhigh&alow=pivotkey) +low; ahigh=alow; alow=pivotkey; return low;void qsort(int a,int low,int high)/快速排序的遞歸形式 int pivotloc; if(lowsetNum();LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/獲取時間Count1double d;int temp,j;for (unsigned long int i=0;igetRanNum();i+)j=i;temp=si;while (j=1 & tempSortNum+;if(j1)this-SortNum+;sj=temp;QueryPerformanceCounter(&Count2);/獲取時間Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/計算時間差，d的單位為ms.cout插入排序算法對RanNum個隨機數(shù)排序時間為為d ms.endl;cout插入排序算法對RanNum個隨機數(shù)交換次數(shù)為SortNum次。endl;(4) 冒泡排序（bubble sort）：將被排序的記錄數(shù)組R1.n垂直排列，每個記錄Ri看作是重量為Ri.key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上飄浮。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。從無序區(qū)底部向上依次比較相鄰的兩個氣泡的重量，若發(fā)現(xiàn)輕者在下、重者在上，則交換二者的位置。即依次比較(Rn，Rn-1)，(Rn-1，Rn-2)，(R2，R1)；對于每對氣泡(Rj+1，Rj)，若Rj+1.keysetNum();LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/獲取時間Count1double d;unsigned long int temp;for(unsigned long int i=0;iRanNum);i+)for(int j=i+1;jRanNum);j+)if(sisj)temp = si;si=sj;sj=temp;this-SortNum+; QueryPerformanceCounter(&Count2);/獲取時間Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/計算時間差，d的單位為ms.cout冒泡排序算法對RanNum個隨機數(shù)排序時間為d ms.endl;cout冒泡排序算法對RanNum個隨機數(shù)交換次數(shù)為SortNum次。endl; (5) 堆排序：堆排序與其他排序算法最大的區(qū)別是它依靠一種特殊的數(shù)據(jù)結(jié)構(gòu)堆來進行排序。堆是一種完全二叉樹，并且根節(jié)點不大于左右子樹中的所有節(jié)點，ni=n2*i&ni=n2*i+1。因此堆排序算法首先要將給出的無序數(shù)組構(gòu)造成一個堆，然后輸出根節(jié)點（最小元素），將剩余元素重新恢復成堆，再次輸出根節(jié)點。依次類推，直至最后一個節(jié)點輸出，此時堆排序完成。void Sort:heapRestor(unsigned long int *s,int i,int m) int ma;if(imin(s2*i,s2*i+1)if(s2*iheapRestor(s,2*i,m);elsema=si;si=s2*i+1;s2*i+1=ma;this-heapRestor(s,2*i+1,m);this-SortNum=this-SortNum+2;else if(iSortNum+;void Sort:heapCreat(unsigned long int *s,int m)int num;for(num=m/2;num=1;num-)this-heapRestor(s,num,m);void Sort:heapSort(unsigned long int *s1,unsigned long int *s2)this-setNum();int i,num;num=this-RanNum;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/獲取時間Count1double d;this-heapCreat(s1,this-RanNum);for(i=0;iRanNum;i+)s2i=s11;s11=s1num;this-heapRestor(s1,1,-num);QueryPerformanceCounter(&Count2);/獲取時間Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;/計算時間差，d的單位為ms.cout堆排序算法對RanNum個隨機數(shù)排序時間為為d ms.endl;cout堆排序算法對RanNum個隨機數(shù)交換次數(shù)為SortNum次。endl; (6) 合并排序：這里的合并排序和下邊要描述的快速排序都采用了分而治之的思想，但兩者仍然有很大差異。合并排序是將一個無序數(shù)組n1r分成兩個數(shù)組n1r/2與nr/2+1r，分別對這兩個小數(shù)組進行合并排序，然后再將這兩個數(shù)組合并成一個大數(shù)組。由此我們看出合并排序時一個遞歸過程（非遞歸合并排序這里不做討論）。合并排序的主要工作便是“合并”，兩個小規(guī)模數(shù)組合并成大的，兩個大的再合并成更大的，當然元素比較式在合并的過程中進行的。void Sort:mergeSort(unsigned long int *s,int left,int right)int i;if(left right) i=(left + right)/2; mergeSort(s,left, i); mergeSort(s, i + 1, right); Merge(s, left, i, right); int Sort:partition(unsigned long int *s,int low,int high)int key,i,p,r;p=low;r=high;key=sp;while(pp;i-)if(siSortNum+;break; r-;this-SortNum+;for(i=p;ikey)sr=sp;r-;this-SortNum+;break;p+;this-SortNum+;sp=key;return p;(7)基本操作 AList(int size=DefaultListSize) maxSize = size; listSize = fence = 0; listArray = new ElemmaxSize; AList() delete listArray; 清空。釋放數(shù)組，將數(shù)組大小和柵欄置0.void clear() delete listArray; listSize = fence = 0; listArray = new ElemmaxSize;將柵欄賦初值0，放在開頭。void setStart() fence = 0; 將柵欄指向數(shù)組最后。void setEnd() fence = listSize; 獲得當前的位置。用柵欄的指向即可直接獲得。void prev() if (fence != 0) fence-; 獲得最大值的大小，由柵欄可直接獲得。void next() if (fence = listSize) fence+; 返回當前位置左邊的長度。直接返回柵欄的值獲得。int leftLength() const return fence; 返回當前位置右邊的長度。用最大長度減去當前柵欄的值。int rightLength() const return listSize - fence; 設置當前位置，將值直接賦予柵欄。bool setPos(int pos) if (pos = 0) & (pos = 0) & (pos = listSize);返回當前的值。bool getValue(Elem& it) const if (rightLength() = 0) return false; else it = listArrayfence; return true; （4）算法的時空分析插入排序：直接插入排序算法必須進行n-1趟。最好情況下，即初始序列有序，執(zhí)行n-1趟，但每一趟只比較一次，移動元素兩次，總的比較次數(shù)是(n-1)，移動元素次數(shù)是2(n-1)。因此最好情況下的時間復雜度就是O(n)。最壞情況(非遞增)下，最多比較i次，因此需要的比較次數(shù)是：所以，時間復雜度為O(n2)。冒泡排序：當原始數(shù)據(jù)正向有序時，冒泡排序出現(xiàn)最好情況。此時，只需進行一趟排序，作n-1次關鍵字比較，因此最好情況下的時間復雜度是O(n)。當原始數(shù)據(jù)反向有序時，冒泡排序出現(xiàn)最壞情況。此時，需進行n-1趟排序，第i趟作(n-i)次關鍵字間的比較，并且需執(zhí)行(n-i)次元素交換，所以，比較次數(shù)為：因此,最壞情況下的時間復雜度為O(n2)快速排序：如果每一次分劃操作后，左、右兩個子序列的長度基本相等，則快速排序的效率最高，其最好情況時間復雜度為O(nlog2n)；反之，如果每次分劃操作所產(chǎn)生的兩個子序列，其中之一為空序列，此時，快速排序效率最低，其最壞情況時間復雜度為O(n2)。如果選擇左邊第一個元素為主元，則快速排序的最壞情況發(fā)生在原始序列正向有序或反向有序時?？焖倥判虻钠骄闆r時間復雜度為O(nlog2n)。堆排序：堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用Heapify實現(xiàn)的。堆排序的最壞時間復雜度為O(nlogn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是不穩(wěn)定的，算法時間復雜度O(nlogn)。歸并排序：在最佳、平均、最差情況下，時間復雜度為Q(n log n)，不足的就是需要兩倍的空間代價，當輸入的待排序數(shù)據(jù)存儲在鏈表中時，歸并排序是一個很好的選擇.（5）函數(shù)的調(diào)用關系圖用戶輸入排序的元素個數(shù)n產(chǎn)生n個隨機數(shù)主程序?qū)﹄S機數(shù)進行排序輸出（6）輸入和輸出的格式輸入 請輸入排序規(guī)模：/提示輸入 等待輸入 輸出 插入排序算法對n個隨機數(shù)排序時間為 插入排序算法對n個隨機數(shù)交換次數(shù)為 冒泡排序算法對n個隨機數(shù)排序時間為 冒泡排序算法對n個隨機數(shù)交換次數(shù)為 堆排序算法對n個隨機數(shù)排序時間為 堆排序算法對n個隨機數(shù)交換次數(shù)為 合并排序算法對n個隨機數(shù)排序時間為 合并排序算法對n個隨機數(shù)交換次數(shù)為快速排序算法對n個隨機數(shù)排序時間為 快速排序算法對n個隨機數(shù)交換次數(shù)為 排序后，前50個有序元素為：四、用戶使用說明（可選）1、本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為conversion.exe2、運行程序時輸入 請輸入排序規(guī)模：/提示輸入 等待輸入 輸出 插入排序算法對n個隨機數(shù)排序時間為 插入排序算法對n個隨機數(shù)交換次數(shù)為 冒泡排序算法對n個隨機數(shù)排序時間為 冒泡排序算法對n個隨機數(shù)交換次數(shù)為 堆排序算法對n個隨機數(shù)排序時間為 堆排序算法對n個隨機數(shù)交換次數(shù)為 合并排序算法對n個隨機數(shù)排序時間為 合并排序算法對n個隨機數(shù)交換次數(shù)為快速排序算法對n個隨機數(shù)排序時間為 快速排序算法對n個隨機數(shù)交換次數(shù)為 排序后，前50個有序元素為：五：實現(xiàn)圖1 控制臺程序?qū)嶒灲Y(jié)果：實驗分別實現(xiàn)插入排序、冒泡排序、堆排序、合并排序、快速排序，以不同規(guī)模（100，1000，2000，5000，10000，100000個數(shù)據(jù)）的隨機數(shù)作為測試數(shù)據(jù)集，實驗結(jié)果截圖如下：排序規(guī)模為100排序規(guī)模為：1000排序規(guī)模為：2000排序規(guī)模為：5000排序規(guī)模為：10000排序規(guī)模為：100000（六）算法性能分析在程序中我們根據(jù)數(shù)據(jù)規(guī)模的不同產(chǎn)生不同的隨機整型數(shù)組，然后分別讓不同的排序算法來進行從小到大的排序。這里需要注意的是：每種排序算法在相同的輸入規(guī)模中原始無序數(shù)據(jù)都是一樣的。例如五種排序算法要對長度為100的無序數(shù)組進行排序，它們所要排序的無序數(shù)組都是一樣的，我們以此來保證實驗的公正性。在這里我們認為比較次數(shù)是排序算法的主要操作，因此我們在每個排序算法中加入計數(shù)器來記錄排序過程中的比較次數(shù)，以此來作為對算法性能分析的主要參數(shù)（排序時間作為輔助參數(shù)）。表1為在輸入規(guī)模分別為100，1000，2000，5000，10000，100000時各個算法的元素交換次數(shù)。表2為在輸入規(guī)模分別為100，1000，2000，5000，10000，100000時各個算法的排序時間。 排序規(guī)模（n） 算法10010002000500010000100000插入排序27822462559832116266052248708162509250617冒泡排序26842420119631585956790224520141127169842堆排序100016480370631060262319032985016合并排序555871919432553011204091536596快速排序5991037723702714311528791946925表1 排序算法比較次數(shù)性能比較 排序規(guī)模（n） 算法10010002000500010000100000插入排序0.04523.058312.126358.2854177.5416694冒泡排序0.10079.4697621.3535133.777526.97142698.7堆排序0.07370.5794671.284443.595778.03182102.961合并排序0.37092.191434.1192511.679420.8016192.61快速