算法設(shè)計(jì)與分析第-章遞歸分治策略

1、算法設(shè)計(jì)與分析授課教師：劉偉電 話： 郵 件： 辦 公 室：長(zhǎng)安校區(qū) 2 號(hào)實(shí)驗(yàn)樓 303 室 （軟件工程系辦公室）西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略2.7 合并排序排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。如圖像檢索中的檢索結(jié)果排序是依據(jù)某種算法計(jì)算得到的“檢索圖像相似性”關(guān)鍵字，然后進(jìn)行排序；在谷歌上搜索網(wǎng)頁(yè)，也是按照一定的算法計(jì)算網(wǎng)頁(yè)的“重要性”進(jìn)行排序。有很多排序算法，如冒泡排序、插入排序、選擇排序等。西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略自然圖像檢索結(jié)果排序醫(yī)學(xué)圖像檢索結(jié)果排序西安郵電大學(xué)計(jì)算機(jī)

2、學(xué)院第2章 遞歸與分治策略網(wǎng)頁(yè)檢索結(jié)果排序西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略合并排序算法是用分治策略實(shí)現(xiàn)對(duì) n 個(gè)元素進(jìn)行排序的算法。其基本思想是（1）將待排序元素分成大小大致相同的兩個(gè)子集合，（2）分別對(duì)兩個(gè)子集合進(jìn)行排序，最終（3）將排好序的子集合合并成為所要求的排好序的集合。合并排序算法可遞歸地描述如下：templatevoid MergeSort( Type a, int left, int right ) if ( left right ) / 至少有2個(gè)元素 int i = ( left + right ) / 2; /取中點(diǎn) MergeSort( a, left, i

3、); MergeSort( a, i + 1, right ); Merge( a, b, left, i, right ); /合并到數(shù)組b Copy( a, b, left, right ); /復(fù)制回?cái)?shù)組a 西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略合并排序算法示例西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略算法說(shuō)明（1）Merge 函數(shù)：合并兩個(gè)排好序的數(shù)組段到一個(gè)新的數(shù)組 b 中；（2）Copy 函數(shù)：將合并后的數(shù)組段再?gòu)?fù)制回?cái)?shù)組 a 中。Merge 函數(shù) 和 Copy 函數(shù)可以在 O( n ) 時(shí)間內(nèi)完成，計(jì)算時(shí)間 T( n ) 滿足：西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略

4、算法的進(jìn)一步改進(jìn)很容易看出，上述算法中的 MergeSort 函數(shù)的遞歸過(guò)程只是將待排序集合一分為二，直至待排序集合只剩下一個(gè)元素為止，然后不斷合并兩個(gè)排好序的數(shù)組段。因此可以首先將數(shù)組 a 中相鄰元素兩兩配對(duì)，用合并算法將它們排序，構(gòu)成 n / 2 組長(zhǎng)度為 2 的排好序的子數(shù)組段，然后再將它們排序成長(zhǎng)度為 4 的排好序的子數(shù)組段，如此直至整個(gè)數(shù)組排好序。用這種思想可以消去遞歸，“消去遞歸后的合并排序算法”描述如下：西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略templatevoid MergeSort( Type a, int n ) Type * b = new Type n ; / 定

5、義輔助空間 b int s = 1; while( s n ) MergePass( a, b, s, n ); / 合并到數(shù)組 b s += s; MergePass( b, a, s, n ); / 合并到數(shù)組 a s += s; 西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略上述算法中的函數(shù) MergePass 用于合并排好序的相鄰數(shù)組段。具體的合并算法由 Merge 來(lái)實(shí)現(xiàn)。templatevoid MergePass( Type x, Type y, int s, int n ) / 合并大小為 s 的相鄰子數(shù)組 int i = 0; while( i = n - 2 * s ) /

6、合并大小為 s 的相鄰 2 段子數(shù)組 Merge( x, y, i, i + s - 1, i + 2 * s - 1 ); i = i + 2 * s; / 剩下的元素個(gè)數(shù)少于 2s if ( i + s n ) Merge( x, y, i, i + s - 1, n - 1 ); else for( int j = i; j = n - 1; j+ ) y j = x j ; 西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略templatevoid Merge( Type c, Type d, int l, int m, int r ) / 合并 cl:m 和 cm + 1:r 到 dl:r

7、 int i = 1, j = m + 1,k = 1; while( ( i = m ) & ( j = r ) ) if ( c i m ) for( int q = j; q = r;q+ ) d k+ = c q ; else for( int q = i; q = m;q+ ) d k+ = c q ; 類型為 Type 的元素的比較運(yùn)算“=”：如果 Type 是自定義的，則必須重載運(yùn)算“=”。比如 2 幅圖像之間的大小比較。西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略輔助數(shù)組smallestsmallestAGLORHIMST A西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略合并過(guò)程

8、（1）在每一半排序數(shù)組中指向最小元素；（2）將二者中的較小的值插入輔助數(shù)組；（3）重復(fù)直至結(jié)束。smallestsmallestAGLORHIMSTA G西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略輔助數(shù)組合并過(guò)程（1）在每一半排序數(shù)組中指向最小元素；（2）將二者中的較小的值插入輔助數(shù)組；（3）重復(fù)直至結(jié)束。smallestsmallestAGLORHIMSTAG H西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略輔助數(shù)組合并過(guò)程（1）在每一半排序數(shù)組中指向最小元素；（2）將二者中的較小的值插入輔助數(shù)組；（3）重復(fù)直至結(jié)束。smallestsmallestAGLORHIMSTAGH I西安郵電大學(xué)

9、計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略輔助數(shù)組合并過(guò)程（1）在每一半排序數(shù)組中指向最小元素；（2）將二者中的較小的值插入輔助數(shù)組；（3）重復(fù)直至結(jié)束。smallestsmallestAGLORHIMSTAGHI L西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略輔助數(shù)組合并過(guò)程（1）在每一半排序數(shù)組中指向最小元素；（2）將二者中的較小的值插入輔助數(shù)組；（3）重復(fù)直至結(jié)束。smallestsmallestAGLORHIMSTAGHIL M西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略輔助數(shù)組合并過(guò)程（1）在每一半排序數(shù)組中指向最小元素；（2）將二者中的較小的值插入輔助數(shù)組；（3）重復(fù)直至結(jié)束。smalles

10、tsmallestAGLORHIMSTAGHILM O西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略輔助數(shù)組合并過(guò)程（1）在每一半排序數(shù)組中指向最小元素；（2）將二者中的較小的值插入輔助數(shù)組；（3）重復(fù)直至結(jié)束。smallestsmallestAGLORHIMSTAGHILMO R西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略輔助數(shù)組合并過(guò)程（1）在每一半排序數(shù)組中指向最小元素；（2）將二者中的較小的值插入輔助數(shù)組；（3）重復(fù)直至結(jié)束。first halfexhaustedsmallestAGLORHIMSTAGHILMOR S西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略輔助數(shù)組合并過(guò)程（1）在每

11、一半排序數(shù)組中指向最小元素；（2）將二者中的較小的值插入輔助數(shù)組；（3）重復(fù)直至結(jié)束。first halfexhaustedsmallestAGLORHIMSTAGHILMORS T西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略輔助數(shù)組合并過(guò)程（1）在每一半排序數(shù)組中指向最小元素；（2）將二者中的較小的值插入輔助數(shù)組；（3）重復(fù)直至結(jié)束。first halfexhaustedsecond halfexhaustedAGLORHIMSTAGHILMORST西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略輔助數(shù)組合并過(guò)程（1）在每一半排序數(shù)組中指向最小元素；（2）將二者中的較小的值插入輔助數(shù)組；（3）重

12、復(fù)直至結(jié)束。西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略2.8 快速排序快速排序算法是基于分治策略的另一個(gè)排序算法。基本思想如下：排序子數(shù)組 a p : r ，步驟如下：（1）分解：以 a p 為基準(zhǔn)元素將 a p : r 分成 3 段： a p : q - 1 、 a q 、 a q + 1 : r 。滿足條件： a p : q - 1 中任何一個(gè)元素 = a q 。下標(biāo) q 在劃分過(guò)程中確定。（2）遞歸求解：通過(guò)遞歸調(diào)用快速排序算法分別對(duì) a p : q - 1 和 a q + 1 : r 進(jìn)行排序。（3）合并：對(duì) a p : q - 1 和 a q + 1 : r 的排序在各自的范圍內(nèi)進(jìn)

13、行，因此排好序后不需任何運(yùn)算整個(gè)數(shù)組 a p : r 即完成排序。西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略快速排序算法可遞歸地描述如下：templatevoid QuickSort( Type a, int p, int r ) if ( p r ) int q = Partition( a, p, r ); QuickSort( a, p, q - 1 ); / 對(duì)左半段排序 QuickSort( a, q + 1, r ); / 對(duì)右半段排序 西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略上述算法的關(guān)鍵是函數(shù) Partition ，其功能是以一個(gè)確定的基準(zhǔn)元素 a p 對(duì)子數(shù)組 a p

14、: r 進(jìn)行劃分，它是整個(gè)排序算法的關(guān)鍵：template int Partition( Type a, int p, int r ) int i = p, j = r + 1; Type x = a p ; while( true ) / 將 x 的元素交換到右邊區(qū)域 while( a +i x & i x ); if ( i = j ) break; Swap( a i , a j ); a p = a j ; aj := x; return j; / 返回劃分位置 西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略函數(shù) Partition 的一些說(shuō)明：（1）函數(shù)主要功能是將小于 x 的元素放在

15、原數(shù)組的左半部分，而將大于 x 的元素放在原數(shù)組的右半部分；（2）取 a p 作為基準(zhǔn)可保證算法正常結(jié)束，若選擇 a r 作為劃分基準(zhǔn)，且 a r 又是 a p : r 中的最大元素，則函數(shù)返回的值為 q = r，這樣會(huì)使 QuickSort 陷入死循環(huán)；（3）函數(shù)的計(jì)算時(shí)間復(fù)雜性為 O( r p 1 )。西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略快速排序算法的時(shí)間復(fù)雜性在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的。關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次數(shù)較少（相對(duì)于其他比較類算法速度快）。算法的運(yùn)行

16、時(shí)間與劃分是否對(duì)稱有關(guān)：（1）最壞情況：劃分過(guò)程產(chǎn)生的兩個(gè)區(qū)域分別包含 n 1 和 1 個(gè)元素時(shí)，由于函數(shù) Partition 的計(jì)算時(shí)間為 O( n )，如果算法 Partition 的每一步均出現(xiàn)這種不對(duì)稱劃分，則時(shí)間復(fù)雜性為：注：由于上述劃分的極端情況，QuickSort 中的遞歸僅執(zhí)行了一次，所以上面 T( n 1 ) 的系數(shù)為 1。西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略（2）最好情況：每次劃分所取的基準(zhǔn)都恰好為中值，即每次劃分都產(chǎn)生兩個(gè)大小為 n / 2 的區(qū)域，則時(shí)間復(fù)雜性為：西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略快速排序算法

17、的性能取決于劃分的對(duì)稱性。通過(guò)修改算法 Partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被劃分時(shí)，可以在 a p : r 中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱的。算法如下：templateint RandomizedPartition( Type a, int p, int r ) int i = Random( p, r ); / 產(chǎn)生 p 和 r 之間的一個(gè)隨機(jī)整數(shù) Swap( a i , a p ); / 將隨機(jī)選擇的元素作為劃分基準(zhǔn)元素 return Partition (a, p, r);西安郵電大學(xué)計(jì)算機(jī)學(xué)院第2章 遞歸與分治策略隨機(jī)選擇策略的快速排序算法通過(guò)調(diào)用 RandomizedPartition 來(lái)產(chǎn)生隨機(jī)的劃分：template int RandomizedQuickSort( Type a, int p, int r ) if ( p r ) int q = Randomize