數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)排序算法時(shí)間性能的分析

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告目錄1 需求分析1.1.1 問題描述1.1.2設(shè)計(jì)內(nèi)容1.2概要設(shè)計(jì)2.2.1原始數(shù)據(jù)2.2.2程序的流程2.2.3總體設(shè)計(jì)圖3.3詳鄉(xiāng)田設(shè)計(jì)和編碼4.3.1算法基本思想4.3.2算法描述4.3.3算法設(shè)計(jì)5.3.4算法時(shí)間分析8.4測(cè)試結(jié)果9.5小結(jié)9.參考文獻(xiàn)10附錄：程序源代碼 1.0數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告1需求分析1.1問題描述(1) 輸入的形式和輸入值的范圍：本程序要求實(shí)現(xiàn)各種算法的時(shí)間性能的比較， 由丁需要比較的數(shù)目較大，不能手動(dòng)輸入，丁是采用系統(tǒng)生成隨機(jī)數(shù)。用戶輸入 隨機(jī)數(shù)的個(gè)數(shù)n,然后調(diào)用隨機(jī)事件函數(shù)產(chǎn)生n個(gè)隨機(jī)數(shù)，對(duì)這些隨機(jī)數(shù)進(jìn)行排 序。丁是數(shù)據(jù)為整數(shù)。(2

2、) 輸出的形式：輸出在各種數(shù)目的隨機(jī)數(shù)下，各種排序算法所用的時(shí)較次數(shù)。(3) 程序所能達(dá)到的功能：該程序可以根據(jù)用戶的輸入而產(chǎn)生相應(yīng)的隨機(jī)數(shù)，然后對(duì)隨機(jī)數(shù)進(jìn)行各種排序，根據(jù)排序進(jìn)行時(shí)間和次數(shù)的比較。(4)測(cè)試數(shù)據(jù)。1.2設(shè)計(jì)內(nèi)容對(duì)各種排序方法(快速排序、堆排序、希爾排序、冒泡排序、歸并排序)的 時(shí)間性能進(jìn)行比較。(1) 設(shè)計(jì)并實(shí)現(xiàn)上述各種排序算法；(2) 在排序中實(shí)現(xiàn)比較時(shí)間性能；(3) 在輸入中分別調(diào)用上述排序算法，并比較時(shí)間性能。202概要設(shè)計(jì)2.1原始數(shù)據(jù)1. 抽象數(shù)據(jù)類型ADT List數(shù)據(jù)對(duì)象 D = ai | ai ElemSet, i=1,2,.,n, n >0 數(shù)據(jù)關(guān)系

3、R1 = <ai-1 ,ai >|ai-1 ,ai D, 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 set

4、Pos(int pos) = 0;bool getValue(Elem&) const = 0;void print() const = 0;2.2程序的流程(1) 輸入模塊：輸入要排序的數(shù)的數(shù)量 n。(2) 處理模塊：系統(tǒng)產(chǎn)生n個(gè)隨機(jī)數(shù)，對(duì)隨機(jī)數(shù)進(jìn)行排序。(3) 輸出模塊：將排序的結(jié)果輸出。2.3總體設(shè)計(jì)圖3詳細(xì)設(shè)計(jì)和編碼3.1算法基本思想1. 隨機(jī)數(shù)的產(chǎn)生：利用srand()產(chǎn)生隨機(jī)數(shù)。2. 快速排序：選定一記錄 R ,將所有其他記錄關(guān)鍵字 K'與記錄R的關(guān)鍵字K比 較，若K'<K則將記錄換至R之前，若K'K則將記錄換至R之后，繼續(xù)對(duì)R前 后兩部分記錄

5、進(jìn)行快速排序，直至排序范圍為 1。3. 希爾排序：將序歹0分割成若干子序歹0分別進(jìn)行直接插入排序，待序歹0記錄基本 有序時(shí)再對(duì)整體進(jìn)行一次直接插入排序。4. 冒泡排序：比較并交換相鄰的元素對(duì)，直到所有元素都被放到正確的地方為止。5. 歸并排序：將兩個(gè)或者多個(gè)有序表歸并成一個(gè)有序表。6. 堆排序：首先將數(shù)組轉(zhuǎn)化為一個(gè)滿足堆定義的序列， 然后將堆頂?shù)淖畲笤厝?出，再將剩下的數(shù)排成堆，再取堆頂數(shù)值，。如此下去，直到堆為空。到最后 結(jié)束時(shí)，就排出了一個(gè)由小到大排列的數(shù)組。3.2算法描述(1) 快速排序是對(duì)起泡排序的一種改進(jìn)。它的基本思想是：通過一趟排序?qū)⒋庞涗浄謩e 分割成獨(dú)立的兩部分，其中一部分記

6、錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字大 小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序歹0有序。(2) 堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。 堆是一個(gè)近似完全二義樹 的結(jié)構(gòu)，并同時(shí)滿足堆性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小丁(或大丁)它的父 結(jié)點(diǎn)。只需一記錄大小的輔助空間，每個(gè)待排序的記錄僅占用一個(gè)存儲(chǔ)空間。它 的思想是：先是對(duì)堆做比較，左子數(shù)小丁本數(shù)，右子數(shù)大丁本數(shù)，然后不停比較、 交換，最后達(dá)到整個(gè)數(shù)組的排序。(3) 希爾排序它乂稱“縮小增量排序”，乂是一種屆插入排序類的方法，但在時(shí)間效率上 有很大改進(jìn)。它的思想是：先把數(shù)組分成等長(zhǎng)的兩個(gè)數(shù)組，用 ri與rn/2+i 比較小的

7、在前，大的在后，然后在一剛剛兩兩一組的兩組做比較，就這樣，每次 比較，每組數(shù)的個(gè)數(shù)都是上一次的兩倍，最后完成整個(gè)數(shù)組的排序。(4) 冒泡排序它是一種“交換”進(jìn)行排序的方法之中最簡(jiǎn)單的一種。它的思想是：相鄰的 兩個(gè)元素進(jìn)行比較，將小的調(diào)到前面，大的調(diào)到后面。(5) 歸并排序“歸并”的含義是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。它的 算法思想是：先把數(shù)組對(duì)半分多次，直到每組只有兩個(gè)數(shù)據(jù)時(shí)，進(jìn)行比較、排序, 然后再兩兩合并，最后做到整個(gè)數(shù)組的排序完成。3.3算法設(shè)計(jì)(1) 產(chǎn)生隨機(jī)數(shù)：直接調(diào)用函數(shù)srand(),以時(shí)間作為隨機(jī)種子進(jìn)行選擇，并把 隨機(jī)數(shù)裝入數(shù)組中。unsigned long

8、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;m<num;m+)ram=rand();cout<<endl;return ra;(2) 快速排序：要實(shí)現(xiàn)快速排序首先選擇一個(gè)軸值，這里選取數(shù)組第一個(gè)為軸 值。定義兩個(gè)標(biāo)識(shí)low,high。high標(biāo)識(shí)最后一個(gè)元素的位置，從后向前，將關(guān) 鍵字與軸值比較

9、，直至遇到小丁軸值的關(guān)鍵字，前移，low標(biāo)識(shí)在第二個(gè)元素的位置，從前向后，將關(guān)鍵字與軸值比較，直至遇到大丁軸值的關(guān)鍵字，后移。當(dāng) low,high相遇后第一趟排序結(jié)束。調(diào)整數(shù)列，軸值左邊的為比軸值小的，右邊 為比軸值大的。對(duì)軸值左邊（即 low至U pivotkey-1 的數(shù)）和右邊的子歹U（pivotkey+1到high的數(shù)）分別進(jìn)行上述遞歸快速排序，直到范圍為1結(jié)束int partition(int a,int low,int high)(/int pivotkey;/pivotkey=alow;while(low<high)(while(low<high&&a

10、high>=pivotkey)-high;alow=ahigh;while(low<high&&alow<=pivotkey)+low;快速排序中的一趟作為樞軸來使用ahigh=alow;alow=pivotkey;return low;void qsort(int a,int low,int high)(/ int pivotloc;if(low<high)(pivotloc=partition(a,low,high);/qsort(a,low,pivotloc-1);qsort(a,pivotloc+1,high);快速排序的遞歸形式一趟排序結(jié)果的調(diào)

11、用(3)希爾排序：先把數(shù)組分成等長(zhǎng)的兩個(gè)數(shù)組，用 ri與rn/2+i比較小 的在前，大的在后，然后在一剛剛兩兩一組的兩組做比較，就這樣，每次比較， 每組數(shù)的個(gè)數(shù)都是上一次的兩倍，最后完成整個(gè)數(shù)組的排序。void ShellInsert(sqList &L,int dk)(/對(duì)順序表L作一趟希爾插入排序。For (i=dk+1;i<=L.length;+i)If(LT(L.ri.key,L.ri-dk.key)/需將 L.ri 插入有序增量子表L.r0=L.ri;/ 暫存在 L.r0 For(j=i-dk;j>0&&LT(L.r0.key,L.rj.key);

12、j-=dk)L.rj+dk=L.rj;/記錄后移，查找插入位置L.rj+dk=L.r0;/插入 冒泡排序(bubble sort ):將被排序的記錄數(shù)組 R1.n垂直排歹U,每個(gè)記 錄Ri看作是重量為Ri.key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則， 從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此 反復(fù)進(jìn)行，直到最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。從無(wú)序區(qū)底部向上依次比較相鄰的兩個(gè)氣泡的重量，若發(fā)現(xiàn)輕者在下、重者在上，則交換二者的位置。即依次比較(Rn , Rn-1) , (Rn-1 , Rn-2) , , , (R2 , R1); 對(duì)

13、丁每對(duì)氣泡(Rj+1 , Rj),若 Rj+1.key<Rj.key ,則交換 Rj+1和 Rj 的內(nèi)容。第一趟掃描完畢時(shí)，"最輕"的氣泡就飄浮到該區(qū)間的頂部，即關(guān)鍵字最 小的記錄被放在最高位置 R1上。掃描R2.n。掃描完畢時(shí)，"次輕"的氣泡飄 浮到R2的位置上，最后，經(jīng)過 n-1趟掃描可得到有序區(qū)R1.n(5)堆排序：將序列看成是完全二義樹，完全二義樹中所有非終端結(jié)點(diǎn)的值均不 大丁(或不小丁)其左右孩子結(jié)點(diǎn)的值。若在輸出堆頂最小值之后，使得剩余的 元素序列乂重建成一個(gè)堆，則得到次小值。如此反復(fù)，就得到一個(gè)有序序列。(6)歸并排序：歸并排序是將一

14、個(gè)無(wú)序數(shù)組n1 , r分成兩個(gè)數(shù)組n1 , r/2與nr/2+1 , r,分別對(duì)這兩個(gè)小數(shù)組進(jìn)行歸并排序，然后再將這兩個(gè)數(shù)組合并 成一個(gè)大數(shù)組。由此我們看出歸并排序時(shí)一個(gè)遞歸過程。歸并排序的主要工作便是“合并”,兩個(gè)小規(guī)模數(shù)組合并成大的，兩個(gè)大的再合并成更大的，當(dāng)然元素 比較式在合并的過程中進(jìn)行的。3.4算法時(shí)間分析<1>希爾排序：當(dāng)n在某個(gè)特定范圍內(nèi)，希爾排序所需的比較次數(shù)和移動(dòng)次數(shù)約 為n的1.3次方，當(dāng)n->無(wú)窮大時(shí)，可減少到n(log2n)22。<2>冒泡排序：當(dāng)原始數(shù)據(jù)正向有序時(shí)，冒泡排序出現(xiàn)最好情況。此時(shí)，只需進(jìn) 行一趟排序，作n-1次關(guān)鍵字比較，因此

15、最好情況下的時(shí)間復(fù)雜度是O(n)。當(dāng)原始數(shù)據(jù)反向有序時(shí)，冒泡排序出現(xiàn)最壞情況。此時(shí)，需進(jìn)行 n-1趟排序，第i 趟作(n-i)次關(guān)鍵字間的比較，并且需執(zhí)行(n-i)次元素交換，所以，比較次數(shù)為： 因此，最壞情況下的時(shí)間復(fù)雜度為 O(n2)。<3快速排序：如果每一次分劃操作后，左、右兩個(gè)子序列的長(zhǎng)度基本相等，則 快速排序的效率最高，其最好情況時(shí)間復(fù)雜度為O(nlog2n)；反之,如果每次分劃操作所產(chǎn)生的兩個(gè)子序列，其中之一為空序列，此時(shí)，快速排序效率最低，其 最壞情況時(shí)間復(fù)雜度為O(n2)。如果選擇左邊第一個(gè)元素為主元，則快速排序的 最壞情況發(fā)生在原始序列正向有序或反向有序時(shí)。快速排序的平

16、均情況時(shí)間復(fù)雜度為 O(nlog2n)。<4>堆排序：堆排序的時(shí)間，主要由建立初始堆和反復(fù)重建堆這兩部分的時(shí)間開 銷構(gòu)成，它們均是通過調(diào)用Heapify實(shí)現(xiàn)的。堆排序的最壞時(shí)間復(fù)雜度為O(nlogn)。堆排序的平均性能較接近丁最壞性能。由丁建初始堆所需的比較次數(shù) 較多，所以堆排序不適宜丁記錄數(shù)較少的文件。堆排序是不穩(wěn)定的，算法時(shí)間復(fù)雜度 O(nlogn)。<5>歸并排序：在最佳、平均、最差情況下，時(shí)間復(fù)雜度為 (n log n),不足的就 是需要兩倍的空間代價(jià)，當(dāng)輸入的待排序數(shù)據(jù)存儲(chǔ)在鏈表中時(shí)，歸并排序是一個(gè) 很好的選擇.4測(cè)試結(jié)果1.程序主界面I ' F:讖據(jù)

17、結(jié)構(gòu)誤程沒計(jì)做據(jù)結(jié)構(gòu)組員深程既十淚北ugMang方rndexb|=排序的時(shí)間性能的分析= = = = = = = = =5 種排序的排序時(shí)間和交換次數(shù)= = = = =BillS瞻懿:嚼熾嚴(yán)RIi：W®-r8419 -=排序的時(shí)間性能的分析=5小結(jié)通過此次課程設(shè)計(jì)使我更加深入的了解了各種排序算法的思想和基本原 理。對(duì)內(nèi)部排序算法的基本運(yùn)算有所掌握，充分理解了各種排序算法的優(yōu)缺點(diǎn)。學(xué)會(huì)了如何把學(xué)到的知識(shí)用丁解決實(shí)際問題， 鍛煉了自己的動(dòng)手能力。在設(shè)計(jì)的 整個(gè)過程中我遇到了很多問題，使我認(rèn)識(shí)了自己的不足，還有很多地方有待改正 和提高。但和同學(xué)積極溝通討論，相互學(xué)習(xí)，相互幫助，一個(gè)人的力量

18、是渺小的， 但團(tuán)結(jié)的力量是不容忽視的，也同樣鍛煉了我們的協(xié)作能力，為以后在學(xué)習(xí)工作 中能更好發(fā)展打下了堅(jiān)實(shí)的基礎(chǔ)。這次課程設(shè)計(jì)使我受益匪淺。參考文獻(xiàn)1 王昆侖，李紅等編著.數(shù)據(jù)結(jié)構(gòu)與算法.北京:中國(guó)鐵道出版社,2007.2 蘇仕華等編著.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).北京：機(jī)械工業(yè)出版社,2005.3 蘇仕華編著.數(shù)據(jù)結(jié)構(gòu)與算法解析.合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2004.4 郭嵩山等著.國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽例題解.北京：電子工業(yè)出版社,2008.5 劉大有，唐海鷹等編著.數(shù)據(jù)結(jié)構(gòu).北京：高等教育出版社,2001.6 徐孝凱編著.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程.北京：活華大學(xué)出版社，1999.7 嚴(yán)蔚敏，陳文博編著.

19、數(shù)據(jù)結(jié)構(gòu)及算法教程.北京：活華大學(xué)出版社，2001.8 劉振安，劉燕啟等編著.C程序設(shè)計(jì)課程設(shè)計(jì).北京：機(jī)械出版社，2004.9 胡學(xué)鋼.數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)指導(dǎo).北京：活華大學(xué)出版社，1999.附錄：程序源代碼/*cout：輸出 cin :輸入 endl： 換行system("pause"):屏幕暫停(去掉這句屏幕瞬間自動(dòng)關(guān)閉)*/#include<time.h>#include<windows.h>#include<iostream>#include <stdlib.h>using namespace std;/命名空間，使

20、 cout/cin ,起作用const int maxsize=9999;int num=0;/定義全局變量，為每一趟的輸出做準(zhǔn)備int x=0;template<class type>class sortlist(private:int SortNum;int currentsize;/數(shù)據(jù)表中數(shù)據(jù)元素的個(gè)數(shù)public:type *arr;/存儲(chǔ)數(shù)據(jù)元素的向量(排序表)sortlist():currentsize(0)arr=new typemaxsize;/構(gòu)造函數(shù)sortlist(int n)arr=new typemaxsize;currentsize=n;void in

21、sert(int i,type x)arri=x;sortlist()delete arr;/析構(gòu)函數(shù)void swap(type &x,type &y)/數(shù)據(jù)元素x和y交換位置type temp=x;x=y;y=temp;void bubblesort();/冒泡排序void selectsort();/快速排序void heapsort();/堆排序void mergesort(sortlist<type> &table);/歸并排序void shellsort();/希爾排序void filterdown(const int start);/建立最大堆

22、voidmergepass(sortlist<type>&sourcetable,sortlist<type>&mergedtable,constint len);/一趟歸并voidmerge(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const intleft,const int mid,const int right);/兩路歸并算法;template <class type>/冒泡排序 OKvoid sortlist<type

23、>: bubblesort()( SortNum = 0;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/獲取時(shí)間 Count1int i=1;double d;int finish=0;/0表示還沒有排好序while ( i<currentsize && !finish )( finish=1;/排序結(jié)束標(biāo)志置為，假定已經(jīng)排好序for (int j=0; j < c

24、urrentsize-i; j+ )if (arrj > arrj+1 )/逆序( swap(arrj,arrj+1);/相鄰元素交換位置finish=0;SortNum+;/排序結(jié)束標(biāo)志置為，表示本趟發(fā)生了交換，說明還沒有排好序 i+;QueryPerformanceCounter(&Count2);/獲取時(shí)間 Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart *1000.0;coutvv"冒泡排序算法，排序時(shí)間為"vvdvv" ms "<

25、<endl;cout<<"冒泡排序算法，交換次數(shù)為 "vvSortNumvvendl;num = 0;coutvvendl;template vclass type>/快速排序 OKvoid sortlistvtype>:selectsort()( SortNum = 0;double d;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/獲取時(shí)間 Co

26、unt1int i=0;int finish = 0; /0表示還沒有排好序while (i<currentsize-1 && ! finish) finish = 1;/排序結(jié)束標(biāo)志置為，假定已經(jīng)排好序for (int j=i+1; j<currentsize; j+) if (arri > arrj) swap (arri,arrj);finish = 0;SortNum+;i+;QueryPerformanceCounter(&Count2);/獲取時(shí)間 Count2d=(double)(Count2.QuadPart-Count1.QuadPa

27、rt)/(double)Freg.QuadPart *1000.0;cout<<"快速選擇排序算法，排序時(shí)間為"<<d<<" ms "<<endl;cout<<"快速選擇排序算法，交換次數(shù)為"<<SortNum+<<endl;num = 0;/SortNum = 0;cout<<endl;template <class type>/建立最大堆void sortlist<type>:filterdown(const i

28、nt start)/向下調(diào)整使從start開始到currentsize-1為止的子表成為最大堆int i=start,j=2*i+1;/j 為 i 的左孩子int tablesize=currentsize;type temp=arri;while (j <= currentsize-1) if (j<currentsize-1 && arrj<arrj+1)j+;/在兩個(gè)孩子中選關(guān)鍵字較大者if (temp >= arrj)break;else arri = arrj;i = j;j = 2*j+1;SortNum+;SortNum+;arri = t

29、emp;template <class type>/ 堆排序 OKvoid sortlist<type>:heapsort() SortNum = 0;double d;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/ 獲取時(shí)間 Count1 int tablesize=currentsize,i;for (i=(currentsize-2)/2; i>=0; i-)fi

30、lterdown(i); /初始建堆for (i=currentsize-1; i>=1; i-)( swap(arr0,arri);/堆頂元素和最后一個(gè)元素交換currentsize-;filterdown(0);/重建最大堆QueryPerformanceCounter(&Count2);d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;cout<<"堆排序算法，排序時(shí)間為"<<d<<" ms "<&

31、lt;endl;cout<<"堆排序算法，交換次數(shù)為 "<<SortNum<<endl;num = 0;/SortNum = 0;currentsize = tablesize;template <class type>/ 希爾排序 OKvoid sortlist<type>:shellsort()( SortNum = 0;double d;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);Que

32、ryPerformanceCounter(&Count1);/獲取時(shí)間 Count1if (currentsize<=1 | arr=NULL)return;for (int div=currentsize/2; div>=1; div/=2)(for (int i=div; i<currentsize; i+=div)(for (int j=i; (arrj<arrj-div) && j>=0; j-=div)(swap(arrj,arrj-div);SortNum+;QueryPerformanceCounter(&Count2

33、);/ 獲取時(shí)間 Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart *1000.0;cout<<”希爾排序算法，排序時(shí)間為"<<d<<" ms "<<endl;cout<<”希爾排序算法，交換次數(shù)為 "<<SortNum<<endl;num = 0;/SortNum = 0;cout<<endl;template <class type>voidsortl

34、ist<type>:merge(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int right)( int i=left,j=mid+1,k=left;/ 指針初始化/i是前一段的當(dāng)前元素位置，j是后一段的當(dāng)前元素位置，k是輔助數(shù)組的當(dāng) 前位置while (i<=mid && j<=right)if (sourcetable.arri <= sourcetable.arrj)(

35、 mergedtable.arrk = sourcetable.arri;i+;k+;SortNum+;else( mergedtable.arrk = sourcetable.arrj;j+；k+;SortNum+;if (i <= mid)for (int p=k,q=i; q<=mid; p+,q+)( SortNum+;mergedtable.arrp = sourcetable.arrq;elsefor (int p=k,q=j; q<=right; p+,q+)( mergedtable.arrp = sourcetable.arrq;/把后一段復(fù)制至 USort

36、Num;mergedtable;template <class type>/歸并排序循環(huán)調(diào)用它voidsortlist<type>:mergepass(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int len)( int i = 0;while (i+2*len <= currentsize-1)/表示至少有個(gè)子序歹0( merge(sourcetable,mergedtable,i,i+len-1,i+2*len-1);i+=2*len;Sort

37、Num+;if (i+len <= currentsize-1)/若只有最后兩個(gè)子序歹0( merge(sourcetable,mergedtable,i,i+len-1,currentsize-1);SortNum+;else/若只有最后一個(gè)子序歹Ufor (int j=i; j<=currentsize-1; j+)( mergedtable.arrj=sourcetable.arrj;SortNum+;template <class type>/歸并排序 OKvoid sortlist<type>:mergesort(sortlist<type> &table )(/按數(shù)據(jù)元素關(guān)鍵字非遞減的順序?qū)ε判虮韙able中數(shù)據(jù)元素進(jìn)行遞歸排序SortNum = 0;double d;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequ