數(shù)據(jù)結(jié)構(gòu)排序技術(shù)

1、第八章 排序技術(shù)本章的基本內(nèi)容是：排序的基本概念插入排序交換排序選擇排序概 述 排序：給定一組記錄的集合r1, r2, , rn，其相應(yīng)的關(guān)鍵碼分別為k1, k2, , kn，排序是將這些記錄排列成順序為rs1, rs2, , rsn的一個序列，使得相應(yīng)的關(guān)鍵碼滿足ks1ks2ksn（稱為升序）或ks1ks2ksn（稱為降序）。正序：待排序序列中的記錄已按關(guān)鍵碼排好序。逆序（反序）：待排序序列中記錄的排列順序與排好序的順序正好相反。排序的基本概念排序算法的穩(wěn)定性：假定在待排序的記錄集中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，即在原序列中，ki=kj且ri在rj

2、之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。 概 述 排序的基本概念學(xué)號姓名高數(shù)英語思想品德0001王 軍85880002李 明64920003湯曉影8586687278概 述 排序的基本概念單鍵排序：根據(jù)一個關(guān)鍵碼進行的排序；多鍵排序：根據(jù)多個關(guān)鍵碼進行的排序。學(xué)號姓名高數(shù)英語思想品德0001王 軍85880002李 明64920003湯曉影8586687278按學(xué)號排序單鍵排序按成績（高數(shù)英語思想品德）排序多鍵排序概 述 排序的基本概念設(shè)關(guān)鍵碼分別為k1, k2, , km，多鍵排序有兩種方法： 依次對記錄進行m次排序，第一次按k1排序，第二次按

3、k2排序，依此類推。這種方法要求各趟排序所用的算法是穩(wěn)定的； 將關(guān)鍵碼k1, k2, , km分別視為字符串依次首尾連接在一起，形成一個新的字符串，然后，對記錄序列按新形成的字符串排序。多鍵排序單鍵排序排序的分類1. 內(nèi)排序：在排序的整個過程中，待排序的所有記錄全部被放置在內(nèi)存中2. 外排序：由于待排序的記錄個數(shù)太多，不能同時放置在內(nèi)存，而需要將一部分記錄放置在內(nèi)存，另一部分記錄放置在外存上，整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。概 述 排序的基本概念排序的分類1. 基于比較：基本操作關(guān)鍵碼的比較和記錄的移動，其最差時間下限已經(jīng)被證明為（nlog2n）。 2. 不基于比較

4、：根據(jù)關(guān)鍵碼的分布特征。概 述 排序的基本概念基于比較的內(nèi)排序1. 插入排序2. 交換排序3. 選擇排序4. 歸并排序1. 基本操作。內(nèi)排序在排序過程中的基本操作：比較：關(guān)鍵碼之間的比較；移動：記錄從一個位置移動到另一個位置。 2. 輔助存儲空間。輔助存儲空間是指在數(shù)據(jù)規(guī)模一定的條件下，除了存放待排序記錄占用的存儲空間之外，執(zhí)行算法所需要的其他存儲空間。3.算法本身的復(fù)雜程度。 排序算法的性能概 述 排序算法的存儲結(jié)構(gòu)概 述 從操作角度看，排序是線性結(jié)構(gòu)的一種操作，待排序記錄可以用順序存儲結(jié)構(gòu)或鏈接存儲結(jié)構(gòu)存儲。假定2：將待排序的記錄序列排序為升序序列。 int rn+1; /待排序記錄存儲在

5、r1rn，r0留做他用假定1：采用順序存儲結(jié)構(gòu)，關(guān)鍵碼為整型，且記錄只有關(guān)鍵碼一個數(shù)據(jù)項。插入排序插入排序的主要操作是插入，其基本思想是：每次將一個待排序的記錄按其關(guān)鍵碼的大小插入到一個已經(jīng)排好序的有序序列中，直到全部記錄排好序為止?；舅枷耄涸诓迦氲?i（i1）個記錄時，前面的 i-1個記錄已經(jīng)排好序。 直接插入排序插入排序有序序列無序序列r1r2ri-1rirnri+1r1r2ri-1rirnri+1基本思想：在插入第 i（i1）個記錄時，前面的 i-1個記錄已經(jīng)排好序。 （1）如何構(gòu)造初始的有序序列？（2）如何查找待插入記錄的插入位置?直接插入排序插入排序需解決的關(guān)鍵問題?直接插入排序過

6、程示例 r 0 1 2 3 4 5 6211825221025*212125插入排序i = 218221025*25i = 318221025*2225222110252115102525*2521151025*252118151018181025*i = 418i = 61825*i = 5r0的作用?暫存單元監(jiān)視哨解決方法：將第1個記錄看成是初始有序表，然后從第2個記錄起依次插入到這個有序表中，直到將第n個記錄插入。插入排序關(guān)鍵問題(1)如何構(gòu)造初始的有序序列？算法描述：for (i=2; i=n; i+) 插入第i個記錄，即第i趟直接插入排序；關(guān)鍵問題(2)如何查找待插入記錄的插入位置?

7、解決方法：在i-1個記錄的有序區(qū)r1 ri-1中插入記錄ri，首先順序查找ri的正確插入位置，然后將ri插入到相應(yīng)位置。r0有兩個作用：1. 進入循環(huán)之前暫存了ri的值，使得不致于因記錄的后移而丟失ri的內(nèi)容；2. 在查找插入位置的循環(huán)中充當(dāng)哨兵。插入排序算法描述：r0=ri; j=i-1; while (r0rj) rj+1=rj; j-;void insertSort (int r , int n) for (i=2; i=n; i+) r0=ri; j=i-1; while (r0=ri-1，內(nèi)層循環(huán)會出現(xiàn)什么情況?直接插入排序算法性能分析最好情況下（正序）： 插入排序12345時間復(fù)雜

8、度為O(n)。比較次數(shù)：n-1移動次數(shù)：2(n-1) 123451234512345123452345直接插入排序算法性能分析插入排序最好情況下（正序）： 比較次數(shù)：n-1移動次數(shù)：2(n-1) 最壞情況下（逆序或反序）： 時間復(fù)雜度為O(n2)。54321453213452123451123454321比較次數(shù)：移動次數(shù)：2)1)(2(2-+=nnini2)1)(4(1-+=+nnin2=i）（時間復(fù)雜度為O(n)。平均情況下（隨機排列）： 直接插入排序算法性能分析插入排序時間復(fù)雜度為O(n2)。比較次數(shù)：移動次數(shù)：4)1)(4(-+=nnn2=i4)1)(2(2-+=nnnii2（21+i

9、）空間性能：需要一個記錄的輔助空間。直接插入排序算法是一種穩(wěn)定的排序算法。直接插入排序算法性能分析插入排序直接插入排序算法簡單、容易實現(xiàn)，適用于待排序記錄基本有序或待排序記錄較小時。當(dāng)待排序的記錄個數(shù)較多時，大量的比較和移動操作使直接插入排序算法的效率降低。插入排序如何改進直接插入排序?注意到，在插入第 i（i1）個記錄時，前面的 i-1 個記錄已經(jīng)排好序，則在尋找插入位置時，可以用折半查找來代替順序查找，從而較少比較次數(shù)。請同學(xué)們寫出這個改進的直接插入排序算法，并分析時間性能。希爾排序改進的著眼點：（1）若待排序記錄按關(guān)鍵碼基本有序時，直接插入排序的效率可以大大提高；（2）由于直接插入排序算

10、法簡單，則在待排序記錄數(shù)量n較小時效率也很高。 插入排序（1）應(yīng)如何分割待排序記錄，才能保證整個序列逐步向基本有序發(fā)展？（2）子序列內(nèi)如何進行直接插入排序？插入排序需解決的關(guān)鍵問題?基本思想：將整個待排序記錄分割成若干個子序列，在子序列內(nèi)分別進行直接插入排序，待整個序列中的記錄基本有序時，對全體記錄進行直接插入排序。希爾排序基本有序：接近正序，例如1, 2, 8, 4, 5, 6, 7, 3, 9；局部有序：部分有序，例如6, 7, 8, 9, 1, 2, 3, 4, 5。局部有序不能提高直接插入排序算法的時間性能。 插入排序希爾排序分割待排序記錄的目的?1. 減少待排序記錄個數(shù)；2. 使整個

11、序列向基本有序發(fā)展。 子序列的構(gòu)成不能是簡單地“逐段分割”，而是將相距某個“增量”的記錄組成一個子序列。 啟示?希爾插入排序過程示例 1 2 3 4 5 6 7 8 94021254925*16初始序列插入排序300813d = 44021254925*16300813252125*300849131640d = 21325210825*16304940252125*300813164049d = 10825211325*16304049082513162125*403049解決方法：將相隔某個“增量”的記錄組成一個子序列。增量應(yīng)如何取？希爾最早提出的方法是d1=n/2，di+1=di/2。關(guān)

12、鍵問題(1)應(yīng)如何分割待排序記錄？插入排序算法描述：for (d=n/2; d=1; d=d/2) 以d為增量，進行組內(nèi)直接插入排序；解決方法：在插入記錄ri時，自ri-d起往前跳躍式（跳躍幅度為d）搜索待插入位置，并且r0只是暫存單元，不是哨兵。當(dāng)搜索位置0，表示插入位置已找到。在搜索過程中，記錄后移也是跳躍d個位置。在整個序列中，前d個記錄分別是d個子序列中的第一個記錄，所以從第d+1個記錄開始進行插入。插入排序關(guān)鍵問題(2)子序列內(nèi)如何進行直接插入排序？算法描述：for (i=d+1; i0 & r0rj) rj+d=rj; /記錄后移d個位置 j=j-d; /比較同一子序列的前一個記錄

13、 rj+d=r0; 插入排序關(guān)鍵問題(2)子序列內(nèi)如何進行直接插入排序？希爾排序算法的時間性能希爾排序算法的時間性能是所取增量的函數(shù)，而到目前為止尚未有人求得一種最好的增量序列。研究表明，希爾排序的時間性能在O(n2)和O(nlog2n)之間。當(dāng)n在某個特定范圍內(nèi)，希爾排序所需的比較次數(shù)和記錄的移動次數(shù)約為O(n1.3 ) 。 插入排序希爾排序開始時增量較大，每個子序列中的記錄個數(shù)較少，從而排序速度較快；當(dāng)增量較小時，雖然每個子序列中記錄個數(shù)較多，但整個序列已基本有序，排序速度也較快。 課堂練習(xí)：1. 欲將序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的關(guān)鍵碼按

14、字母升序重排，則初始步長為4的希爾排序一趟的結(jié)果是？答：原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shell一趟后：2. 以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，分別寫出執(zhí)行以下算法的各趟排序結(jié)束時，關(guān)鍵字序列的狀態(tài)，并說明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實現(xiàn)？ 直接插入排序 希爾排序（取dk=5,3,1）P,Q,R,A,D,H,C,F,M,S,X ,Y答：顯然，直接插入排序方法易于在鏈表上實現(xiàn)；但希爾排序方法因為是按增量選擇記錄，不易于在鏈表上實現(xiàn)。 交換排序的主要

15、操作是交換，其主要思想是：在待排序列中選兩個記錄，將它們的關(guān)鍵碼相比較，如果反序（即排列順序與排序后的次序正好相反），則交換它們的存儲位置。 交換排序反序則 交換rirj起泡排序基本思想：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。 rj rj+1 ri+1 rn-1 rn 無序區(qū) 有序區(qū) 1ji-1 已經(jīng)位于最終位置反序則交換交換排序05981269385381起泡排序過程示例 交換排序059812693853810598126938538105981269385381交換排序Flag=1;for(i=1;in&flag;i+) flag=0; for(j=1;jrj+

16、1)flag=1;ri-rj+1因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，因此要在排序過程中設(shè)置一個標(biāo)志flag判斷元素是否進行過交換。從而減少不必要的比較。起泡排序的時間性能分析最好情況（正序）：交換排序比較次數(shù)：n-1移動次數(shù)：0 12345時間復(fù)雜度為O(n)。12345最壞情況（反序）：起泡排序的時間性能分析最好情況（正序）：交換排序比較次數(shù)：n-1移動次數(shù)：0 54321時間復(fù)雜度為O(n)；時間復(fù)雜度為O(n2)。43215321452134512345比較次數(shù)：移動次數(shù)：2)1(1-=nn(n-i)n-1i2)1(1-=n3n3(

17、n-i)n-1i平均情況：時間復(fù)雜度為O(n2)。快速排序的基本思想首先選一個軸值（即比較的基準(zhǔn)），通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠?，前一部分記錄的關(guān)鍵碼均小于或等于軸值，后一部分記錄的關(guān)鍵碼均大于或等于軸值，然后分別對這兩部分重復(fù)上述方法，直到整個序列有序。交換排序如何選擇軸值？如何實現(xiàn)分割（稱一次劃分）？如何處理分割得到的兩個待排序子序列？如何判別快速排序的結(jié)束？需解決的關(guān)鍵問題?選擇軸值的方法：1.使用第一個記錄的關(guān)鍵碼；2.選取序列中間記錄的關(guān)鍵碼；3.比較序列中第一個記錄、最后一個記錄和中間記錄的關(guān)鍵碼，取關(guān)鍵碼居中的作為軸值并調(diào)換到第一個記錄的位置；4.隨機選取軸值。交換

18、排序關(guān)鍵問題：如何選擇軸值？選取不同軸值的后果：決定兩個子序列的長度，子序列的長度最好相等。13652750384955ji1338652750495513652750493855交換排序關(guān)鍵問題：如何實現(xiàn)一次劃分？jjiiijijjj解決方法：設(shè)待劃分的序列是rs rt，設(shè)參數(shù)i，j分別指向子序列左、右兩端的下標(biāo)s和t，令rs為軸值，（1）j從后向前掃描，直到rjri，將rj移動到ri的位置，使關(guān)鍵碼?。ㄍS值相比）的記錄移動到前面去；（2）i從前向后掃描，直到rirj，將ri移動到rj的位置，使關(guān)鍵碼大（同軸值比較）的記錄移動到后面去；（3）重復(fù)上述過程，直到i=j。交換排序關(guān)鍵問題：如何

19、實現(xiàn)一次劃分？交換排序關(guān)鍵問題：如何實現(xiàn)一次劃分？算法描述：int Partition(int r , int first, int end) i=first; j=end; /初始化 while (ij) while (ij & ri= rj) j-； /右側(cè)掃描 if (ij) rirj; i+; /將較小記錄交換到前面 while (ij & ri= rj) i+； /左側(cè)掃描 if (ij) rjri; j-; /將較大記錄交換到后面 retutn i; /i為軸值記錄的最終位置解決方法：對分割得到的兩個子序列遞歸地執(zhí)行快速排序。交換排序關(guān)鍵問題：如何處理分割得到的兩個待排序子序列？

20、1327386550495513275038495565ijij算法描述：交換排序關(guān)鍵問題：如何處理分割得到的兩個待排序子序列？ void QuickSort (int r , int first, int end ) pivotpos = Partition (r, first, end ); /一次劃分 QuickSort (r, first, pivotpos-1); /對前一個子序列進行快速排序 QuickSort (r, pivotpos+1, end ); /對后一個子序列進行快速排序解決方法：若待排序列中只有一個記錄，顯然已有序，否則進行一次劃分后，再分別對分割所得的兩個子序列進

21、行快速排序（即遞歸處理）。 交換排序關(guān)鍵問題：如何判別快速排序的結(jié)束？ void QuickSort (int r , int first, int end )/在序列 firstend中遞歸地進行快速排序 if (first end) pivotpos = Partition (r, first, end ); QuickSort (r, first, pivotpos-1); QuickSort (r, pivotpos+1, end ); 算法描述：交換排序關(guān)鍵問題：如何判別快速排序的結(jié)束？ 交換排序例：38, 27, 55, 50, 13, 49, 65的快速排序遞歸樹如下：38135

22、055496527快速排序的遞歸執(zhí)行過程可以用遞歸樹描述。快速排序的時間性能分析快速排序的時間性能分析交換排序快速排序的時間性能快速排序遞歸的深度每次劃分軸值的選取最好情況：每一次劃分對一個記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)?？焖倥判虻臅r間性能分析交換排序T(n)2T(n/2)n 2(2T(n/4)n/2)n4T(n/4)2n 4(2T(n/8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n)最壞情況：每次劃分只得到一個比上一次劃分少一個記錄的子序列（另一個子序列為空），為 O(n2)。最好情況：每一次劃分對一個記錄定位后，該記錄的左

23、側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)?？焖倥判虻臅r間性能分析交換排序平均情況：為O(nlog2n)。)()1(21211nOnninni=-=-=）（選擇排序的主要操作是選擇，其主要思想是：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小的記錄，添加到有序序列中。 選擇排序有序序列r1r2ri-1rirnrk無序序列rnri+1r1r2ri-1riri交換最小記錄簡單選擇排序基本思想：第i 趟在n-i+1（i=1,2,n-1）個記錄中選取關(guān)鍵碼最小的記錄作為有序序列中的第i個記錄。 選擇排序需解決的關(guān)鍵問題?如何在待排序序列中選出關(guān)鍵碼最小的記錄？如何確定待排序序列中關(guān)鍵碼最小的記錄在有序

24、序列中的位置？ 簡單選擇排序示例0821i = 2最小者 08交換21,08最小者 16交換25,16最小者 21交換49,212128i = 12516490808i = 32108284921選擇排序28491625161625i = 4最小者 25交換25,28i = 5最小者 28不交換選擇排序簡單選擇排序示例492108281625254921081628252849210816282528無序區(qū)只有一個記錄解決方法：設(shè)置一個整型變量index，用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。 選擇排序關(guān)鍵問題：如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？212825164908indexi

25、ndexindex08算法描述：index=i; for (j=i+1; j=n; j+) if (rjrindex) index=j;解決方法：設(shè)置一個整型變量index，用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。 關(guān)鍵問題：如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？解決方法：第i趟簡單選擇排序的待排序區(qū)間是ri rn，則ri是無序區(qū)第一個記錄，所以，將index所記載的關(guān)鍵碼最小的記錄與ri交換。選擇排序關(guān)鍵問題：如何確定最小記錄的最終位置？算法描述： if (index!=i) ririndex; void selectSort ( int r , int n) for ( i=1; i

26、n; i+) index=i; for (j=i+1; j=n; j+) if (rjrindex) index=j; if (index!=i) ririndex; 簡單選擇排序算法選擇排序簡單選擇排序算法的性能分析移動次數(shù)：最好情況（正序）：0次選擇排序12345123451234512345123451234最壞情況：3(n-1)次簡單選擇排序算法的性能分析移動次數(shù)：最好情況（正序）：0次選擇排序空間性能：需一個輔助空間。穩(wěn)定性：是一種穩(wěn)定的排序算法。45231152341253412354123451234比較次數(shù)：)()1(21211nOnninni=-=-=）（簡單選擇排序的時間復(fù)

27、雜度為O(n2)。堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值（稱為小根堆），或每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值（稱為大根堆）。選擇排序182032364525385040281. 小根堆的根結(jié)點是所有結(jié)點的最小者。2. 較小結(jié)點靠近根結(jié)點，但不絕對。堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值（稱為小根堆），或每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值（稱為大根堆）。選擇排序503845402836322018281. 大根堆的根結(jié)點是所有結(jié)點的最大者。2. 較大結(jié)點靠近根結(jié)點，但不絕對。堆和序列的關(guān)系選擇排序

28、將堆用順序存儲結(jié)構(gòu)來存儲，則堆對應(yīng)一組序列。5038454028363220182850 38 45 32 36 40 28 20 18 281 2 3 4 5 6 7 8 9 10采用順序存儲基本思想：首先將待排序的記錄序列構(gòu)造成一個堆，此時，選出了堆中所有記錄的最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個記錄。 選擇排序堆排序需解決的關(guān)鍵問題?如何由一個無序序列建成一個堆（即初始建堆）？如何處理堆頂記錄？如何調(diào)整剩余記錄，成為一個新堆（即重建堆）？ 堆調(diào)整堆調(diào)整：在一棵完全二叉樹中，根結(jié)點的左右子樹均是堆，如何調(diào)整根結(jié)點，使整個完

29、全二叉樹成為一個堆？選擇排序283632161825321618253628void sift ( int r , int k, int m )/要篩選結(jié)點的編號為k，堆中最后一個結(jié)點的編號為m i=k; j=2*i; while (j=m ) /篩選還沒有進行到葉子 if (jm & rjrj) break; else ri rj; i=j; j=2*i; 選擇排序堆調(diào)整算法描述：選擇排序關(guān)鍵問題：如何由一個無序序列建成一個堆？282516321836163216282518362532162818362528323628161825算法描述：for (i=n/2; i=1; i-) sif

30、t(r, i, n) ; 選擇排序關(guān)鍵問題：如何由一個無序序列建成一個堆？最后一個結(jié)點（葉子）的序號是n，則最后一個分支結(jié)點即為結(jié)點n的雙親，其序號是n/2。選擇排序關(guān)鍵問題：如何處理堆頂記錄？32362816182536 28 32 25 18 161 2 3 4 5 6對應(yīng)交換16 28 32 25 18 361 2 3 4 5 6對應(yīng)321628361825算法描述：r1rn-i+1; 選擇排序關(guān)鍵問題：如何處理堆頂記錄？解決方法：第 i 次處理堆頂是將堆頂記錄r1與序列中第n-i+1個記錄rn-i+1交換。321628361825選擇排序關(guān)鍵問題：如何調(diào)整剩余記錄，成為一個新堆？162

31、81632361825283236181625解決方法：第 i 次調(diào)整剩余記錄，此時，剩余記錄有n-i個，調(diào)整根結(jié)點至第n-i個記錄。選擇排序關(guān)鍵問題：如何調(diào)整剩余記錄，成為一個新堆？算法描述：sift(r, 1, n-i);堆排序算法void HeapSort ( int r, int n) for (i=n/2; i=1; i-) /初建堆 sift(r, i, n) ; for (i=1; in; i+ ) r1rn-i+1; /移走堆頂 sift(r, 1, n-i); /重建堆 選擇排序堆排序算法的性能分析第1個for循環(huán)是初始建堆，需要O(n)時間；第2個for循環(huán)是輸出堆頂重建堆

32、，共需要取n-1次堆頂記錄，第 i 次取堆頂記錄重建堆需要O(log2i)時間，需要O(nlog2n)時間；因此整個時間復(fù)雜度為O(nlog2n)，這是堆排序的最好、最壞和平均的時間代價。選擇排序歸并排序歸并排序的主要操作是歸并，其主要思想是：將若干有序序列逐步歸并，最終得到一個有序序列。 歸并排序歸并：將兩個或兩個以上的有序序列合并成一個有序序列的過程。 基本思想：將一個具有n個待排序記錄的序列看成是n個長度為1的有序序列，然后進行兩兩歸并，得到n/2個長度為2的有序序列，再進行兩兩歸并，得到n/4個長度為4的有序序列，直至得到一個長度為n的有序序列為止。二路歸并排序歸并排序需解決的關(guān)鍵問題

33、?如何將兩個有序序列合成一個有序序列？怎樣完成一趟歸并？如何控制二路歸并的結(jié)束？60 20 31 5 44 55 65void Merge (int r , int r1 , int s, int m, int t ) i=s; j=m+1; k=s; while (i=m & j=t) if (ri=rj) r1k+=ri+; else r1k+=rj+; if (i=m) while (i=m) /收尾處理 r1k+=ri+; /前一個子序列 else while (j=t) r1k+=rj+; /后一個子序列 歸并排序關(guān)鍵問題：如何將兩個有序序列合成一個有序序列？算法描述：void Me

34、rgePass (int r , int r1 , int n, int h) i=1; while (in-2h+1) /情況1 Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h; if (in-h+1) Merge (r, r1, i, i+h-1, n); /情況2 else for (k=i; k=n; k+) /情況3 r1k=rk;一趟歸并排序算法歸并排序算法描述：void MergeSort (int r , int r1 , int n ) h=1; while (hn) MergePass (r, r1, n, h); h=2*h; MergePass (r1, r, n, h); h=2*h; 歸并排序關(guān)鍵問題：如何控制二路