歸并排序算法論文

1、 歸并排序算法解決排序問題目錄 TOC o 1-5 h z HYPERLINK l bookmark2 o Current Document 1 引言 2 HYPERLINK l bookmark4 o Current Document 歸并排序的基本思想 2 HYPERLINK l bookmark6 o Current Document 歸并排序算法不同的方式 3 HYPERLINK l bookmark8 o Current Document 歸并排序基本算法 3 HYPERLINK l bookmark10 o Current Document 實(shí)現(xiàn)過程 3 HYPERLINK l b

2、ookmark24 o Current Document 性能分析： 4 HYPERLINK l bookmark26 o Current Document 遞歸二路歸并排序 5 HYPERLINK l bookmark28 o Current Document 算法過程 5性能分析： 6 HYPERLINK l bookmark32 o Current Document 歸并排序算法的改進(jìn)算法 7 HYPERLINK l bookmark34 o Current Document 引理 7 HYPERLINK l bookmark36 o Current Document 應(yīng)用例子 7 HY

3、PERLINK l bookmark38 o Current Document 時(shí)間復(fù)雜性的分析 8 HYPERLINK l bookmark40 o Current Document 總結(jié) 9 HYPERLINK l bookmark42 o Current Document 參考文獻(xiàn) 91 引言從歸并排序的概念上進(jìn)行分析，該算法的思想比 較容易理解，并且也能夠直觀的感知其實(shí) 質(zhì)是利用存儲(chǔ)空間的歸并。在實(shí)現(xiàn)的過程中，可以有多種方法， 畫出歸并過程示意圖后， 隨即可以得出其算法的代碼。 但是我們?cè)诶眠f歸思想實(shí)現(xiàn)歸并排序的教學(xué)程中， 一定要讓 學(xué)生分清是用遞歸還是用回歸進(jìn)行的歸并， 畫出圖形區(qū)

4、分這兩種不同的歸并過程。 通過這一 環(huán)節(jié)，我們不但能夠理解穩(wěn)定的歸并排序， 而且還讓學(xué)生認(rèn)清遞歸和回歸是解決這一問題兩 種不同的操作過程。2.歸并排序的基本思想歸并排序主要是二路歸并排序，它的基本思想是：設(shè) n 個(gè) 數(shù)據(jù)，初始時(shí)把他們看成 n 個(gè)長度為 l 的有序子數(shù)組，然后從 第個(gè)子數(shù)組開始，把相鄰的子數(shù)組兩兩歸并，得 到 n 2 個(gè)長 度為 2 的新的有序子數(shù)組 （當(dāng) n 為奇數(shù)是最后個(gè)新的有序子 數(shù)組長度 為 1） ；對(duì)這些新的有序子數(shù)組再兩兩歸并；如此重復(fù)，直到得到個(gè)長度為 n 的有序數(shù)組為止”。 歸并排序有兩種實(shí)現(xiàn)方法： 自頂向下和自底向上， 前者定 義是自底向上，3.歸并排序算法不

5、同的方式1.歸并排序基本算法1.實(shí)現(xiàn)過程當(dāng)初次理解歸并概念的時(shí)候，我們可以列舉下列 一組數(shù)據(jù)的歸并過程。 例如： 70 83 100 65 10 32 7 65 9第一次：【70 83】【65 100】【10 32】【7 65】【9】 第二次：【65 70 83 100 】【 7 10 32 65】【9】 第三次：【7 10 32 65 65 70 83 100 】【9】 第四次：【7 9 10 32 65 65 70 83 100 】 具體程序代碼如下：函數(shù)： void merge(int e ， int n) 形參說明： e 是已知待排序的數(shù)組， n 是數(shù)組中元素的個(gè)數(shù)，下標(biāo)從 0 開始。

6、 void merge(int e ， int n) int +p=(int+)malloc(Sizeof(int)+n) ； * 開辟一塊實(shí)現(xiàn)交替歸并空間 * int len=l，f=0； *len 為歸并單元寬度， f 是一個(gè)標(biāo)識(shí)，實(shí)現(xiàn)交替歸并 * while(1enn) *當(dāng)歸并單元達(dá)到或者超過序列長度時(shí)，歸并結(jié)束* if(f=0)merge pass(e ， P， n，len) ； *交替進(jìn)行歸并 * else merge pass(p， e，n，fen);len*=2 ； *擴(kuò)大歸并單元寬度 * f=lf；if(f) *將最終結(jié)果存放的指定數(shù) 據(jù)域中 * for(f=0;fn ； f

7、+)ef=pf ； free(p);Void merge_pass(int e ，int a ， int n，intlen)int f _S，s_end； *f_ s 存放即將歸并的第一個(gè)單元起始下標(biāo) *f _s=0； *S_end 存放即將歸并的第二個(gè)單元末下標(biāo) * while(f_s+ len=n)s end=n 一 1; * 確定真正末下 標(biāo)位置 *merg_step(e ， a， f_s ， f_s+len-1， s_end)； *實(shí)現(xiàn)將兩個(gè)單元合并 * f_s=S_end+l;if(f_sn) *沒有歸并的部分復(fù)制過去，保證交替歸并的正確進(jìn)行 * for( ； f_sn； f_s+)

8、af_s=ef S；void merge step(int e ，int a ， int s， int m，int n) * 實(shí)現(xiàn)將兩部分單元?dú)w并， m 為分界點(diǎn)下標(biāo)， 即為第一單元的末下標(biāo) * int i， J， k； k=i=s； J=m+1； while(i=m j=n) if(ei=ej ak+=ei+;else ak+=ej+; while(i=m) ak+=ei+; while(j=n) ak+=ej+;2.性能分析：利用最基本的方法實(shí)現(xiàn)歸并排序， 我們需要利用三個(gè)函數(shù)， 在實(shí)現(xiàn)的過程中， 程序的可讀較 高。但是在程序執(zhí)行的過程中， 函數(shù)之間需要頻繁的進(jìn)行嵌套調(diào)用， 數(shù)據(jù)的交替歸并

9、也顯得 比較麻煩，所以在正確的實(shí)現(xiàn)歸并算法的基礎(chǔ)上，我們引入了遞歸序列的方法。2.遞歸二路歸并排序1.算法過程利用遞歸的思想可以掩蓋上一方法的頻繁嵌套調(diào)用，而利用遞歸的真正目的還可以解決上一方法中數(shù)據(jù)的交替歸并，其方法是它將數(shù)組分解成兩部分a1，?，am和am+1，?，ar來排序數(shù)組a l，?，ar。這兩個(gè)子數(shù)組部分獨(dú)立排序（通過遞歸調(diào)用），而且將 生成的有序予文件歸并得到最后的所有文件。進(jìn)而可以得到一個(gè)原形化的分治遞歸程序。在分解過程中我們可以參照下面的數(shù)據(jù)分解圖。例如：一組數(shù)據(jù)為：70、83、100、65、10、32、7、65、9共9個(gè)元素，由元素的個(gè)數(shù)我們可以畫出二分遞歸圖形。令函數(shù)內(nèi)部

10、第一次遞歸調(diào)用左半部分，可以得出歸并的過程:70 83 100 65 10 32 7 65 970 83 100 65 10 32 7 65 970 83 100 10 6532 7 65 910 65 70 83 100 32 7 65 910 65 70 83 100 7 32 65 910 65 70 83 100 7 32 9 6510 65 70 83 100 7 9 32 657 9 10 32 65 65 70 83 100Void merge(i nt sr,i nt tr,i nt I,i nt m,i nt n)Int j2=m+1,j1=l,k=l;if(srj1=srj

11、2)trk+=stj1+；else trk+=srj2+；while(j1=m)trk+=srjl+；while(j2=n)trk+=srJ2+；for(k=i ； k=n ； k+)srk=trk;)Void msort(int sr , int tr , int S, int t)t int m ;if(s=t)trs=srS;else (m=(s+t) / 2;msort(sr, tr, s, m);msort（sr ， tr， m+l， t） ； merge（sr ，tr ， s， m，t）；）)2.性能分析： 由于本次二路歸并排序算法是通過遞歸劃分有序段的，且遞歸的深度恰好與 n 個(gè)

12、結(jié)點(diǎn)的完 全二叉樹的深度相同，每個(gè)有序段的長度不超過n， 所以兩個(gè)有序段的合并算法時(shí)間數(shù)量級(jí)不會(huì)超過 0(n)。因此，對(duì)n個(gè)記錄進(jìn)行歸并排序的時(shí)間性能T(n)-0(nl092n)?？臻g上，需要兩個(gè)與待排序記錄序 列空間等長的輔助空間及遞歸時(shí)深度為 l092n 的?？?間，因此， 總的空間需求為 S(n)=0(n+l092n)。對(duì)于每個(gè)遞歸程序都有一個(gè)對(duì)應(yīng)的非遞歸程序， 雖然等價(jià)， 但它可以按不同的順序來執(zhí) 行。作為分治算法設(shè)計(jì)思想的一個(gè)原型， 歸并排序的遞歸與非遞歸的區(qū)別值得我們?cè)敿?xì)加以 研究。請(qǐng)看遞歸算法完成的歸并序列。 如下所示， 一個(gè)共有 9 個(gè)元素的序列通過如下歸并序列 進(jìn)行排序： (

13、n+m 表示 n 個(gè)元素與 m 個(gè)元素進(jìn)行歸并 )1+1 2+1 1+1 3+2 1+1 1+1 2+2 5+4 歸并的順序由算法的遞歸結(jié)構(gòu)決定。但如果采用 的是非遞歸的方法，各子序列被獨(dú)立 處理，歸并則可 以按不同的結(jié)合序列來完成。如下顯示了第一次的非 遞歸策略進(jìn)行排序， 其中的歸并序列為：l+1 1+1 1+1 1+1 2+2 2+2 4+4 8+1 在這兩種情況下，遞歸的結(jié)合形式是：4個(gè)1+1， 1個(gè) 2+1， 1個(gè) 2+2， 1個(gè) 3+2， 1個(gè)5+4，而非遞歸的結(jié)合形式是： 4個(gè) 1+1， 2個(gè) 2+2， 1個(gè) 4“， 1個(gè) 8+1。不但歸并的完成順序不 同，而且歸并元素的分配也是不

14、同的。 遞歸方法的分配方式是在單方向遞歸的過程中分配好 歸并的次序， 當(dāng)單個(gè)遞歸結(jié)束后， 進(jìn) 行回歸的時(shí)候， 開始進(jìn)行真正的歸并， 在歸并的過程 中 還要確保右邊的歸并集合也是有序的， 進(jìn)而在回歸的過程中還要進(jìn)行右邊歸并集合的歸并操 作，如此不斷地進(jìn)行，最后則達(dá)到有序整體。歸并排序算法的改進(jìn)算法1.引理設(shè)有p個(gè)數(shù)據(jù)，若用下列方法分組，X ?GI(tl, 2, ? , P)滿足：t=1+(x-min)/(max-min)X (p-1).其中，min , max是這P個(gè)數(shù)的最小值和最大值。 則對(duì)任意xX?Gy?G x s。排序的體算法： 設(shè)有 n 個(gè)數(shù)據(jù)序列， m=n/2 前 m 個(gè)數(shù)據(jù)的最小值為

15、 min ， 最大 值為 max。若rain=max，則執(zhí)行 。用引理方法分組。若組GI中的元素多于一個(gè)，則需要用遞歸再次調(diào)用本排序算法。對(duì)于后m=n-n/2個(gè)數(shù)據(jù)，令其最小值為 min，最大值為 max，若min=max則執(zhí)。用下列方法對(duì)該 m個(gè)數(shù)據(jù)分組，x Go,滿足：1=【n, 2】+l+(x min)/(max-min)。若 Gi 中數(shù)據(jù)元素多于個(gè),則利用遞歸繼續(xù)排序。應(yīng)用兩路歸并算法,將已有序列的前 n/2 個(gè)與 n-n/2 個(gè)數(shù)據(jù)歸并成個(gè)長度為 n 的完整排序序列。該算法對(duì)“散列型”數(shù)據(jù)序列排序較優(yōu),而對(duì)“密集型” 數(shù)列排序要增加一些存儲(chǔ)空 間。2.應(yīng)用例子數(shù)列 X=3 5,70,

16、43 , 50, 10040604。 8,80, 1o 利用該算法 排序過程為n=10, n/2=5，在前五個(gè)數(shù)據(jù)中min-3 5,max=10.0分組 Gl=35, 43, 50, G2, G3=70, G4=, G5=100。遞歸：n=3，在n/2=1的第一個(gè)數(shù)據(jù)中 min=3 . 5, max=3. 5, 而單個(gè) G2=3. 5 有序。而后 3-1=2 個(gè)數(shù)據(jù)分組 G2=(43, 50)中 min=43, max=50 又進(jìn)行遞歸： 2/2=1 得G2=4. 3, G3=5. 0.歸并G1, G2, G3后得有序子序列3. 5, 4. 3, 5. 0),因此可得 前五個(gè)有 序子序列為 f

17、35, 43, 50,70, 10oJ。n=10 的后五個(gè)數(shù)據(jù)中min=1 0, max=80 遞歸步驟 (1)和 (2)后得 G110,G2=,G3=4. 0, G4=(4. 8, 6. 0), G5= 8. 0。遞歸步驟 ：n=2,這兩個(gè)數(shù)據(jù)的前一個(gè) 數(shù)據(jù) min=4. 8, max=4. 8,則這單個(gè)數(shù)據(jù)序列 4. 8有序。這兩個(gè)數(shù)據(jù)后個(gè)數(shù)據(jù)的max=min=6. 0單個(gè)6. 0)有序,歸并后得有序子序列 (1. 0, 4. 0, 4. 8, 6. 0, 8. 0)。最后得兩個(gè)長度為 5的子序列歸并為長度為 10的有序序列,此為排序的結(jié)果。時(shí)間復(fù)雜性的分析命題： n 個(gè)數(shù)據(jù)歸并排序改進(jìn)算

18、法的時(shí)間復(fù)雜性為T(n)=O(nlogn)證明：設(shè)n個(gè)關(guān)鍵字排序的算法所需時(shí)間為M(n),最壞情 況下，n , 2個(gè)數(shù)據(jù)全部被分配到同一組中，而求出 In/21 個(gè)數(shù)據(jù) 的最大值和最小值所需的時(shí)間是 n 的線性函數(shù)， 而兩路歸并排 序所需的時(shí)間也是 n 的線性函數(shù)，因此有：M(n)=cn+2M(n/2)將n個(gè)數(shù)據(jù)項(xiàng)排序所需的時(shí)T(n)展開成：T(n) 1 T(n)=Co n=l其中C1和c0均為某個(gè)正常數(shù)，c,n表示遞歸劃jl【d-3第一步所需要的時(shí)間，因?yàn)镸(r1)時(shí)間是線性的，所以上述公式可近似地表示為：T(n)wcn+2T(11 , 2) n1T(n)=co n=1 其中 C 也是某個(gè)正常數(shù)，由此可得遞歸方程的解為：T(n)=cnlogn+O(n) 所以在最壞的情況下，該算法的時(shí)間復(fù)雜度為T(n)=O(nlogn)4.總結(jié)總之，以上幾種歸并排序的實(shí)現(xiàn)形式，是兩個(gè)基 本的歸并排序算法，均以歸并兩個(gè)有 序序列為一個(gè)有 序序列的運(yùn)算為基礎(chǔ)。 這兩個(gè)算法緊密相關(guān)， 而且實(shí) 際上， 當(dāng)排序元素個(gè) 數(shù)為 2 的冪時(shí)， 它們執(zhí)行著相 同的歸并集合， 但它們卻并不相等， 因?yàn)闅w并集合 的結(jié)合順 序是不一樣