2022-02巖數(shù)據(jù)結(jié)構(gòu)講義第6章排序2010秋

1、數(shù)據(jù)結(jié)構(gòu)與算法Data Structrues and Algorithms哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2012-1-4Slide 6-2學(xué)習(xí)目標(biāo)掌握排序的基本概念和常用術(shù)語熟練掌握排序、排序；氣泡排序、快速排序；選擇排序、堆排序；歸并排序；基數(shù)排序的基本、排序過程和算法實(shí)現(xiàn)。、算法原理掌握各種排序算法的性能及其分析方法，以及各種排序方法的比較和選擇等。2012-1-4Slide 6-3本章主要內(nèi)容基本概念氣泡排序快速排序直接選擇排序堆排序6.6（直接）排序6.7排序（二路）歸并排序基數(shù)排序本章小結(jié)2012-1-4Slide 6-46.1 基本概念排序（sorting）也稱分類：假設(shè)給定一組n個(gè)序

2、列r1, r2, , rn，其相應(yīng)的關(guān)鍵字序列為k1, k2, , kn。排序是將這些排列成順序?yàn)閞s1, rs2, , rsn的一個(gè)序列，使得相應(yīng)的關(guān)鍵字的值滿足ks1ks2ksn（稱為升序）或ks1ks2ksn（稱為降序）。排序的目的：方便查詢和處理。排序算法的穩(wěn)定性：假定在待排序的集中，存在多個(gè)具有相同關(guān)鍵字值的，若經(jīng)過排序，這些的相對次序仍然保持不變，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。2012-1-4Slide 6-56.1 基本概念（cont.）排序分類：按照排序時(shí)排序?qū)ο蟠娣诺脑O(shè)備，分為，排序

3、:排序過程中數(shù)據(jù)對象全部在內(nèi)存中的排序。外部排序:排序過程數(shù)據(jù)對象并非完全在內(nèi)存中的排序按照排序是的基本操作是否基于關(guān)鍵字的比較？分為,基于比較：基本操作關(guān)鍵字的比較和的移動(dòng)時(shí)間下限已經(jīng)被證明為（nlog2n）。，其交換排序（氣泡、快速排序）；選擇排序（直接選擇、堆排序）；排序（直接、折半、排序）、歸并排序（二路歸并排序）。不基于比較：根據(jù)根據(jù)組成關(guān)鍵字的的分量及其分布特征，如基數(shù)排序。2012-1-4Slide 6-66.1 基本概念（cont.）排序算法的性能：基本操作。內(nèi)排序在排序過程中的基本操作：比較：關(guān)鍵碼之間的比較；移動(dòng)：從一個(gè)位置移動(dòng)到另一個(gè)位置。輔助輔助空間?？臻g是指在數(shù)據(jù)規(guī)模

4、一定的條件下，除了存放待排序的其他額外占用的空間?？臻g之外，執(zhí)行算法所需要算法本身的復(fù)雜度。2012-1-4Slide 6-76.1 基本概念（cont.）結(jié)構(gòu)：排序算法及其從操作角度看，排序是線性結(jié)構(gòu)的一種操作，待排序記錄可以用順序結(jié)構(gòu)或結(jié)構(gòu)。假定采用順序結(jié)構(gòu)：structrecords keytypekey ;fieldsother ;；typedef Sort（records LISTmaxsize ;n , LIST &A）:對n個(gè)的數(shù)組按照關(guān)鍵字不減的順序進(jìn)行排序。2012-1-4Slide 6-86.2 氣泡排序算法的基本將待排序的：看作是豎著排列的“氣泡”，關(guān)鍵字較小的比較輕，從

5、而要往上浮。對這個(gè)“氣泡”序列進(jìn)行n-1遍（趟）處理。所謂一遍（趟）處理，就是自底向上檢查一遍這個(gè)序列，并注意兩個(gè)相比較的關(guān)鍵字的順序是否正確。如果發(fā)現(xiàn)順序不對，即 “輕”的在下面，就交換它們的位置。顯然，處理1遍之后，“最輕”的就浮到了最置；處理2遍之后，“次輕”的二遍處理時(shí)，由于最就浮到了次置。在作第已是“最輕”的，所置上的以不必檢查。一般地，第i遍處理時(shí)，不必檢查第i置以上的的關(guān)鍵字，因?yàn)榻?jīng)過前面i-1遍的處理，它們已正確地排好序。2012-1-4Slide 6-96.2 氣泡排序（cont.）算法的實(shí)現(xiàn)：void BubbleSort (n , LIST&A )for (for (i

6、=1; i = i+1; j- )if ( Aj.key Aj-1 )swap (Aj, Aj-1)void swap(records &x, records &y)recordsw = x ;w ;x = y ;y = w ; 2012-1-4Slide 6-106.2 氣泡排序（cont.）算法（時(shí)間）性能分析：最好情況（正序）：比較次數(shù)：n-1移動(dòng)次數(shù)：0時(shí)間復(fù)雜度： O(n)；情況（反序）：n-1比較次數(shù)：(n-i) n (n 1)2i 1n-13(n-i) 3n(n 1)移動(dòng)次數(shù)：2i 1時(shí)間復(fù)雜度： O(n2)；空間復(fù)雜度： O(1)。平均情況：時(shí)間復(fù)雜度為O(n2)。2012-1

7、-4Slide 6-116.3 快速排序快速算法是對氣泡排序的改進(jìn)，改進(jìn)的著眼點(diǎn)：在氣泡排序中，的比較和移動(dòng)是在相鄰單元中進(jìn)行的，每次交換只能上移或下移一個(gè)單元，因而總的比較次數(shù)和移動(dòng)次數(shù)較多。2012-1-4Slide 6-12較大從前面直接移動(dòng)到后面較小從后面直接移動(dòng)到前面增大的比較和移動(dòng)距減少總的比較次數(shù)和移動(dòng)次6.3 快速排序（cont.）：算法的基本是C.R.A.Hoare 1962年一種劃分交換排序。采用的是分治策略(一般與遞歸技術(shù)結(jié)合使用)，以減少排序過程中的比較次數(shù)。通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按此方

8、法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。分治法的基本分解(劃分): 將原問題分解為若干個(gè)與原問題相似的子問題；求解: 遞歸地求解子問題。若子問題的規(guī)模足夠小，則直接求解組合: 將每個(gè)子問題的解組原問題的解。2012-1-4Slide 6-136.3 快速排序（cont.）算法的實(shí)現(xiàn)步驟：設(shè)被排序的無序區(qū)為Ai,Aj1. 基準(zhǔn)元素選?。哼x擇其中的一個(gè)元素(控制關(guān)鍵字);(怎么選擇？)的關(guān)鍵字v 作為基準(zhǔn)2. 劃分：通過基準(zhǔn)元素v 把無序區(qū)Ai,Aj劃分成左、的關(guān)鍵字都小于v ；右邊的右兩部分，使得左邊的各的關(guān)鍵字都大于等于v ；(如何劃分？)各遞

9、歸求解：重復(fù)(1)(2)，分別對左邊和右邊部分遞歸地進(jìn)行快速排序；組合：左、右兩部分均有序，整個(gè)序列有序。2012-1-4Slide 6-1431415926536.3 快速排序（cont.）基準(zhǔn)元素的選?。夯鶞?zhǔn)元素的選取是任意的，但不同的影響很大；對算法性能一般原則：是每次都能將表劃分為規(guī)模相等的兩部分（最佳情況）。此時(shí)，劃分次數(shù)為log2n，全部比較次數(shù)nlog2n，交換次數(shù)(n/6)log2n 。設(shè) FindPivot( i , j)是求Ai.key,Aj.key的基準(zhǔn)元素 v=Ak，返回其下標(biāo)k 。v =(Ai.key，A(i+j)/2.key, Aj.key的中值 )v =從Ai.k

10、ey到Aj.key 最先找到的兩個(gè)不同關(guān)鍵字中的最大者。（若Ai.key,Aj.key之中至少有兩個(gè)關(guān)字不相同）優(yōu)點(diǎn)：若無兩個(gè)關(guān)鍵字不同，則Ai到Aj已有序，排序結(jié)束。2012-1-4Slide 6-1531415926536.3 快速排序（cont.）FindPivot(i,j ) /* 設(shè)A是外部數(shù)組 */*若Ai,Aj的關(guān)鍵字全部相同，則返回0；否則，左邊兩個(gè)不同關(guān)鍵字中的較大者的下標(biāo)。*/keytypek ;for ( k=i+1 ;key = Ai.key ; /* 第1個(gè)關(guān)鍵字的值A(chǔ)i.key */*從左到右查找不同的關(guān)鍵字 */kreturnkey ) /* 選擇較大的關(guān)鍵字 *

11、/k ;else if ( Ak.key return i ;key )return 0 ;2012-1-4Slide 6-1631415926536.3 快速排序（cont.）無序區(qū)劃分（分割）：設(shè)被排序的無序區(qū)為Ai,Aj(1) 掃描:令游標(biāo) l 從左端(初始時(shí)l = i )開始向右掃描，越過關(guān)鍵字小于v 的所有，直到遇到Al.keyv；又令游標(biāo) r 從右端(初始時(shí) r = j )開始向左掃描，越過關(guān)鍵字大于等于v 的所有，直到遇到Ar.keyv；測試l 和 r：若l r, 即 l= r +1)轉(zhuǎn)(4)交換：交換Al 和Ar，轉(zhuǎn)( 1 )；(目的是使 l 和 r 都至少向其前進(jìn)方向前進(jìn)一步

12、)此時(shí)Ai,Aj被劃分成為滿足條件的兩部分Ai,Al -1和Al ,Aj。2012-1-4Slide 6-1731415926536.3 快速排序（cont.）Partition (i ,j , keytypvot )/*劃分Ai,Aj，是關(guān)鍵字 pivot 的在序列，關(guān)鍵字pivot 的在右子序列，返回有子序列的起始下標(biāo)*/t l , r ; dofor( l = i ; Al.key = pivot ; r-)if( l r ) swap(Al,Ar); while( l = r );；returnl ;2012-1-4Slide 6-1831415926536.3 快速排序（cont.）

13、快速排序的實(shí)現(xiàn)：/*對外部數(shù)組A 的元素Ai,Aj進(jìn)行快速排序*/void QuickSort (i ,j )keytypvot;k; /關(guān)鍵字大于等于pivot的pivotindex ; /關(guān)鍵字為pivot的 pivotindex = FindPivot ( i , j );在序列中的起始下標(biāo)在數(shù)組A中的下標(biāo)if( pivotindex != 0 ) /遞歸終止條件pivot=Apivotindex.key; k=Partition ( i , j , pivot ); QuickSort ( i , k-1);QuickSort ( k , j );/對數(shù)組A1,An進(jìn)行快速排序可調(diào)用Q

14、uickSort(1,n)實(shí)現(xiàn)2012-1-4Slide 6-196.3 快速排序（cont.）v =3示例v =2v =5v =4v =9v =62012-1-4Slide 6-201123345569655956543396554332114593653136.3 快速排序（cont.）快速排序（時(shí)間）性能分析最好情況：每一次劃分后，劃分點(diǎn)的左側(cè)子表與右側(cè)子表的長度同，則有，為O(nlog2n)。T(n)2T(n/2)n2(2T(n/4)n/2)n4T(n/4)2n4(2T(n/8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n)時(shí)間復(fù)雜度為O(nlog2n)空間復(fù)

15、雜度為O(log2n)2012-1-4Slide 6-216.3 快速排序（cont.）快速排序（時(shí)間）性能分析情況：每次劃分只得到一個(gè)比上一次劃分少一個(gè)（另一個(gè)子序列長度為1），則有的子序n1 1 2 1) O ( n2 )nin( n（）i 1時(shí)間復(fù)雜度為O(n2)空間復(fù)雜度為O(n)2012-1-4Slide 6-226.3 快速排序（cont.）快速排序（時(shí)間）性能分析平均情況：快速排序的遞歸執(zhí)行過程可以用遞歸樹描述。例如，序列 38, 27, 55, 50, 13, 49, 65的快速排序遞歸如下:385013552749時(shí)間復(fù)雜度為O(nlog2n)空間復(fù)雜度為O(log2n)65

16、2012-1-4Slide 6-236.4 直接選擇排序算法的基本選擇排序的主要操作是選擇，其主要是：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵字值最?。ㄗ畲螅┑募拥接行蛐蛄兄?。，添序列進(jìn)行n-1遍的處理，直接選擇排序，對待排序的1遍處理是將A1n中最小者與A1交換位置，第2遍處是將A2n中最小者與A2交換位置， ，第i遍處理是將Ain中最小者與Ai交換位置。這樣，經(jīng)過i遍處理之后，前i個(gè)的位置就已經(jīng)按從小到大的順序排列好了。直接選擇排序與氣泡排序的區(qū)別在：氣泡排序每次比較后，如果發(fā)現(xiàn)順序不對立即進(jìn)行交換，而選擇排序不立即進(jìn)行交換，而是找出最小關(guān)鍵字后再進(jìn)行交換。2012-1-4Slide 6-246

17、.4 直接選擇排序（cont.）n, LIST A )算法的實(shí)現(xiàn)voidSelectSort (keytype lowkey;/當(dāng)前最小關(guān)鍵字i, j，lowindex; /當(dāng)前最小關(guān)鍵字的下標(biāo)for(i=1; in; i+) /在Ain中選擇最小的關(guān)鍵字，與Ai交換lowindex = i ; lowkey = Ai.key ;for ( j = i+1; j=n; j+)if (Aj.keylowkey) /用當(dāng)前最小關(guān)鍵字與每個(gè)關(guān)鍵字比較lowkey=Aj ;lowindex = j ;swap(Ai, Alowindex) ; 2012-1-4Slide 6-256.4 直接選擇排序（

18、cont.）性能分析移動(dòng)次數(shù)：最好情況（正序）：0次情況：3(n-1)次比較次數(shù)：n1 1 2 1) O ( n2 )nin( n（）i 1時(shí)間復(fù)雜度為O(n2)。空間復(fù)雜度為O(1)。2012-1-4Slide 6-266.5 堆排序堆排序是對直接選擇排序的改進(jìn)，改進(jìn)的著眼點(diǎn)：如何減少關(guān)鍵字之間的比較次數(shù)。若能利用每趟比較后的結(jié)果，也就是在找出關(guān)鍵字值最小的同時(shí)，也找出關(guān)鍵字值較小的，則可減少后面的選擇中所用的比較次數(shù)，從而提高整個(gè)排序過程的效率。2012-1-4Slide 6-27查找最小值的同時(shí)，找出較小減少關(guān)鍵字之間的比較次6.5 堆排序（cont.）堆的定義把具有如下性質(zhì)的數(shù)組A表示

19、的完全二叉樹稱為（最?。┒眩?1) 若2*i n ，則Ai.key A2*i.key ;(2) 若2*i+1 n ，則Ai.key A2*i+1.key 。把具有如下性質(zhì)的數(shù)組A表示的完全二叉樹稱為（最大）堆:(1) 若2*i n，則Ai.key A2*i.key ;(2) 若2*i+1 n，則Ai.key A2*i+1.key 。12最小3最大3946552012-1-4Slide 6-286.5 堆排序（cont.）堆的性質(zhì)對于任意一個(gè)非葉結(jié)點(diǎn)的關(guān)鍵字，都不大于其左、右兒子結(jié)點(diǎn)的關(guān)鍵字。即Ai/2.keyAi.key1 i/2 i n。在堆中，以任意結(jié)點(diǎn)為根的仍然是堆。特別地，每個(gè)葉也點(diǎn)也

20、可視為堆。每個(gè)結(jié)點(diǎn)都代表(是)一個(gè)堆。以堆（的數(shù)量）不斷擴(kuò)大的方式進(jìn)行初始建堆。在堆中（包括各小的。去掉堆中對應(yīng)的堆），其根結(jié)點(diǎn)的關(guān)鍵字是最最大的葉結(jié)點(diǎn)后，仍然是堆。以堆的規(guī)模逐漸縮小的方式進(jìn)行堆排序。2012-1-4Slide 6-296.5 堆排序（cont.）：堆排序的基本首先將待排序的序列用完全二叉樹表示；然后完全二叉樹構(gòu)造成一個(gè)堆，此時(shí)，選出了堆中所有記錄關(guān)鍵字的最小者；最后將關(guān)鍵字最小者從堆中移走，并將剩余的再調(diào)整成堆，這樣又找出了次小的關(guān)鍵字，以此類推，直到堆中只有一個(gè)。排表整2012-1-4Slide 6-30堆(初建堆)按關(guān)鍵字有的序列完全二叉樹待排序序6.5 堆排序（con

21、t.）堆排序的實(shí)現(xiàn)步驟：結(jié)構(gòu)A表示把待排序的序列用完全二叉樹的數(shù)組初始建堆：把數(shù)組所對應(yīng)的完全二叉樹以堆不斷擴(kuò)大的方式整理成堆。令 i= n/2,2,1并分別把以n/2 ,2,1 為根的完全二叉樹整理成堆，即執(zhí)行算法PushDown ( i , n )。堆排序：令i = n, n-1 , 2交換：把堆頂元素(當(dāng)前最小的)與位置 i(當(dāng)前最大的葉結(jié)點(diǎn)下標(biāo))的元素交換，即執(zhí)行swap(A1,Ai)；整理:把剩余的 i-1個(gè)元素整理成堆，即執(zhí)行PushDown(1 , i-1)；重復(fù)執(zhí)行完這一過程之后，則A1,A2,An是按關(guān)鍵字不增順序的有序序列。2012-1-4Slide 6-316.5 堆排序

22、（cont.）堆排序的實(shí)現(xiàn)：void HeapSort (n , LIST A )i;for( i=n/2; i=1; i+) PushDown( i, n);for( i=n; i=2; i-) /*初始建堆，從最右非葉結(jié)點(diǎn)開始*/*整理堆，把以i為根，最大下標(biāo)的葉為n*/swap(A1,Ai); /堆頂與當(dāng)前堆中的下標(biāo)最大的葉結(jié)點(diǎn)交換PushDown( 1, i-1 );/*整理堆把以1為根，最大葉下標(biāo)為i-1的完全二整理成堆*/2012-1-4Slide 6-326.5 堆排序（cont.）整理堆算法：PushDown(, last)把以A為根，以Alast為最右邊葉結(jié)點(diǎn)的完全二叉樹整理

23、成堆。根據(jù)堆的定義，它要完成的功能是，把完全二中的關(guān)鍵字最小的元素放到堆頂，而把原堆頂元素下推到適當(dāng)?shù)奈恢?，?A,Alast)成為堆。那么，怎樣把關(guān)鍵字最小的元素放到堆頂，把堆頂元素下推到適當(dāng)位置呢？具體操作(要點(diǎn))如下：把完全二的根或者的根與其左、右兒子比較如果它比其左右兒子大，則與其中較小者交換（若、右兒子相等，則與其左兒子交換）。重復(fù)上述過程直到以APushDown(為根的完全二, last)算法實(shí)現(xiàn)如下：是堆為止。2012-1-4Slide 6-336.5 堆排序（cont.）void PushDown(,last)/*整理堆:A是外部數(shù)組,把A下推到完全二的適當(dāng)位置*/*/r=;

24、/* r是被下推到的適當(dāng)位置，初始值為根while(rA2*r.key)swap(Ar,A2*r);/*下推*/r=last; /*Ar.key小于等于A2*r.key或者大于，交換后到葉，循環(huán)結(jié)束*/ else if(Ar.keyA2*r.key)&(A2*r.keyA2*r+1.key)&(A2*r+1.keylast/2， 即 i log2(last/)-1。所以while循環(huán)體最多執(zhí)行l(wèi)og2(last/ O(log(last/)次，即PushDown時(shí)間復(fù)雜度)=O( log2n )。所以，HeapSort時(shí)間復(fù)雜度： O( log2n )。這是堆排序的最好、和平均的時(shí)間代價(jià)。Hea

25、pSort空間復(fù)雜度： O( 1 )。2012-1-4Slide 6-376.6 （直接）：排序算法的基本排序的主要操作是，其基本是：每次將一個(gè)待排序的按其關(guān)鍵字的大小到一個(gè)已經(jīng)排好序的有序序列中，直到全部排好序?yàn)橹?。?jīng)過i-1遍處理后，A1i-1己排好序。第i遍處理僅將AiA1i-1,i的適當(dāng)位置，使得A1i又是排好序的序列。要達(dá)到這個(gè)目的，可以用順序比較的方法。首先比較 Ai和Ai-1的關(guān)鍵字，如果Ai-1.keyAi.key，由于 A1i已排好序，第i遍處理就結(jié)束了；否則交換Ai與 Ai-1的位置，繼續(xù)比較Ai-1和Ai-2的關(guān)鍵字，直到找到某一個(gè)位置j(1ji-1)，使得Aj.keyA

26、j+1.key時(shí)為止。2012-1-4Slide 6-386.6 （直接）算法的實(shí)現(xiàn)排序（cont.）voidInsertSort (i, j ;n, LIST A )A0.key = - ;/哨兵for(i=1; i=n; i+) j=i;while(Aj.key=1; d=d/2) for (i=d+1; i0 & A0.key Aj.key) Aj+d= Aj; /后移d個(gè)位置j=j-d;/比較同一子序列的前一個(gè)Aj+d= A0; 2012-1-4Slide 6-446.7算法的性能分析排序分組排序（cont.）排序開始時(shí)增量較大，每個(gè)子序列中的個(gè)數(shù)較少，從而排序速度較快；當(dāng)增量較小時(shí)，

27、雖然每個(gè)子序列中個(gè)數(shù)較多，但整個(gè)序列已基本有序，排序速度也較快。排序算法的時(shí)間性能是所取增量的函數(shù)，而到目前為止尚未有人求得一種最好的增量序列。研究表明，排序的時(shí)間性能在O(n2)和O(nlog2n)之間當(dāng)n在某個(gè)特定范圍內(nèi)，排序所需的比較次數(shù)和的移動(dòng)次數(shù)約為O(n1.3 ) 。2012-1-4Slide 6-456.8 （二路）歸并排序歸并排序歸并：將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)有序序列的過程。歸并排序的主要操作是歸并，其主要是：將若干有序序列逐步歸并，最終得到一個(gè)有序序列。如何將兩個(gè)有序序列一個(gè)有序序列？（二路歸并基礎(chǔ)）設(shè)相鄰的按關(guān)鍵字有序序列為As Am和Am+1 At，歸并成一個(gè)

28、按關(guān)鍵字有序序列Bs Btsmm+1tA jistB k2012-1-4Slide 6-466.8 （二路）歸并排序（cont.）void Merge (s ,m ,t , LIST A , LIST B)/*將有序序列As,Am和Am+1,At合并為一個(gè)有序序列 Bs,Bt*/i = s ; j = m+1 , k = s ;/置初值/* 兩個(gè)序列非空時(shí)，取小者輸出到Bk上 */ while ( i = m & j = t )Bk+ = ( A i .key = A j .key) ? Ai+ : Aj+ ;/* 若第一個(gè)子序列非空(未處理完)，則剩余部分到B */while ( i = m

29、 )Bk+ = Ai+ ;/* 若第二個(gè)子序列非空(未處理完)，則剩余部分到B */while ( j = t )Bk+ = Aj+ ;/*時(shí)間復(fù)雜度：O( ts1 )；空間復(fù)雜度：O( ts1 ) */2012-1-4Slide 6-476.8 （二路）歸并排序（cont.）二路歸并排序的基本（自底向上的非遞歸算法）將一個(gè)具有n個(gè)待排序序序列；的序列看成是n個(gè)長度為1的有然后進(jìn)行兩兩歸并，得到n/2 個(gè)長度為2的有序序列；再進(jìn)行兩兩歸并，得到n/4個(gè)長度為4的有序序列；，直至得到1個(gè)長度為n的有序序列為止。26 5 1577 126177 77 61 11 111161 1559 15591

30、559 61 48 19 191948 265#48 # 1 155111115152619592661487759 196148 77 *2012-1-4Slide 6-486.8 （二路）歸并排序（cont.）怎樣完成一趟歸并？/*把A中長度為 h 的相鄰序列歸并成長度為 2h 的序列*/void MergePass (n ,h , LIST A , LIST B)i , t ;for ( i=1 ; i+2*h-1= n ; i+=2*h )Merge(i, i+h-1, i+2*h-1, A, B) ;/歸并長度為h的兩個(gè)有序子序列if ( i+h-1 n )/* 尚有兩個(gè)子序列，其中

31、最后一個(gè)長度小于 h*/Merge( i, i+h-1, n , A, B) ;/* 歸并最后兩個(gè)子序列 */else /* 若i= n 時(shí)，則剩余一個(gè)子序列輪空，直接for ( t= i ; t= n ; t+ ) Bt = At ; /* Mpass */*/2012-1-4Slide 6-496.8 （二路）歸并排序（cont.）（二路）歸并排序算法：如何控制二路歸并的結(jié)束？void MergeSort (n , LIST A )/* 二路歸并排序 */h = 1 ;/* 當(dāng)前歸并子序列的長度，初始為1 */LIST B ;while (h n)MergePass (n , h , A

32、, B) ;h = 2*h ;MergePass (n , h , B , A) ; /* A、B互換位置 */h = 2*h ;/* MergeSort */2012-1-4Slide 6-50開始時(shí),有序序列的長度h=1;結(jié)束時(shí),有序序列的長度h=n,用有序序列的長度來控制排序的結(jié)束.6.8 （二路）歸并排序（cont.）（二路）歸并排序算法性能分析時(shí)間性能：一趟歸并操作是將A1An中相鄰的長度為h的有序序列進(jìn)行兩兩歸并，并把結(jié)果存放到B1Bn中，這需要O(n)時(shí)間。整個(gè)歸并排序需要進(jìn)行l(wèi)og2n趟，因此，總的時(shí)間代價(jià)是O(nlog2n)。這是歸并排序算法的最好、平均的時(shí)間性能?？臻g性能：

33、算法在執(zhí)行時(shí)，需要占用與原始儲空間，因此空間復(fù)雜度為O(n)。序列同樣數(shù)量的2012-1-4Slide 6-516.8 （二路）歸并排序（cont.）（二路）歸并排序分治算法算法的基本分解：將當(dāng)前待排序的序列Alow, , Ahigh一分為點(diǎn) mid = ( low + high ) / 2 ；二，即求求解：遞歸地對序列 Alow, , Amid和Amid+1,Ahigh進(jìn)行歸并排序；組合：將兩個(gè)已排序子序列歸并為一個(gè)有序序列。遞歸的終止條件是子序列長度為 1，因?yàn)橐粋€(gè)算法實(shí)現(xiàn)自然有序。2012-1-4Slide 6-526.8 （二路）歸并排序（cont.）（二路）歸并排序分治算法算法實(shí)現(xiàn)v

34、oid MergeSort ( LIST A , LIST B ,low ,high )/* 用分治法對Alow, , Ahigh進(jìn)行二路歸并 */mid = (low+high)/2 ;if (low0 */ MergeSort (A , B , low , mid) ;MergeSort (A , B , mid+1 , high) ; Merge (low , mid , hight , A , B) ;/* MergeSort */2012-1-4Slide 6-536.9 基數(shù)排序多關(guān)鍵字排序理論上可以證明，對于基于關(guān)鍵字之間比較的排序，無論用什么方法都至少需要進(jìn)行l(wèi)og2n!次比較

35、。由Stirling公式可知，log2n! nlog2n-1.44n+O(log2n)。所以基于關(guān)鍵字比較的排序時(shí)間的下界是O(nlog2n)。因此不存在時(shí)間復(fù)雜性低于此下界的基于關(guān)鍵字比較的排序!只有不通過關(guān)鍵字比較的排序方法,才有可能突破此下界。基數(shù)排序（時(shí)間復(fù)雜性可達(dá)到線性級O(n)不比較關(guān)鍵字的大小，而根據(jù)關(guān)鍵字的每個(gè)分量的值，排列順序的方法，稱為分配法排序（基數(shù)排序）。而把關(guān)鍵字各個(gè)分量所有可能的取值范圍的最大值稱為基數(shù)或桶或箱，因此基數(shù)排序又稱為桶排序?；鶖?shù)排序的適用范圍：顯然，要求關(guān)鍵字分量的取值范圍必須是有限的，否則可能要無限的箱。2012-1-4Slide 6-546.9 基

36、數(shù)排序多關(guān)鍵字排序（cont.）算法的基本設(shè)待排序的序列的關(guān)鍵字都是位相同的整數(shù)（不相同時(shí),取位數(shù)的最大值），其位數(shù)為figure，每個(gè)關(guān)鍵字可以各自含有figure個(gè)分量，每個(gè)分量的值取值范圍為0,1,9即基數(shù)為10。依次從低位考查，每個(gè)分量。首先把全部數(shù)據(jù)裝入一個(gè)隊(duì)列A，然后按下列步驟進(jìn)行: 1.初態(tài):設(shè)置10個(gè)隊(duì)列，分別為Q0,Q1,Q9，并且均為空2.分配:依次從隊(duì)列中取出每個(gè)數(shù)據(jù)data；第pass遍處時(shí)，考查data.key右起第pass位數(shù)字，設(shè)其為r，把data取盡A，則全部數(shù)據(jù)被分配到Q0,Q1,Q9.隊(duì)列Qr，3.收集:從Q0開始，依次取出Q0,Q1,Q9中的全部數(shù)據(jù)排隊(duì)A

37、。，并按照取出順序，把每個(gè)數(shù)據(jù)4.重復(fù)1,2,3步，對于關(guān)鍵字中有figure位數(shù)字的數(shù)據(jù)進(jìn)行figure遍處理，即到按關(guān)鍵字有序的序列。2012-1-4Slide 6-556.9 基數(shù)排序多關(guān)鍵字排序（cont.）算法示例：321986123432543018765678987789098890109901210012890901012210109321210901012109432 012018 321018 098123 310 321 432 543 678 76572012-1-4Slide 6-56Q0:012018098Q1:109123 Q2:210Q3:321Q4:432Q5

38、:543Q6:678 Q7:765789 Q8:890Q9: 90198698789890 901 986987Q0:901109Q1:210012018Q2:321123 Q3:432Q4:543Q5:Q6:765Q7:678 Q8:986 987 789Q9:890 098123 543 765 986987018678098789019123 432 543 765678986987 789890098Q0:890210Q1:321901Q2:432012Q3:123543 Q4:Q5:765Q6:986Q7:987Q8:018678098Q9:7891096.9 基數(shù)排序多關(guān)鍵字排序（

39、cont.）算法實(shí)現(xiàn)：voidRadixSort(figure, QUEUE &A)QUEUE Q10; records data ;/*求整數(shù) k 的第 p 位*/pass, r, i ;for ( pass=1; pass=figure ; pass+ ) for ( i=0 ; i=9 ; i+ ) /*置空隊(duì)列*/MAKENULL( Qi ) ;while ( !EMPTY( A ) )/* 分配 */ data = FRONT ( A ) ; DEQUEUE ( A );r = Radix(data.key, pass) ; ENQUEUE( data , Qr ) ; Radix (k,p)er= 1 ;i=1; i=p-1 ; i+ )for (er =er * 10 ;return ( k%(er*10)/er) ;for ( i=0 ; i =9 ; i+ ) /* 收集 */ while ( !EMPTY( Qi ) ) data = FRONT ( Qi ) ; DEQUEUE( Qi ) ;for (i=0;inext=Q2.front-next; Q1.rear=Q2.rear;Q1Q22012-1-4Slide 6-586.9