吉林大學(xué)數(shù)據(jù)結(jié)構(gòu)課件第七章排序

1、排 序排序排序：排序指按規(guī)定的順序排列一個(gè)給定對(duì)象集合排序指按規(guī)定的順序排列一個(gè)給定對(duì)象集合中的諸元素中的諸元素 。文件文件: : 它是待排序數(shù)據(jù)對(duì)象的有限集合。它是待排序數(shù)據(jù)對(duì)象的有限集合。記錄記錄：R1，R2，Rn關(guān)鍵詞域關(guān)鍵詞域( (key):): 通常數(shù)據(jù)對(duì)象有多個(gè)屬性域，即多通常數(shù)據(jù)對(duì)象有多個(gè)屬性域，即多個(gè)數(shù)據(jù)成員組成，其中有一個(gè)屬性域可用來(lái)區(qū)分對(duì)個(gè)數(shù)據(jù)成員組成，其中有一個(gè)屬性域可用來(lái)區(qū)分對(duì)象，作為排序依據(jù)。該域即為關(guān)鍵詞域。每個(gè)文件象，作為排序依據(jù)。該域即為關(guān)鍵詞域。每個(gè)文件用哪個(gè)屬性域作為關(guān)鍵詞，要視具體的應(yīng)用需要而用哪個(gè)屬性域作為關(guān)鍵詞，要視具體的應(yīng)用需要而定。即使是同一個(gè)文件

2、表，在解決不同問(wèn)題的場(chǎng)合定。即使是同一個(gè)文件表，在解決不同問(wèn)題的場(chǎng)合也可能取不同的域做關(guān)鍵碼。也可能取不同的域做關(guān)鍵碼。概概 述述主關(guān)鍵詞主關(guān)鍵詞: : 如果在數(shù)據(jù)表中各個(gè)對(duì)象的關(guān)鍵碼互不相同，如果在數(shù)據(jù)表中各個(gè)對(duì)象的關(guān)鍵碼互不相同，這種關(guān)鍵碼即主關(guān)鍵碼。按照主關(guān)鍵碼進(jìn)行排序，排序的這種關(guān)鍵碼即主關(guān)鍵碼。按照主關(guān)鍵碼進(jìn)行排序，排序的結(jié)果是唯一的。結(jié)果是唯一的。次關(guān)鍵詞次關(guān)鍵詞: : 數(shù)據(jù)表中有些對(duì)象的關(guān)鍵碼可能相同，這種關(guān)數(shù)據(jù)表中有些對(duì)象的關(guān)鍵碼可能相同，這種關(guān)鍵碼稱(chēng)為次關(guān)鍵碼。按照次關(guān)鍵碼進(jìn)行排序，排序的結(jié)果鍵碼稱(chēng)為次關(guān)鍵碼。按照次關(guān)鍵碼進(jìn)行排序，排序的結(jié)果可能不唯一?？赡懿晃ㄒ?。概概 述述

3、排序：排序：記錄按關(guān)鍵詞域遞增或遞減的順序排列記錄按關(guān)鍵詞域遞增或遞減的順序排列n個(gè)記錄相應(yīng)的關(guān)鍵詞個(gè)記錄相應(yīng)的關(guān)鍵詞:K1，K2，Kn在關(guān)鍵詞域上定義一個(gè)次序關(guān)系在關(guān)鍵詞域上定義一個(gè)次序關(guān)系“” ，使，使得對(duì)于任意三個(gè)關(guān)鍵詞的取值得對(duì)于任意三個(gè)關(guān)鍵詞的取值a、b、c，下，下列條件成立：列條件成立：在在ab，a=b，ba 三個(gè)可能性中，有且只有一三個(gè)可能性中，有且只有一個(gè)可能性成立（三分率）；個(gè)可能性成立（三分率）；如果如果ab，并且，并且bc，則有，則有ac（傳遞性）（傳遞性）. 這兩個(gè)性質(zhì)顯示了線性次序的數(shù)學(xué)性質(zhì)，也這兩個(gè)性質(zhì)顯示了線性次序的數(shù)學(xué)性質(zhì)，也稱(chēng)作稱(chēng)作全序全序. 概概 述述排序：

4、排序：記錄按關(guān)鍵詞域遞增或遞減的順序排列記錄按關(guān)鍵詞域遞增或遞減的順序排列n個(gè)記錄相應(yīng)的關(guān)鍵詞個(gè)記錄相應(yīng)的關(guān)鍵詞:K1，K2，Kn在關(guān)鍵詞域上定義一個(gè)次序關(guān)系在關(guān)鍵詞域上定義一個(gè)次序關(guān)系“Kj，則稱(chēng)（Ki ，Kj）為上述序列的一個(gè)反序?qū)? 正好是序列K1，K2，Kn的反序?qū)€(gè)數(shù)2njjd K(1) ， K(n) K(1) d1=0,p11=1 K(1) ， K(n) K(1) d1=0,p11=1K(1), K(2) d2=0,p21=1/2K(2) ,K(1) d2=1,p22=1/2K(?), K(?) , K(3) d2=0,p1=1/3K(?) , K(3) ,K(?) d2=1,p2

5、=1/3K(3) , K(?) , K(?) d2=2,p3=1/3 平均情況下平均情況下:若待排序文件中記錄所有可能的排列的概率若待排序文件中記錄所有可能的排列的概率相同，則可取上述最好情況和最壞情況的平相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵詞比較次數(shù)和均情況。在平均情況下的關(guān)鍵詞比較次數(shù)和記錄移動(dòng)次數(shù)分別為記錄移動(dòng)次數(shù)分別為 因此，直接插入排序的時(shí)間復(fù)雜度為因此，直接插入排序的時(shí)間復(fù)雜度為 o(n2)。2(1)(4)14njjnnnd 2(1)(8)(1)(1)4njjnnnnd 最好情況最好情況下，排序前記錄已經(jīng)按關(guān)鍵下，排序前記錄已經(jīng)按關(guān)鍵詞從小到大有序排列，

6、每趟只需與前詞從小到大有序排列，每趟只需與前面的有序部分的最后一個(gè)記錄的關(guān)鍵面的有序部分的最后一個(gè)記錄的關(guān)鍵詞比較詞比較 1 1 次，記錄移動(dòng)次，記錄移動(dòng) 2 2 次，總的次，總的關(guān)鍵詞比較次數(shù)為關(guān)鍵詞比較次數(shù)為 n-1，記錄移動(dòng)次，記錄移動(dòng)次數(shù)為數(shù)為 2(n-1)。最壞情況下最壞情況下:第第 i 趟時(shí)第趟時(shí)第 i 個(gè)記錄前面的所有記錄的關(guān)鍵個(gè)記錄前面的所有記錄的關(guān)鍵詞都比第詞都比第 i 個(gè)記錄的關(guān)鍵詞大，即個(gè)記錄的關(guān)鍵詞大，即dj取最大取最大值，因此必須與前面值，因此必須與前面 i-1個(gè)記錄都做關(guān)鍵詞個(gè)記錄都做關(guān)鍵詞比較，并且每做比較，并且每做 1 次比較就要做次比較就要做 1 次記錄移次記

7、錄移動(dòng)。則總的關(guān)鍵詞比較次數(shù)為動(dòng)。則總的關(guān)鍵詞比較次數(shù)為 221 1)1(22 nndndnjnjjj記錄移動(dòng)次數(shù)為記錄移動(dòng)次數(shù)為 241112 nndnnnjj直接插入排序算法直接插入排序算法優(yōu)點(diǎn)優(yōu)點(diǎn):是算法的執(zhí)行過(guò)程相當(dāng)清晰，并是算法的執(zhí)行過(guò)程相當(dāng)清晰，并 且書(shū)寫(xiě)容易且書(shū)寫(xiě)容易.缺點(diǎn)缺點(diǎn):期望復(fù)雜性為期望復(fù)雜性為O(n2) . 穩(wěn)定性：穩(wěn)定性：直接插入排序是直接插入排序是穩(wěn)定的穩(wěn)定的排序方法。排序方法。最好情況是：最好情況是：當(dāng)被排序文件初態(tài)為正序時(shí)，當(dāng)被排序文件初態(tài)為正序時(shí)，算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為O(n) . 輔助空間：輔助空間： O(1) 一種改進(jìn)的方法是對(duì)半插入法，即在

8、插入第j個(gè)元素時(shí)，不是像直接插人排序那樣順序?qū)ふ也迦氲奈恢茫遣捎脤?duì)半（或二分）的方法 1 2 3 4 5 6 temp1 2 3 4 5 6 temp251 2 3 4 5 6 temp2116希爾排序希爾排序 希爾排序（希爾排序（漸減增量排序法）漸減增量排序法）思想：思想： 把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序法，隨著增量逐漸減少，所分成的組接插入排序法，隨著增量逐漸減少，所分成的組包含的關(guān)鍵詞越來(lái)越多，到增量值減至包含的關(guān)鍵詞越來(lái)越多，到增量值減至1 1時(shí)，整時(shí)，整個(gè)文件恰好被分成一個(gè)組，算法便告終止個(gè)文件恰好被分成一個(gè)組，算法便告

9、終止. . 希爾排序希爾排序增量的取法增量的取法(16條記錄條記錄)： d d1 1= = =8= = =8n/2n/216/216/2d d2 2= = =4= = =4d d1 1/2/2 8/28/2d d3 3= = =2= = =2d d2 2/2/2 4/24/2d d4 4= = =1= = =1d d3 3/2/2 2/22/2 例例 將十個(gè)數(shù)進(jìn)行希爾將十個(gè)數(shù)進(jìn)行希爾排序的示例。排序的示例。 0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9 36 25 48 12 65 25* 43 58 76 32下標(biāo)下標(biāo)d1=525434858127625*36

10、3265 25* 25 48 12 32 36 43 58 76 65一趟一趟排序結(jié)果排序結(jié)果 例例 將十個(gè)數(shù)進(jìn)行希爾將十個(gè)數(shù)進(jìn)行希爾排序的示例。排序的示例。 0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9下標(biāo)下標(biāo)d d2 2=2=2 25* 25 48 12 32 36 43 58 76 6525*48483232434376252512123636585865653243481225 25* 12 32 25 43 36 48 58 76 65二趟二趟排序結(jié)果排序結(jié)果 12 25* 25 32 36 43 48 58 65 76三趟三趟排序結(jié)果排序結(jié)果d d3

11、 3=1=1漸減增量排序算法漸減增量排序算法 7.2 交換排序交換排序 反序?qū)Ψ葱驅(qū)?duì)于序列K1，K2，Kn ，如果1ijn，且KiKj，則稱(chēng)（Ki ，Kj）為上述序列的一個(gè)反序?qū)? 交換排序的思想：交換文件中存在的反序?qū)粨Q排序的思想：交換文件中存在的反序?qū)?冒泡排序、分劃交換排序（快速排序）冒泡排序、分劃交換排序（快速排序）7.2.1 冒泡排序冒泡排序 冒泡排序思想：通過(guò)比較相鄰記錄的關(guān)鍵詞，冒泡排序思想：通過(guò)比較相鄰記錄的關(guān)鍵詞，交換存在逆序的記錄；使關(guān)鍵詞較大的記錄如交換存在逆序的記錄；使關(guān)鍵詞較大的記錄如氣泡一般逐漸往上氣泡一般逐漸往上“飄移飄移”直至直至“水面水面”。 1 2 3

12、4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9算法算法BSort ( R，n ) BS1 冒泡過(guò)程冒泡過(guò)程 FOR i = n TO 2 STEP 1 DO FOR j = 1 TO i1 DO IF Kj Kj+1 THEN ( RjRj+1 ) n 關(guān)鍵詞的比較次數(shù)為關(guān)鍵詞的比較次數(shù)為 (n-1)+(n-2)+1= = (n-1)n/2經(jīng)過(guò)一趟冒泡，可以把具有最大關(guān)鍵詞經(jīng)過(guò)一趟冒泡，可以把具有最大關(guān)鍵詞的記錄移至最后（第的記錄移至最后（第n個(gè)位置）。個(gè)位置）。第第i趟冒泡，把第趟冒泡，把第i大記錄放在第大記錄放在第i個(gè)位置個(gè)位置上。上。做做n

13、-1趟冒泡，就可以對(duì)所有記錄排序。趟冒泡，就可以對(duì)所有記錄排序。發(fā)生一次記錄交換，反序?qū)Φ膫€(gè)數(shù)減少發(fā)生一次記錄交換，反序?qū)Φ膫€(gè)數(shù)減少一個(gè)。一個(gè)。v在掃描過(guò)程中，可在掃描過(guò)程中，可能最后幾趟已無(wú)任能最后幾趟已無(wú)任何交換發(fā)生，程序何交換發(fā)生，程序應(yīng)能做到，一旦發(fā)應(yīng)能做到，一旦發(fā)現(xiàn)某趟掃描中無(wú)任現(xiàn)某趟掃描中無(wú)任何交換時(shí)就會(huì)終止何交換時(shí)就會(huì)終止算法的改進(jìn)算法的改進(jìn)/改進(jìn)的冒泡排序算法改進(jìn)的冒泡排序算法. 算法算法Bubble ( R，n )Bubble1 終止位置初始化終止位置初始化BOUND n Bubble2 冒泡過(guò)程冒泡過(guò)程WHILE BOUND0 DO ( t 0 / t用來(lái)記錄一趟冒泡最后記

14、錄交換的位置用來(lái)記錄一趟冒泡最后記錄交換的位置 FOR j1 TO BOUND 1 DO IF Kj Kj+1 THEN ( RjRj+1 . tj ) . BOUND t ) 冒泡排序演示冒泡排序演示 假定記錄序列假定記錄序列R1，R2，Rn所對(duì)應(yīng)的關(guān)鍵詞序列所對(duì)應(yīng)的關(guān)鍵詞序列為為A = K1，K2，Kn 令令bj（1 j n）表示）表示A中關(guān)鍵詞第中關(guān)鍵詞第 j 小的記錄小的記錄左邊左邊大于它的關(guān)鍵詞的個(gè)數(shù)，則文件大于它的關(guān)鍵詞的個(gè)數(shù)，則文件 b1，b2，bn 稱(chēng)為稱(chēng)為A的的反序表反序表. 經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反序表也會(huì)發(fā)生變化。序表也

15、會(huì)發(fā)生變化。 經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反序表也會(huì)發(fā)生變化。序表也會(huì)發(fā)生變化。 經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反序表也會(huì)發(fā)生變化。序表也會(huì)發(fā)生變化。 經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反序表也會(huì)發(fā)生變化。序表也會(huì)發(fā)生變化。 經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反序表也會(huì)發(fā)生變化。序表也會(huì)發(fā)生變化。 經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反序表也會(huì)發(fā)生變化。序表也會(huì)發(fā)生變化。 經(jīng)過(guò)一趟冒泡后，

16、記錄的位置發(fā)生變化，反經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反序表也會(huì)發(fā)生變化。序表也會(huì)發(fā)生變化。 經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反序表也會(huì)發(fā)生變化。序表也會(huì)發(fā)生變化。afterbefore 經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反序表也會(huì)發(fā)生變化。序表也會(huì)發(fā)生變化。 定理定理7.1 設(shè)設(shè)K1，K2，Kn是序列是序列1，2，n的一個(gè)排列，的一個(gè)排列，b1，b2，bn是對(duì)應(yīng)的反是對(duì)應(yīng)的反序表序表. 如果算法如果算法Bubble的一趟冒泡把的一趟冒泡把K1, K2, Kn改變?yōu)楦淖優(yōu)镵1, K2, Kn, 那么從那么從b

17、1, b2, bn中把中把每個(gè)非零元素減每個(gè)非零元素減1, 就得到了相應(yīng)的反序就得到了相應(yīng)的反序表表b1,b2,bn . 冒泡趟數(shù)：冒泡趟數(shù)：A = 1 + max b1，b2，bn 記錄的初始排列是按關(guān)鍵詞從小到大記錄的初始排列是按關(guān)鍵詞從小到大排好序時(shí)，此算法只執(zhí)行一趟起泡，排好序時(shí)，此算法只執(zhí)行一趟起泡，做做 n-1 次關(guān)鍵詞比較，次關(guān)鍵詞比較，不發(fā)生記錄交換不發(fā)生記錄交換；這是最好的情形。這是最好的情形。最壞的情形是算法執(zhí)行了最壞的情形是算法執(zhí)行了n-1趟起泡，趟起泡，第第 i 趟趟 (1 i n) 做了做了 n- i 次關(guān)鍵詞比較，次關(guān)鍵詞比較，執(zhí)行了執(zhí)行了n-i 次記錄交換。這樣在

18、最壞情次記錄交換。這樣在最壞情形下總的關(guān)鍵詞比較次數(shù)和記錄形下總的關(guān)鍵詞比較次數(shù)和記錄交換次交換次數(shù)數(shù)為：為： (n-1)n/2 推論推論7.1 算法算法Bubble的冒泡的冒泡趟數(shù)趟數(shù)A = 1 + max b1，b2，bn ；記錄交換次數(shù)記錄交換次數(shù)B= bi ；關(guān)鍵詞的比較次數(shù)關(guān)鍵詞的比較次數(shù)C= Ci ，其中，其中Ci等等于第于第i趟冒泡時(shí)的趟冒泡時(shí)的BOUND減減1. 比比較較 交交換換 趟趟數(shù)數(shù) 最最好好 n1 0 1 平平均均 )()ln(21nOnnn ) 1(41nn ) 1 (2/Onn 最最壞壞 ) 1(21nn ) 1(21nn n 冒泡排序算法冒泡排序算法時(shí)間復(fù)雜度時(shí)

19、間復(fù)雜度: :O(n2)（包括最壞和平均）（包括最壞和平均） . . 穩(wěn)定性：穩(wěn)定性：冒泡排序是冒泡排序是穩(wěn)定的穩(wěn)定的排序方法。排序方法。最好情況是：最好情況是：當(dāng)被排序文件初態(tài)為正序時(shí)，當(dāng)被排序文件初態(tài)為正序時(shí)，算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為O(n) . . 空間復(fù)雜度：空間復(fù)雜度： O(1) . . 可以采用氣泡上浮和下沉交替的方法?？梢圆捎脷馀萆细『拖鲁两惶娴姆椒ā?第一趟第一趟第二趟第二趟第三趟第三趟第四趟第四趟79799090909090909090565679797979888888 88 909056568888797979794 488885656565656563232

20、4 4323235353535272732322727323232321616272716162727272788881616353516161616353535354 44 44 4交換任意反序?qū)螅珼 = 的變化? Ki KjK1，Ki-1，Ki，Ki+1 Kj-1，Kj， Kj+1， ，Knd1 ，di-1 ， di，di+1 dj-1， dj， dj+1， ， dn d1 di-1 , dj+1 dn沒(méi)有發(fā)生變化D=D-1+?MAX（ D -D ）2njjd7.2.2 分劃交換排序分劃交換排序 19621962年年HoareHoare提出了快速排序提出了快速排序 (Quick Sort

21、)(Quick Sort)特點(diǎn)：特點(diǎn)：一趟分劃把一個(gè)記錄放在最終的位置一趟分劃把一個(gè)記錄放在最終的位置 上。上。原理：原理：交換反序?qū)粨Q反序?qū)Γ淮斡涗浗粨Q使得文件，一次記錄交換使得文件 中的中的反序?qū)Φ臄?shù)目反序?qū)Φ臄?shù)目減少的更多。減少的更多?？焖倥判虻幕舅枷肟焖倥判虻幕舅枷? :不斷地交換反序?qū)?。不斷地交換反序?qū)ΑＨ稳〈判蛭募腥稳〈判蛭募械哪硞€(gè)記錄的某個(gè)記錄 (例如取第一個(gè)記錄例如取第一個(gè)記錄) 作為基作為基準(zhǔn)，按照該記錄的關(guān)鍵詞大小，將整個(gè)準(zhǔn)，按照該記錄的關(guān)鍵詞大小，將整個(gè)文件劃分為左右兩個(gè)子文件：文件劃分為左右兩個(gè)子文件： 左側(cè)子文件中所有記錄的關(guān)鍵詞都小左側(cè)子文件中所有記

22、錄的關(guān)鍵詞都小于或等于基準(zhǔn)記錄的關(guān)鍵詞于或等于基準(zhǔn)記錄的關(guān)鍵詞 右側(cè)子文件中所有記錄的關(guān)鍵詞都大右側(cè)子文件中所有記錄的關(guān)鍵詞都大于基準(zhǔn)記錄的關(guān)鍵詞于基準(zhǔn)記錄的關(guān)鍵詞基準(zhǔn)記錄則排在這兩個(gè)子文件中間基準(zhǔn)記錄則排在這兩個(gè)子文件中間( (這這也是該記錄最終應(yīng)安放的位置也是該記錄最終應(yīng)安放的位置) )。分別對(duì)兩個(gè)子文件重復(fù)施行上述方法，分別對(duì)兩個(gè)子文件重復(fù)施行上述方法，直到所有的記錄都排在相應(yīng)位置上為止。直到所有的記錄都排在相應(yīng)位置上為止。算法描述算法描述QuickSort ( R ) if ( R的長(zhǎng)度大于的長(zhǎng)度大于1) 將文件將文件R劃分為兩個(gè)子文件劃分為兩個(gè)子文件 LeftR 和和 RightR;

23、 QuickSort ( LeftR );QuickSort ( RightR ); 將兩個(gè)子文件將兩個(gè)子文件 LeftR 和和 RightR 合并為一個(gè)文件合并為一個(gè)文件R; (1) (2) (3) (4) (5) (6) (7) (8) (9)70 73 69 23 93 18 11 68 100 i(第一個(gè)大于第一個(gè)大于) (第一個(gè)小于第一個(gè)小于) j70 6868 69 23 93 18 11 7373 10070 68 69 23 1111 18 9393 73 10070 68 69 23 11 18 93 73 10018 68 69 23 11 70 93 73 100 算法算

24、法QSort（R，m，n） /*對(duì)文件（對(duì)文件（Rm，Rn）進(jìn)行排序）進(jìn)行排序. 我們選擇我們選擇Km作作為控制分劃的關(guān)鍵詞，并假定對(duì)任意的為控制分劃的關(guān)鍵詞，并假定對(duì)任意的min有有KiKn+1 . */QSort1 遞歸出口遞歸出口 IF m n THEN （im . jn+1 . KKm . WHILE i j DO （ii+1 WHILE Ki K DO jj1 . IF i j THEN Ri Rj ) Rm Rj . QSort ( R，m，j1 ) . QSort ( R，j+1，n ) ) 分劃交換排序分劃交換排序演示演示 68 69 23 93 18 11 73 MAX 68

25、 69 23 93 18 11 73 MAXi=5i=5j=8j=8i=1i=1(1) (2) (3) (4) (5) (6) (7) (8) (9)(1) (2) (3) (4) (5) (6) (7) (8) (9) 73 69 23 93 18 11 68 MAX 73 69 23 93 18 11 68 MAXi=2i=2j=8j=8i=2i=2 73 69 23 93 18 11 68 MAX 73 69 23 93 18 11 68 MAX 68 69 23 93 18 11 73 MAX 68 69 23 93 18 11 73 MAXj=8j=8 68 69 23 93 18

26、11 73 MAX 68 69 23 93 18 11 73 MAXi=3i=3j=8j=8 68 69 23 93 18 11 73 MAX 68 69 23 93 18 11 73 MAXi=4i=4j=8j=8 68 69 23 93 18 11 73 MAX 68 69 23 93 18 11 73 MAXi=5i=5j=7j=7 68 69 23 11 18 93 73 MAX 68 69 23 11 18 93 73 MAXi=5i=5j=7j=7 68 69 23 11 18 93 73 MAX 68 69 23 11 18 93 73 MAXi=7i=7j=6j=618 68

27、69 23 11 18 68 69 23 11 93 73 MAX 93 73 MAXim . jn+1 . KKmWHILE i j DO （ii+1 WHILE Ki K DO jj1 . IF i j THEN Ri Rj ) Rm Rj .一趟快速排序一趟快速排序 過(guò)程示例過(guò)程示例: :j=10j=10 18 68 18 68 69 23 1169 23 11 93 7393 73 j=6j=6一趟一趟結(jié)果結(jié)果11 11 69 23 68 69 23 68 93 73 93 73j=2j=2二趟二趟結(jié)果結(jié)果 68 2368 23 93 7393 73 j=5j=5三趟三趟結(jié)果結(jié)果 最終

28、最終結(jié)果結(jié)果多趟快速排序過(guò)程示例多趟快速排序過(guò)程示例 2323 7373 j=8j=8四趟四趟結(jié)果結(jié)果j=4j=4 18 68 18 68 69 23 1169 23 11 93 7393 73 j=6j=6一趟一趟結(jié)果結(jié)果 1111 69 23 6869 23 68 93 7393 73 j=2j=2二趟二趟結(jié)果結(jié)果 68 23 68 23 93 73 93 73j=5j=5三趟三趟結(jié)果結(jié)果 最終最終結(jié)果結(jié)果2323 73 73 j=8j=8四趟四趟結(jié)果結(jié)果j=4j=42 算法算法QSort（R，m，n） IF m Kn THEN Rm+1Rn . IF KmKn THEN RmRn . I

29、F Km+1Km THEN Rm+1Rm . Part2 分劃開(kāi)始分劃開(kāi)始 im jn+1 KKm . Part3 用用Km分劃文件分劃文件( Rm，Rm+1，Rn ) WHILE ij DO ( ii1 WHILE KiK DO ii1 jj1 WHILE KjK DO jj1 . IF ij THEN RiRj ) RmRj 快速排序算法快速排序算法時(shí)間復(fù)雜度時(shí)間復(fù)雜度:O(n:O(n2 2)/)/最壞最壞 . . 時(shí)間復(fù)雜度時(shí)間復(fù)雜度:O(nlog:O(nlog2 2n) /n) /最好和平均最好和平均空間復(fù)雜度空間復(fù)雜度： O(logO(log2 2n) .n) .穩(wěn)定性穩(wěn)定性：快速排

30、序是：快速排序是不穩(wěn)定的不穩(wěn)定的排序方法。排序方法?？焖倥判蚍椒ㄊ悄壳皟?nèi)部排序中最好、最快快速排序方法是目前內(nèi)部排序中最好、最快的排序方法。的排序方法。 7.3 選擇排序選擇排序 思想：思想：對(duì)待排序的文件進(jìn)行對(duì)待排序的文件進(jìn)行n次次選擇選擇，其，其中第中第i次次選擇選擇第第i?。ɑ虼螅┑挠涗浄旁诘谛。ɑ虼螅┑挠涗浄旁诘趇（或（或n-i+1）個(gè)位置上。）個(gè)位置上。 直接選擇排序直接選擇排序 堆排序堆排序7.3.1 直接選擇排序直接選擇排序 1 1 直接選擇排序思想：直接選擇排序思想： 選擇第選擇第i大的記錄大的記錄在剩余的在剩余的n-i+1個(gè)記錄中進(jìn)行一趟個(gè)記錄中進(jìn)行一趟比較，確定出第比較，確

31、定出第i大大記錄記錄，放在第，放在第n-i+1個(gè)位置上。個(gè)位置上。 例如第例如第 i 趟比較（趟比較（i = 0, 1, , n- -2）在前面在前面 n- -i 個(gè)待個(gè)待排序記錄中選出關(guān)鍵碼最大的記錄排序記錄中選出關(guān)鍵碼最大的記錄, 作為有序記錄序列作為有序記錄序列的第的第 i 個(gè)記錄。待到第個(gè)記錄。待到第 n- -2 趟作完，待排序記錄只剩下趟作完，待排序記錄只剩下1個(gè)時(shí)，算法結(jié)束。個(gè)時(shí)，算法結(jié)束。算法算法 SSort（R，n） / 直接選擇排序算法，該算法排序文件（直接選擇排序算法，該算法排序文件（R1，R2，Rn）SS1 排序排序FOR j=n TO 2 STEP 1 DO ( t1

32、. FOR i2 TO j DO IF Kt Ki THEN ti / 找第找第j小元素小元素 / 的下標(biāo)的下標(biāo) RjRt ) / 將將Rt放到第放到第j個(gè)位置上個(gè)位置上 (1) (2) (3) (4) (5) (6)(1) (2) (3) (4) (5) (6) i t 2121 2525 49 25 49 25* * 16 08 16 08 2 1 2 1 初始初始序列序列 2 算法算法 SSort（R，n） FOR j=n TO 2 STEP -1 DO ( t1 . FOR i2 TO j DO IF Kt Ki THEN ti Ri Rt) 21 21 25 25 4949 25 2

33、5* * 16 08 16 08 3 23 2 21 25 21 25 49 49 2525* * 16 08 16 08 4 34 3 21 25 21 25 49 49 25 25* * 1616 08 08 5 35 3 21 25 21 25 49 49 25 25* * 16 16 0808 6 36 3 21 25 08 2521 25 08 25* * 16 16 4949 25 25 0808 25 25* * 16 16 21 25 21 25 49 49 25 25* * 16 16 0808 一趟選擇排序過(guò)程示例一趟選擇排序過(guò)程示例多趟選擇排序過(guò)程示例多趟選擇排序過(guò)程示例

34、 (1) (2) (3) (4) (5) (6)(1) (2) (3) (4) (5) (6)i it t 1 1 21 25 08 25 21 25 08 25* * 16 16 4949 2 2 2 2 21 16 21 16 0808 2525* * 2525 49 49 4 4 3 3 21 16 08 21 16 08 2525* * 25 49 25 49 1 1 5 5 08 08 16 16 2121 2525* * 25 49 25 49 1 1 21 25 49 2521 25 49 25* * 16 08 16 08 3 3 初始初始序列序列 4 4 08 16 08 1

35、6 2121 25 25* * 25 4925 49 2 2 n記錄交換次數(shù)是選擇的趟數(shù)記錄交換次數(shù)是選擇的趟數(shù): n-1.112nn 直接選擇排序算法直接選擇排序算法時(shí)間復(fù)雜度時(shí)間復(fù)雜度:O(n2)（包括最好、最壞和平均）（包括最好、最壞和平均） . 穩(wěn)定性：穩(wěn)定性：不穩(wěn)定的不穩(wěn)定的排序方法。排序方法。空間復(fù)雜度：空間復(fù)雜度： O(1) . 優(yōu)點(diǎn)：優(yōu)點(diǎn)：簡(jiǎn)單、書(shū)寫(xiě)容易簡(jiǎn)單、書(shū)寫(xiě)容易 淘汰賽的思想淘汰賽的思想對(duì)于對(duì)于 n 個(gè)記錄的關(guān)鍵詞，進(jìn)行兩兩比較，個(gè)記錄的關(guān)鍵詞，進(jìn)行兩兩比較，得到得到 n/2 個(gè)比較的優(yōu)勝者個(gè)比較的優(yōu)勝者(關(guān)鍵詞大關(guān)鍵詞大者者)，作為第一步比較的結(jié)果保留下來(lái)。，作為第一步

36、比較的結(jié)果保留下來(lái)。然后對(duì)這然后對(duì)這 n/2 個(gè)記錄再進(jìn)行關(guān)鍵詞的個(gè)記錄再進(jìn)行關(guān)鍵詞的兩兩比較，兩兩比較，如此重復(fù)，直到選出一，如此重復(fù)，直到選出一個(gè)關(guān)鍵詞最大的記錄為止。個(gè)關(guān)鍵詞最大的記錄為止。n-1（15）次）次比較K=94；(16)=64次次比較（14）K=93；(15)=104次次比較（13）K=91；(14)=1 次元素比較次數(shù)次元素比較次數(shù): (n1)+(n1)* log2n nlog2n淘汰賽示意圖淘汰賽示意圖從開(kāi)始尋找最大元素的過(guò)程就是找兄弟結(jié)點(diǎn)和父親結(jié)點(diǎn)的過(guò)程. 從開(kāi)始尋找最大元素的過(guò)程就是找兄弟結(jié)點(diǎn)和父親結(jié)點(diǎn)的過(guò)程. 完全二叉樹(shù)：第i個(gè)元素的左、右兒子分別是第2i和第2i1

37、個(gè)元素，父親結(jié)點(diǎn)是第i/2個(gè)元素. 7.3.2 堆排序堆排序 原理原理 利用淘汰賽的方式尋找當(dāng)前序列利用淘汰賽的方式尋找當(dāng)前序列中的最大記錄中的最大記錄 關(guān)鍵關(guān)鍵 與與當(dāng)前的最大記錄做比較的記錄當(dāng)前的最大記錄做比較的記錄 解決解決 堆堆 完全二叉樹(shù)中的任意非葉結(jié)點(diǎn)的關(guān)鍵詞完全二叉樹(shù)中的任意非葉結(jié)點(diǎn)的關(guān)鍵詞大于等于大于等于它的兩個(gè)兒子結(jié)點(diǎn)的關(guān)鍵詞它的兩個(gè)兒子結(jié)點(diǎn)的關(guān)鍵詞. 我們我們把這樣的數(shù)據(jù)結(jié)構(gòu)稱(chēng)為堆把這樣的數(shù)據(jù)結(jié)構(gòu)稱(chēng)為堆( (極大堆極大堆) )。 極大極大(大根大根)堆堆 極小極小(小根小根)堆堆949375918544511848581034 例例 1 2 3 4 5 6 7 8 9 10

38、 11 12 94 93 75 91 85 44 51 18 48 58 10 34如果數(shù)組如果數(shù)組R中存放了堆，那么中存放了堆，那么R1是最大的記錄，是最大的記錄，將將R1和和Rn交換交換，使得最大記錄放在，使得最大記錄放在Rn的位的位置。置。949375918544511848581034 例例 1 2 3 4 5 6 7 8 9 10 11 12 94 93 75 91 85 44 51 18 48 58 10 34949375918544511848581034 例例 1 2 3 4 5 6 7 8 9 10 11 12 94 93 75 91 85 44 51 18 48 58 10

39、 34349375918544511848581094 例例 1 2 3 4 5 6 7 8 9 10 11 12 34 93 75 91 85 44 51 18 48 58 10 94然后然后對(duì)對(duì)R1，Rn-1進(jìn)行調(diào)整，使它們構(gòu)進(jìn)行調(diào)整，使它們構(gòu)成一個(gè)堆成一個(gè)堆。調(diào)整后，。調(diào)整后，R1是是R1，R2，Rn-1中最大的。然后再交換中最大的。然后再交換R1與與Rn-1 ，使，使R n - 1 中 放 入 次 最 大 的 記 錄 。中 放 入 次 最 大 的 記 錄 。349375918544511848581094 例例 1 2 3 4 5 6 7 8 9 10 11 12 34 93 75 9

40、1 85 44 51 18 48 58 10 94939175488544511834581094 例例 1 2 3 4 5 6 7 8 9 10 11 12 93 91 75 48 85 44 51 18 34 58 10 94109175488544511834589394 例例 1 2 3 4 5 6 7 8 9 10 11 12 10 91 75 48 85 44 51 18 34 58 93 94109175488544511834589394 例例 1 2 3 4 5 6 7 8 9 10 11 12 10 91 75 48 85 44 51 18 34 58 93 94再對(duì)再對(duì)R

41、1，R2，Rn-2進(jìn)行調(diào)整，使之進(jìn)行調(diào)整，使之成為新堆，再進(jìn)行類(lèi)似的交換和調(diào)整，反復(fù)進(jìn)行，成為新堆，再進(jìn)行類(lèi)似的交換和調(diào)整，反復(fù)進(jìn)行，直到調(diào)整范圍只剩下一個(gè)記錄直到調(diào)整范圍只剩下一個(gè)記錄R1為止。此時(shí)為止。此時(shí)R1是是n個(gè)記錄中最小的，且數(shù)組個(gè)記錄中最小的，且數(shù)組Rn中的記錄中的記錄已經(jīng)按從小到大排列了。已經(jīng)按從小到大排列了。堆排序算法的粗略描述如下：堆排序算法的粗略描述如下： （l）建立包含）建立包含Kl，K2，Kn的堆；的堆； （2）FOR in TO 2 STEP 1 DO （RlRi 重建包含重建包含Kl，K2，Ki1的堆）的堆） 堆排序堆排序:若在輸出堆頂?shù)淖畲笾抵?，使得剩余若在?/p>

42、出堆頂?shù)淖畲笾抵?，使得剩余n1個(gè)元素的序列重又建成一個(gè)堆，則得到個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元個(gè)元素中的次大值。如此反復(fù)執(zhí)行，便能得到一個(gè)有素中的次大值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列。序序列。 堆排序需解決的兩個(gè)問(wèn)題：堆排序需解決的兩個(gè)問(wèn)題： 如何建堆；如何建堆； 輸出堆頂元素后，如何調(diào)整新堆。輸出堆頂元素后，如何調(diào)整新堆。重建堆重建堆R1與與Ri交換后，只有交換后，只有R1與其左右兒子不與其左右兒子不滿足堆的性質(zhì)滿足堆的性質(zhì).如果根結(jié)點(diǎn)的兒子存在，則比較根和兩個(gè)兒如果根結(jié)點(diǎn)的兒子存在，則比較根和兩個(gè)兒子的關(guān)鍵詞子的關(guān)鍵詞.如果根結(jié)點(diǎn)的關(guān)鍵詞大，則說(shuō)明該如果根結(jié)點(diǎn)的關(guān)鍵詞大，

43、則說(shuō)明該結(jié)構(gòu)已經(jīng)是堆，終止重建過(guò)程結(jié)構(gòu)已經(jīng)是堆，終止重建過(guò)程. 如果根結(jié)點(diǎn)的關(guān)鍵詞小，則它和關(guān)鍵詞大如果根結(jié)點(diǎn)的關(guān)鍵詞小，則它和關(guān)鍵詞大的兒子進(jìn)行交換，并以這個(gè)兒子為根結(jié)點(diǎn)的兒子進(jìn)行交換，并以這個(gè)兒子為根結(jié)點(diǎn)繼續(xù)重建下去繼續(xù)重建下去. 10917548854451183458939410917548854451183458939410917548854451183458939491107548854451183458939491107548854451183458939491107548854451183458939491857548104451183458939491857548584451

44、1834109394算法算法Restore（R，f，e）/重重 建堆建堆R1 初始化初始化 jf R2 建堆建堆 WHILE j e/2 DO (IF(2j e)AND(K2j Kj THEN（RmRj . jm ） ELSE je ）重建堆演示重建堆演示 2 2 初始建堆初始建堆: :將序號(hào)為將序號(hào)為 n/2 , n/2-1 ,1的結(jié)點(diǎn)的結(jié)點(diǎn)作為根的子樹(shù)都調(diào)整為堆即可。作為根的子樹(shù)都調(diào)整為堆即可。 例例 關(guān)鍵字序列關(guān)鍵字序列（42,13,91,23,24,16,05,88)42,13,91,23,24,16,05,88)。42139123241605884213912324160588421

45、3918824160523421391882416052342889113241605234288911324160523428891232416051342889123241605139188422324160513初始建堆過(guò)程：初始建堆過(guò)程：91884223241605134213918824160523堆排序過(guò)程：堆排序過(guò)程：4288912324160513918842232416051342889123241605139188422324160513428891232416051313884223241605914288912324160513138842232416059142889

46、123241605138813422324160591428891232416051388134223241605914288912324160513882442231316059142889123241605138824422313160591428891232416051388244223131605914288912324160513052442231316889142889123241605134224162313058891堆排序過(guò)程：堆排序過(guò)程：4288912324160513052416231342889142889123241605132423160513428891堆排序過(guò)程

47、：堆排序過(guò)程：42889123241605134224162313058891堆排序過(guò)程：堆排序過(guò)程：428891232416051324231605134288914288912324160513132316052442889142889123241605132313160524428891堆排序過(guò)程：堆排序過(guò)程：428891232416051323131605244288914288912324160513051316232442889142889123241605131613052324428891堆排序過(guò)程：堆排序過(guò)程：428891232416051316130523244288914

48、288912324160513051316232442889142889123241605131305162324428891堆排序過(guò)程：堆排序過(guò)程：42889123241605131305162324428891428891232416051305131623244288914288912324160513051316232442889105 13 16 23 24 42 88 91算法算法HeapSort ( R，n ) / 堆排序算法堆排序算法 HS1 初始建堆初始建堆 FOR i n2 TO 1 STEP 1 DO Restore（R，i，n） HS2 排序排序 FOR in TO 2

49、 STEP 1 DO ( R1Ri . Restore ( R，1，i1 ) ) 堆排序演示堆排序演示堆排序算法堆排序算法時(shí)間復(fù)雜度時(shí)間復(fù)雜度: :O(nlogO(nlog2 2n)n)（包括最好、最壞和平（包括最好、最壞和平均）均） . . 穩(wěn)定性：堆排序是穩(wěn)定性：堆排序是不穩(wěn)定的不穩(wěn)定的排序方法。排序方法?？臻g復(fù)雜度：空間復(fù)雜度： O(1) . O(1) . 7.4 7.4 合并排序合并排序合并：合并：把兩個(gè)或多個(gè)有序文件組成一個(gè)單一的把兩個(gè)或多個(gè)有序文件組成一個(gè)單一的 有序文件。有序文件。兩個(gè)文件的合并。兩個(gè)文件的合并。 3 合并排序。合并排序。開(kāi)始開(kāi)始25574837129286332

50、5,5737,4812,9233,86第一次第一次合并合并25,37,48,5712,33,86,92第二次第二次合并合并12,25,33,37,48,57,86,92第三次第三次合并合并合并排序過(guò)程示例合并排序過(guò)程示例 假定文件（假定文件（Rt，Rt1，Rm）和文件）和文件（Rm1，Rn）都已經(jīng)排序，如何合并這兩）都已經(jīng)排序，如何合并這兩個(gè)文件，得到排序好的大文件（個(gè)文件，得到排序好的大文件（Xt，Xt1，Xn）；）； 執(zhí)行合并過(guò)程，將文件執(zhí)行合并過(guò)程，將文件R中長(zhǎng)度為中長(zhǎng)度為length的的所有子文件合并到文件所有子文件合并到文件X中；中；兩個(gè)有序文件合并成一個(gè)大的有序文件兩個(gè)有序文件合并

51、成一個(gè)大的有序文件 算法算法Merge (R，t，m，n . X)算法算法Merge()演示演示 M1 初始化給每個(gè)文件一個(gè)頭指針初始化給每個(gè)文件一個(gè)頭指針 it jm1 k1 M2 比較比較 i和和 j所指記錄所指記錄 WHILE（im） AND（jn） DO （IF KiKjTHEN（XkRi ii1）ELSE（XkRj jj1）. kk+1）. M3 復(fù)制余留記錄項(xiàng)復(fù)制余留記錄項(xiàng) WHILE (im) Xk =Ri . ii1. kk+1. WHILE (jn) Xk =Rj . jj1. kk+1. t mm+1 nijXk兩個(gè)有序文件合并成一個(gè)大的有序文件兩個(gè)有序文件合并成一個(gè)大的有

52、序文件 算法算法Merge (R，t，m，n . X)算法算法Merge()演示演示 M1 初始化給每個(gè)文件一個(gè)頭指針初始化給每個(gè)文件一個(gè)頭指針 it jm1 k1 M2 比較比較 i和和 j所指記錄所指記錄 WHILE（im） AND（jn） DO （IF KiKjTHEN（XkRi ii1）ELSE（XkRj jj1）. kk+1）. M3 復(fù)制余留記錄項(xiàng)復(fù)制余留記錄項(xiàng) WHILE (im) Xk =Ri . ii1. kk+1. WHILE (jn) Xk =Rj . jj1. kk+1. it mm+1 njXk 算法算法Merge (R，t，m，n. X) ： 假定文件假定文件（Rt

53、，Rt1，Rm）和文件（）和文件（Rm1，Rn）都已經(jīng)排序，該算法合并這兩個(gè)文件后得）都已經(jīng)排序，該算法合并這兩個(gè)文件后得到排序好的大文件（到排序好的大文件（Xt，Xt1，Xn）；）；算法算法MPass（R，n，1engthX） /* 一趟合并算法，該算法執(zhí)行一趟合并過(guò)程，將文一趟合并算法，該算法執(zhí)行一趟合并過(guò)程，將文件件R中長(zhǎng)度為中長(zhǎng)度為length的所有子文件合并到文件的所有子文件合并到文件X中，中，n是是R的記錄個(gè)數(shù)的記錄個(gè)數(shù) */MP1 初始化初始化 i1 MP2 合并相鄰的兩個(gè)長(zhǎng)度為合并相鄰的兩個(gè)長(zhǎng)度為length的子文件的子文件 WHILE i n 2*length + 1 DO

54、（Merge（R，i，ilengthl，i2*length1X）. ii2*length ） MP3 處理余留的長(zhǎng)度小于處理余留的長(zhǎng)度小于2*length的子文件的子文件 IF i+length1 n THEN Merge（R，i，i+length1，n. X） ELSE FOR j = i TO n DO XjRj 1 . 1+length-11+length 1+2length-1i算法算法MPass（R，n，1engthX） /* 一趟合并算法，該算法執(zhí)行一趟合并過(guò)程，將文一趟合并算法，該算法執(zhí)行一趟合并過(guò)程，將文件件R中長(zhǎng)度為中長(zhǎng)度為length的所有子文件合并到文件的所有子文件合并到

55、文件X中，中，n是是R的記錄個(gè)數(shù)的記錄個(gè)數(shù) */MP1 初始化初始化 i1 MP2 合并相鄰的兩個(gè)長(zhǎng)度為合并相鄰的兩個(gè)長(zhǎng)度為length的子文件的子文件 WHILE i n 2*length + 1 DO （Merge（R，i，ilengthl，i2*length1X）. ii2*length ） MP3 處理余留的長(zhǎng)度小于處理余留的長(zhǎng)度小于2*length的子文件的子文件 IF i+length1 n THEN Merge（R，i，i+length1，n. X） ELSE FOR j = i TO n DO XjRj 1 . 1+length-11+length 1+2length-1i 算

56、法算法MPass（R，n，lengthX）：一趟合并）：一趟合并算法，該算法執(zhí)行一趟合并過(guò)程，將文件算法，該算法執(zhí)行一趟合并過(guò)程，將文件R中長(zhǎng)中長(zhǎng)度為度為length的所有子文件合并到文件的所有子文件合并到文件X中，中，n是是R的記錄個(gè)數(shù)，該函數(shù)調(diào)用的記錄個(gè)數(shù)，該函數(shù)調(diào)用Merge()函數(shù)；函數(shù)；算法算法MSort(R，n) / 直接兩路合并排序算法，X是輔助文件，其記錄結(jié)構(gòu)與R相同MS1 初始化 length1 MS2 交替合并 WHILE length n DO （MPass（R，n，lengthX）. length2*length MPass（X，n，lengthR）. length2*

57、length） 算法算法Merge (R，t，m，n. X) ： 假定文件假定文件（Rt，Rt1，Rm）和文件（）和文件（Rm1，Rn）都已經(jīng)排序，該算法合并這兩個(gè)文件后得）都已經(jīng)排序，該算法合并這兩個(gè)文件后得到排序好的大文件（到排序好的大文件（Xt，Xt1，Xn）；）； 算法算法Merge()演示演示 算法算法MPass（R，n，lengthX）：一趟合并）：一趟合并算法，該算法執(zhí)行一趟合并過(guò)程，將文件算法，該算法執(zhí)行一趟合并過(guò)程，將文件R中長(zhǎng)中長(zhǎng)度為度為length的所有子文件合并到文件的所有子文件合并到文件X中，中，n是是R的記錄個(gè)數(shù)，該函數(shù)調(diào)用的記錄個(gè)數(shù)，該函數(shù)調(diào)用Merge()函數(shù)；

58、函數(shù)；算法算法MPass()演示演示 算法算法MSort(R，n) ：該函數(shù)調(diào)用函數(shù)該函數(shù)調(diào)用函數(shù)Mpass(),Mpass(),直接兩路合并排序，直接兩路合并排序，X是輔助文件；是輔助文件；合并排序合并排序MSort(R，n) 演示演示 合并排序。合并排序。開(kāi)始開(kāi)始255748371292863325,5737,4812,9233,86第一次第一次合并合并25,37,48,5712,33,86,92第二次第二次合并合并12,25,33,37,48,57,86,92第三次第三次合并合并合并排序過(guò)程示例合并排序過(guò)程示例合并趟數(shù)：第一趟，合并長(zhǎng)度為1的n個(gè)文件；第二趟，合并長(zhǎng)度小于等于2的個(gè)文件；第 i 趟，合并長(zhǎng)度小于等于2i-1的文件，得到的文件長(zhǎng)度大于2i-1 ，且小于等于2i. 如果存在正整數(shù)k，使得2kn2k+1，合并排序共需要k+1趟合并(log