第8章 排序技術(shù)

1、第八章第八章 排序技術(shù)排序技術(shù)本章的基本內(nèi)容是：本章的基本內(nèi)容是：排序的基本概念排序的基本概念插入排序插入排序交換排序交換排序選擇排序選擇排序歸并排序歸并排序 概概 述述 排序：排序：給定一組給定一組記錄記錄的集合的集合r1, r2, , rn，其相應(yīng)其相應(yīng)的關(guān)鍵碼分別為的關(guān)鍵碼分別為k1, k2, , kn，排序是將這些記錄排序是將這些記錄排列成順序?yàn)榕帕谐身樞驗(yàn)閞s1, rs2, , rsn的一個序列，使得相應(yīng)的一個序列，使得相應(yīng)的關(guān)鍵碼滿足的關(guān)鍵碼滿足ks 1ks 2ks n（稱為升序）或稱為升序）或ks1ks2ksn（稱為降序）。稱為降序）。正序：正序：待排序序列中的記錄已按關(guān)鍵碼排好

2、序。待排序序列中的記錄已按關(guān)鍵碼排好序。逆序（反序）：逆序（反序）：待排序序列中記錄的排列順序與排好待排序序列中記錄的排列順序與排好序的順序正好相反。序的順序正好相反。排序的基本概念排序的基本概念排序算法的穩(wěn)定性：排序算法的穩(wěn)定性：假定在待排序的記錄集中，存在假定在待排序的記錄集中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序相對次序仍然保持不變，即在原序列中，仍然保持不變，即在原序列中，ki=kj且且ri在在rj之前，之前，而在排序后的序列中，而在排序后的序列中，ri仍在仍在rj之前，則稱這種之前，則稱這種排序算法是穩(wěn)定的；否則稱為

3、不穩(wěn)定的。排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。 概概 述述 排序的基本概念排序的基本概念學(xué)號學(xué)號姓名姓名高數(shù)高數(shù)英語英語思想品德思想品德0001王王 軍軍85880002李李 明明64920003湯曉影湯曉影8586687278概概 述述 排序的基本概念排序的基本概念單鍵排序：單鍵排序：根據(jù)一個關(guān)鍵碼進(jìn)行的排序；根據(jù)一個關(guān)鍵碼進(jìn)行的排序；多鍵排序：多鍵排序：根據(jù)多個關(guān)鍵碼進(jìn)行的排序。根據(jù)多個關(guān)鍵碼進(jìn)行的排序。學(xué)號學(xué)號姓名姓名高數(shù)高數(shù)英語英語思想品德思想品德0001王王 軍軍85880002李李 明明64920003湯曉影湯曉影8586687278按學(xué)號排序按學(xué)號排序單鍵排序單鍵排序按成績（高數(shù)

4、英語思想品德）排序按成績（高數(shù)英語思想品德）排序多鍵排序多鍵排序概概 述述 排序的基本概念排序的基本概念設(shè)關(guān)鍵碼分別為設(shè)關(guān)鍵碼分別為k1, k2, , km，多鍵排序有兩種方法：，多鍵排序有兩種方法： 依次對記錄進(jìn)行依次對記錄進(jìn)行m次排序，第一次按次排序，第一次按k1排序，第二排序，第二次按次按k2排序，依此類推。這種方法要求各趟排序所用排序，依此類推。這種方法要求各趟排序所用的算法是穩(wěn)定的；的算法是穩(wěn)定的； 將關(guān)鍵碼將關(guān)鍵碼k1, k2, , km分別視為字符串依次首尾連接分別視為字符串依次首尾連接在一起，形成一個新的字符串，然后，對記錄序列按在一起，形成一個新的字符串，然后，對記錄序列按新

5、形成的字符串排序。新形成的字符串排序。多鍵排序多鍵排序單鍵排序單鍵排序排序的分類排序的分類1. 內(nèi)排序：內(nèi)排序：在排序的整個過程中，待排序的所有記錄在排序的整個過程中，待排序的所有記錄全部被放置在內(nèi)存中全部被放置在內(nèi)存中2. 外排序外排序：由于待排序的記錄個數(shù)太多，不能同時放由于待排序的記錄個數(shù)太多，不能同時放置在內(nèi)存，而需要將一部分記錄放置在內(nèi)存，另一部置在內(nèi)存，而需要將一部分記錄放置在內(nèi)存，另一部分記錄放置在外存上，整個排序過程需要在內(nèi)外存之分記錄放置在外存上，整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。間多次交換數(shù)據(jù)才能得到排序的結(jié)果。概概 述述 排序的基本概念排序的基本

6、概念排序的分類排序的分類1. 基于比較：基于比較：基本操作基本操作關(guān)鍵碼的比較和記錄的移動，關(guān)鍵碼的比較和記錄的移動，其最差時間下限已經(jīng)被證明為其最差時間下限已經(jīng)被證明為（nlog2n）。 2. 不基于比較不基于比較：根據(jù)關(guān)鍵碼的分布特征。：根據(jù)關(guān)鍵碼的分布特征。概概 述述 排序的基本概念排序的基本概念基于比較的內(nèi)排序基于比較的內(nèi)排序1. 插入排序插入排序（插入排序、希爾排序）（插入排序、希爾排序）2. 交換排序交換排序（冒泡排序、快速排序）（冒泡排序、快速排序）3. 選擇排序選擇排序（簡單選擇排序、堆排序）（簡單選擇排序、堆排序）4. 歸并排序歸并排序1. 基本操作基本操作。內(nèi)排序在排序過程

7、中的基本操作：。內(nèi)排序在排序過程中的基本操作：比較比較：關(guān)鍵碼之間的比較；：關(guān)鍵碼之間的比較；移動移動：記錄從一個位置移動到另一個位置。：記錄從一個位置移動到另一個位置。 2. 輔助存儲空間輔助存儲空間。輔助存儲空間是指在數(shù)據(jù)規(guī)模一定的條件下，除了存輔助存儲空間是指在數(shù)據(jù)規(guī)模一定的條件下，除了存放待排序記錄占用的存儲空間之外，執(zhí)行算法所需要放待排序記錄占用的存儲空間之外，執(zhí)行算法所需要的其他存儲空間。的其他存儲空間。3.算法本身的復(fù)雜程度算法本身的復(fù)雜程度。 排序算法的性能排序算法的性能概概 述述 排序算法的存儲結(jié)構(gòu)排序算法的存儲結(jié)構(gòu)概概 述述 從操作角度看，排序是線性結(jié)構(gòu)的一種操作，待排序從

8、操作角度看，排序是線性結(jié)構(gòu)的一種操作，待排序記錄可以用記錄可以用順序順序存儲結(jié)構(gòu)或存儲結(jié)構(gòu)或鏈接鏈接存儲結(jié)構(gòu)存儲。存儲結(jié)構(gòu)存儲。假定假定2：將待排序的記錄序列排序?yàn)閷⒋判虻挠涗浶蛄信判驗(yàn)樯蛏蛐蛄?。序列?int rn+1; /待排序記錄存儲在待排序記錄存儲在r1rn，r0留做他用留做他用假定假定1 1：采用采用順序順序存儲結(jié)構(gòu)，關(guān)鍵碼為存儲結(jié)構(gòu)，關(guān)鍵碼為整型整型，且記錄，且記錄只有關(guān)鍵碼只有關(guān)鍵碼一個一個數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)。插入排序插入排序插入排序的主要操作是插入排序的主要操作是插入插入，其基本思想是：，其基本思想是：每次將一個待排序的記錄按其關(guān)鍵碼的大小插每次將一個待排序的記錄按其關(guān)鍵碼的

9、大小插入到一個已經(jīng)排好序的有序序列中，直到全部入到一個已經(jīng)排好序的有序序列中，直到全部記錄排好序?yàn)橹?。記錄排好序?yàn)橹?。有序序列有序序列無序序列無序序列12i-1ini+1基本思想基本思想：在插入第：在插入第 i（i1）個記錄時，前面的）個記錄時，前面的 i-1個記錄已經(jīng)排好序。個記錄已經(jīng)排好序。 直接插入排序直接插入排序插入排序插入排序有序序列有序序列無序序列無序序列12i-1ini+1基本思想基本思想：在插入第：在插入第 i（i1）個記錄時，前面的）個記錄時，前面的 i-1個記錄已經(jīng)排好序。個記錄已經(jīng)排好序。 （1）如何構(gòu)造初始的有序序列？）如何構(gòu)造初始的有序序列？（2）如何查找待插入記錄的

10、插入位置）如何查找待插入記錄的插入位置?直接插入排序直接插入排序插入排序插入排序需解決的關(guān)鍵問題需解決的關(guān)鍵問題?12i-1ini+1r 0 1 2 3 4 5 6插入排序插入排序i = 2i = 3i = 4i = 6i = 5r0的作用的作用?暫存單元暫存單元監(jiān)視哨監(jiān)視哨解決方法：解決方法：將第將第1個記錄看成是初始有序表，然后從第個記錄看成是初始有序表，然后從第2個記錄起個記錄起依次插入到這個有序表中，直到將第依次插入到這個有序表中，直到將第n個記錄插入。個記錄插入。插入排序插入排序關(guān)鍵問題關(guān)鍵問題(1)如何構(gòu)造初始的有序序列？如何構(gòu)造初始的有序序列？算法描述：算法描述：for (i=2

11、; i=n; i+) 插入第插入第i個記錄，即第個記錄，即第i趟直接插入排序；趟直接插入排序；r 0 1 2 3 4 5 6關(guān)鍵問題關(guān)鍵問題(2)如何查找待插入記錄的插入位置如何查找待插入記錄的插入位置?解決方法：解決方法：在在i- -1個記錄的有序區(qū)個記錄的有序區(qū)r1 ri- -1中插入記錄中插入記錄ri，首，首先順序查找先順序查找ri的正確插入位置，然后將的正確插入位置，然后將ri插入到相插入到相應(yīng)位置。應(yīng)位置。r0有兩個作用：有兩個作用：1. 進(jìn)入循環(huán)之前暫存了進(jìn)入循環(huán)之前暫存了ri的值，使得不致于因記錄的值，使得不致于因記錄的后移而丟失的后移而丟失ri的內(nèi)容；的內(nèi)容；2. 在查找插入位

12、置的循環(huán)在查找插入位置的循環(huán)中充當(dāng)中充當(dāng)哨兵哨兵。插入排序插入排序算法描述：算法描述：r0=ri; j=i-1; while (r0rj) rj+1=rj; j-;r 0 1 2 3 4 5 6ijjr 0 1 2 3 4 5 6插入排序插入排序i = 2i = 3i = 4i = 6i = 5void insertsort (int r , int n) for (i=2; i=n; i+) r0=ri; j=i-1; while (r0=ri-1，內(nèi)層循，內(nèi)層循環(huán)會出現(xiàn)什么情況環(huán)會出現(xiàn)什么情況?r 0 1 2 3 4 5 6i = 2i = 3i = 4i = 6i = 5直接插入排序算法

13、性能分析直接插入排序算法性能分析最好情況下（正序）：最好情況下（正序）： 插入排序插入排序時間復(fù)雜度為時間復(fù)雜度為o(n)。比較次數(shù)：比較次數(shù)：n-1移動次數(shù)：移動次數(shù)：2(n-1) 直接插入排序算法性能分析直接插入排序算法性能分析插入排序插入排序最好最好情況下（正序）：情況下（正序）： 比較次數(shù)：比較次數(shù)：n-1移動次數(shù)：移動次數(shù)：2(n-1) 最壞最壞情況下（逆序或反序）：情況下（逆序或反序）： 時間復(fù)雜度為時間復(fù)雜度為o(n2)。比較次數(shù)：比較次數(shù)：移動次數(shù)：移動次數(shù)：2) 1)(2(2- -+ += = = =nnini2) 1)(4(1- -+ += =+ + nnin2= =i）（

14、時間復(fù)雜度為時間復(fù)雜度為o(n)。平均平均情況下（隨機(jī)排列）：情況下（隨機(jī)排列）： 直接插入排序算法性能分析直接插入排序算法性能分析插入排序插入排序時間復(fù)雜度為時間復(fù)雜度為o(n2)。比較次數(shù)：比較次數(shù)：移動次數(shù)：移動次數(shù)：4) 1)(4(- -+ += = nnn2= =i4) 1)(2(2- -+ += = = =nnnii2（21+ +i）空間性能：空間性能：需要一個記錄的輔助空間。需要一個記錄的輔助空間。直接插入排序算法是一種直接插入排序算法是一種穩(wěn)定穩(wěn)定的排序算法。的排序算法。直接插入排序算法性能分析直接插入排序算法性能分析插入排序插入排序直接插入排序算法簡單、容易實(shí)現(xiàn)，適用于待排直

15、接插入排序算法簡單、容易實(shí)現(xiàn)，適用于待排序記錄基本有序或待排序記錄較小時。序記錄基本有序或待排序記錄較小時。當(dāng)待排序的記錄個數(shù)較多時，大量的比較和移動當(dāng)待排序的記錄個數(shù)較多時，大量的比較和移動操作使直接插入排序算法的效率降低。操作使直接插入排序算法的效率降低。插入排序插入排序如何改進(jìn)直接插入排序如何改進(jìn)直接插入排序?注意到，在插入第注意到，在插入第 i（i1）個記錄時，前面的）個記錄時，前面的 i-1 個個記錄已經(jīng)排好序，則在尋找插入位置時，可以用折記錄已經(jīng)排好序，則在尋找插入位置時，可以用折半查找來代替順序查找，從而較少比較次數(shù)。半查找來代替順序查找，從而較少比較次數(shù)。請同學(xué)們寫出這個改進(jìn)的

16、直接插入排序算法，并分析請同學(xué)們寫出這個改進(jìn)的直接插入排序算法，并分析時間性能。時間性能。 d1希爾排序希爾排序希爾插入排序過程示例希爾插入排序過程示例 1 2 3 4 5 6 7 8 9初始序列初始序列插入排序插入排序d = 4d = 2d = 1將整個待排序記錄將整個待排序記錄分割分割成若干個子序列，在子成若干個子序列，在子序列內(nèi)分別進(jìn)行直接插入排序序列內(nèi)分別進(jìn)行直接插入排序整個序列逐步基本有序整個序列逐步基本有序?qū)θw記錄進(jìn)行直接插入排序?qū)θw記錄進(jìn)行直接插入排序解決方法：解決方法：將相隔某個將相隔某個“增量增量”的記錄組成一個子序列。的記錄組成一個子序列。增量應(yīng)如何??？增量應(yīng)如何??？希

17、爾最早提出的方法是希爾最早提出的方法是d1=n/2，di+1=di/2。關(guān)鍵問題關(guān)鍵問題(1)(1)應(yīng)如何分割待排序記錄？應(yīng)如何分割待排序記錄？插入排序插入排序算法描述：算法描述：for (d=n/2; d=1; d=d/2) 以以d為增量，進(jìn)行組內(nèi)直接插入排序；為增量，進(jìn)行組內(nèi)直接插入排序；n=9d1=4d2=2d3=1初始序列初始序列d = 4解決方法：解決方法：在插入記錄在插入記錄ri時，自時，自ri-d起往前跳躍式（跳躍幅起往前跳躍式（跳躍幅度為度為d）搜索待插入位置，并且搜索待插入位置，并且r0只是暫存單元，只是暫存單元，不是哨兵。當(dāng)搜索位置不是哨兵。當(dāng)搜索位置0，表示插入位置已找到

18、。，表示插入位置已找到。在搜索過程中，記錄后移也是跳躍在搜索過程中，記錄后移也是跳躍d個位置。個位置。在整個序列中，前在整個序列中，前d個記錄分別是個記錄分別是d個子序列中的個子序列中的第一個記錄，所以從第第一個記錄，所以從第d+1個記錄開始進(jìn)行插入。個記錄開始進(jìn)行插入。插入排序插入排序關(guān)鍵問題關(guān)鍵問題( (2) )子序列內(nèi)如何進(jìn)行直接插入排序？子序列內(nèi)如何進(jìn)行直接插入排序？d = 4算法描述：算法描述：for (i=d+1; i0 & r0=1; d=d/2) /以增量為以增量為d d進(jìn)行直接插入排序進(jìn)行直接插入排序 for (i=d+1; i0 & r0rj; j=j-d)

19、 rj+d=rj; /記錄后移記錄后移d d個位置個位置 rj+d=r0; for(i=1;in;i+) coutri ; coutrj+1） rjrj+1； exchange=j； 解決方法：解決方法：設(shè)變量設(shè)變量exchange記載記錄交換的位置，則一趟排序后，記載記錄交換的位置，則一趟排序后，exchange記載的一定是這一趟排序中記錄的最后一次交記載的一定是這一趟排序中記錄的最后一次交換的位置，且從此位置以后的所有記錄均已經(jīng)有序。換的位置，且從此位置以后的所有記錄均已經(jīng)有序。解決方法：解決方法：設(shè)設(shè)bound位置的記錄是無序區(qū)的最后一個記錄，則每位置的記錄是無序區(qū)的最后一個記錄，則每趟

20、起泡排序的范圍是趟起泡排序的范圍是r1 rbound。在一趟排序后，從在一趟排序后，從exchange位置之后的記錄一定是有位置之后的記錄一定是有序的，所以序的，所以bound=exchange。交換排序交換排序關(guān)鍵問題：關(guān)鍵問題：如何確定起泡排序的范圍如何確定起泡排序的范圍？交換交換交換交換交換交換解決方法：解決方法：設(shè)設(shè)bound位置的記錄是無序區(qū)的最后一個記錄，則每位置的記錄是無序區(qū)的最后一個記錄，則每趟起泡排序的范圍是趟起泡排序的范圍是r1 rbound。在一趟排序后，從在一趟排序后，從exchange位置之后的記錄一定是有位置之后的記錄一定是有序的，所以序的，所以bound=exch

21、ange。交換排序交換排序關(guān)鍵問題：關(guān)鍵問題：如何確定起泡排序的范圍如何確定起泡排序的范圍？算法描述：算法描述：bound=exchange; for (j=1; jrj+1） rjrj+1； exchange=j； 解決方法：解決方法：在每一趟起泡排序之前，令在每一趟起泡排序之前，令exchange的初值為的初值為0，在在以后的排序過程中，只要有記錄交換，以后的排序過程中，只要有記錄交換，exchange的的值就會大于值就會大于0。這樣，在一趟比較完畢，就可以通過。這樣，在一趟比較完畢，就可以通過exchange的值是否為的值是否為0來判別是否有記錄交換，從而來判別是否有記錄交換，從而判別整

22、個起泡排序的結(jié)束。判別整個起泡排序的結(jié)束。交換排序交換排序關(guān)鍵問題：關(guān)鍵問題：如何判別起泡排序的結(jié)束？如何判別起泡排序的結(jié)束？解決方法：解決方法：在每一趟起泡排序之前，令在每一趟起泡排序之前，令exchange的初值為的初值為0，在在以后的排序過程中，只要有記錄交換，以后的排序過程中，只要有記錄交換，exchange的的值就會大于值就會大于0。這樣，在一趟比較完畢，就可以通過。這樣，在一趟比較完畢，就可以通過exchange的值是否為的值是否為0來判別是否有記錄交換，從而來判別是否有記錄交換，從而判別整個起泡排序的結(jié)束。判別整個起泡排序的結(jié)束。交換排序交換排序關(guān)鍵問題：關(guān)鍵問題：如何判別起泡排

23、序的結(jié)束？如何判別起泡排序的結(jié)束？算法描述：算法描述：while ( (exchange) ) 執(zhí)行一趟起泡排序；執(zhí)行一趟起泡排序；void bubblesort( (int r , int n) ) exchange=n; while ( (exchange) ) bound=exchange; exchange=0； for ( (j=1; jrj+1) ) rjrj+1； exchange=j； 起泡排序算法起泡排序算法交換排序交換排序起泡排序的時間性能分析起泡排序的時間性能分析最好情況（正序）：最好情況（正序）：交換排序交換排序比較次數(shù)：比較次數(shù)：n-1移動次數(shù)：移動次數(shù)：0 時間復(fù)雜

24、度為時間復(fù)雜度為o(n)。最壞情況（反序）：最壞情況（反序）：起泡排序的時間性能分析起泡排序的時間性能分析最好情況（正序）：最好情況（正序）：交換排序交換排序比較次數(shù)：比較次數(shù)：n-1移動次數(shù)：移動次數(shù)：0 時間復(fù)雜度為時間復(fù)雜度為o(n)；時間復(fù)雜度為時間復(fù)雜度為o(n2)。比較次數(shù)：比較次數(shù)：移動次數(shù)：移動次數(shù)：2) 1(1- -= = = =nn(n-i)n-1i2) 1(1- -= = = =n3n3(n-i)n-1i平均情況：平均情況：時間復(fù)雜度為時間復(fù)雜度為o(n2)。交換排序交換排序如何改進(jìn)起泡排序如何改進(jìn)起泡排序?需掃描需掃描1趟趟需掃描需掃描n-1趟趟需掃描需掃描2趟趟需掃描

25、需掃描n-2趟趟造成不對稱的原因是什么造成不對稱的原因是什么?交換排序交換排序如何改變不對稱性如何改變不對稱性?在排序過程中交替改變掃描方向在排序過程中交替改變掃描方向雙向起泡排序雙向起泡排序快速排序快速排序改進(jìn)的著眼點(diǎn)：改進(jìn)的著眼點(diǎn)：在起泡排序中，記錄的比較和移動是在起泡排序中，記錄的比較和移動是在在相鄰相鄰單元中進(jìn)行的，記錄每次交換只能上移或下移單元中進(jìn)行的，記錄每次交換只能上移或下移一個一個單元，因而總的比較次數(shù)和移動次數(shù)較多。單元，因而總的比較次數(shù)和移動次數(shù)較多。交換排序交換排序減少總的比較次數(shù)和移動次數(shù)減少總的比較次數(shù)和移動次數(shù)增大記錄的比較和移動距離增大記錄的比較和移動距離較大記錄

26、從前面直接移動到后面較大記錄從前面直接移動到后面較小記錄從后面直接移動到前面較小記錄從后面直接移動到前面快速排序的基本思想快速排序的基本思想首先選一個首先選一個軸值軸值（即比較的基準(zhǔn)），通過一趟排序?qū)ⅲ幢容^的基準(zhǔn)），通過一趟排序?qū)⒋判蛴涗洿判蛴涗浄指罘指畛瑟?dú)立的兩部分，前一部分記錄的關(guān)成獨(dú)立的兩部分，前一部分記錄的關(guān)鍵碼均鍵碼均小于或等于小于或等于軸值，后一部分記錄的關(guān)鍵碼均軸值，后一部分記錄的關(guān)鍵碼均大大于或等于于或等于軸值，然后分別對這兩部分重復(fù)上述方法，軸值，然后分別對這兩部分重復(fù)上述方法，直到整個序列有序。直到整個序列有序。交換排序交換排序如何選擇軸值？如何選擇軸值？如何實(shí)現(xiàn)分割

27、（稱一次劃分）？如何實(shí)現(xiàn)分割（稱一次劃分）？如何處理分割得到的兩個待排序子序列？如何處理分割得到的兩個待排序子序列？如何判別快速排序的結(jié)束？如何判別快速排序的結(jié)束？需解決的關(guān)鍵問題需解決的關(guān)鍵問題?選擇軸值的方法：選擇軸值的方法：1.使用第一個記錄的關(guān)鍵碼；使用第一個記錄的關(guān)鍵碼；2.選取序列中間記錄的關(guān)鍵碼；選取序列中間記錄的關(guān)鍵碼；3.比較序列中第一個記錄、最后一個記錄和中間比較序列中第一個記錄、最后一個記錄和中間記錄的關(guān)鍵碼，取關(guān)鍵碼居中的作為軸值并調(diào)換記錄的關(guān)鍵碼，取關(guān)鍵碼居中的作為軸值并調(diào)換到第一個記錄的位置；到第一個記錄的位置；4.隨機(jī)選取軸值。隨機(jī)選取軸值。交換排序交換排序關(guān)鍵問

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

29、記錄移動到前面去；面去；（2）i從前從前向后向后掃描，直到掃描，直到rirj，將將ri移動到移動到rj的位置，使關(guān)鍵碼大（同軸值比較）的記錄移動到后的位置，使關(guān)鍵碼大（同軸值比較）的記錄移動到后面去；面去；（3）重復(fù)上述過程，直到）重復(fù)上述過程，直到i=j。交換排序交換排序關(guān)鍵問題：關(guān)鍵問題：如何實(shí)現(xiàn)一次劃分？如何實(shí)現(xiàn)一次劃分？交換排序交換排序關(guān)鍵問題：關(guān)鍵問題：如何實(shí)現(xiàn)一次劃分？如何實(shí)現(xiàn)一次劃分？算法描述：算法描述：int partition(int r , int first, int end) i=first; j=end; /初始化初始化 while (ij) while (ij &a

30、mp; ri= rj) j-； /右側(cè)掃描右側(cè)掃描 if (ij) rirj; i+; /將較小記錄交換到前面將較小記錄交換到前面 while (ij & ri= rj) i+； /左側(cè)掃描左側(cè)掃描 if (ij) rjri; j-; /將較大記錄交換到后面將較大記錄交換到后面 retutn i; /i為軸值記錄的最終位置為軸值記錄的最終位置ji關(guān)鍵問題：關(guān)鍵問題：如何實(shí)現(xiàn)一次劃分？如何實(shí)現(xiàn)一次劃分？jjiiijijjjint partition(int r , int first, int end) i=first; j=end; /初始化初始化 while (ij) while (

31、ij & ri= rj) j-； if (ij) rirj; i+; while (ij & ri= rj) i+； if (ij) rjri; j-; retutn i;解決方法：解決方法：對分割得到的兩個子序列遞歸地執(zhí)行快速排序。對分割得到的兩個子序列遞歸地執(zhí)行快速排序。交換排序交換排序關(guān)鍵問題：如何處理分割得到的兩個待排序子序列？關(guān)鍵問題：如何處理分割得到的兩個待排序子序列？ ijij算法描述：算法描述：交換排序交換排序關(guān)鍵問題：如何處理分割得到的兩個待排序子序列？關(guān)鍵問題：如何處理分割得到的兩個待排序子序列？ void quicksort (int r , int fi

32、rst, int end ) pivotpos = partition (r, first, end ); /一次劃分一次劃分 quicksort (r, first, pivotpos-1); /對前一個子序列進(jìn)行快速排序?qū)η耙粋€子序列進(jìn)行快速排序 quicksort (r, pivotpos+1, end ); /對后一個子序列進(jìn)行快速排序?qū)笠粋€子序列進(jìn)行快速排序解決方法：解決方法：若待排序列中只有一個記錄，顯然已有序，否則進(jìn)若待排序列中只有一個記錄，顯然已有序，否則進(jìn)行一次劃分后，再分別對分割所得的兩個子序列進(jìn)行一次劃分后，再分別對分割所得的兩個子序列進(jìn)行快速排序（即遞歸處理）。行快速

33、排序（即遞歸處理）。 交換排序交換排序關(guān)鍵問題：關(guān)鍵問題：如何判別快速排序的結(jié)束？如何判別快速排序的結(jié)束？ void quicksort (int r , int first, int end )/在序列在序列 firstend中遞歸地進(jìn)行快速排序中遞歸地進(jìn)行快速排序 if (first end) pivotpos = partition (r, first, end ); quicksort (r, first, pivotpos-1); quicksort (r, pivotpos+1, end ); 算法描述：算法描述：交換排序交換排序關(guān)鍵問題：關(guān)鍵問題：如何判別快速排序的結(jié)束？如何判別

34、快速排序的結(jié)束？ int partition(int r , int first, int end) i=first; j=end; /初始化初始化 while (ij) while (ij & ri= rj) j-； if (ij) rirj; i+; while (ij & ri= rj) i+； if (ij) rjri; j-; retutn i;快速排序的時間性能分析快速排序的時間性能分析交換排序交換排序快速排序的時間性能快速排序的時間性能快速排序遞歸的深度快速排序遞歸的深度每次劃分軸值的選取每次劃分軸值的選取最好情況：最好情況：每一次劃分對一個記錄定位后，該記錄的左

35、側(cè)子表與每一次劃分對一個記錄定位后，該記錄的左側(cè)子表與右側(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)。最好情況：最好情況：每一次劃分對一個記錄定位后，該記錄的左側(cè)子表與每一次劃分對一

36、個記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為右側(cè)子表的長度相同，為o(nlog2n)?？焖倥判虻臅r間性能分析快速排序的時間性能分析交換排序交換排序平均情況：平均情況：為為o(nlog2n)。)() 1(21211nonninni= =- -= =- - - -= =）（選擇排序的主要操作是選擇排序的主要操作是選擇選擇，其主要思想是：，其主要思想是：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小最小的記錄，添加到有序序列中。的記錄，添加到有序序列中。 選擇排序選擇排序有序序列有序序列12i-1ink無序序列無序序列ni+112i-1ii交換交換最小記錄最小

37、記錄簡單選擇排序簡單選擇排序基本思想：基本思想：第第i 趟在趟在n- -i+1（i=1,2, ,n- -1）個記錄中選個記錄中選取關(guān)鍵碼最小的記錄作為有序序列中的第取關(guān)鍵碼最小的記錄作為有序序列中的第i個記錄。個記錄。 選擇排序選擇排序需解決的關(guān)鍵問題需解決的關(guān)鍵問題?如何在待排序序列中選出關(guān)鍵碼最小的記錄？如何在待排序序列中選出關(guān)鍵碼最小的記錄？如何確定待排序序列中關(guān)鍵碼最小的記錄在有如何確定待排序序列中關(guān)鍵碼最小的記錄在有序序列中的位置？序序列中的位置？ 簡單選擇排序示例簡單選擇排序示例最小者最小者 08交換交換21,08最小者最小者 16交換交換25,16最小者最小者 21交換交換49,

38、21選擇排序選擇排序最小者最小者 25交換交換25,28最小者最小者 28不交換不交換選擇排序選擇排序簡單選擇排序示例簡單選擇排序示例無序區(qū)只有無序區(qū)只有一個記錄一個記錄解決方法：解決方法：設(shè)置一個整型變量設(shè)置一個整型變量index，用于記錄在一趟比較的過程用于記錄在一趟比較的過程中關(guān)鍵碼中關(guān)鍵碼最小的記錄位置。最小的記錄位置。 選擇排序選擇排序關(guān)鍵問題：關(guān)鍵問題：如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？indexindex index算法描述：算法描述：index=i; for ( (j=i+1; j=n; j+) ) if ( (rjrindex) ) in

39、dex=j;解決方法：解決方法：設(shè)置一個整型變量設(shè)置一個整型變量index，用于記錄在一趟比較的過程用于記錄在一趟比較的過程中關(guān)鍵碼中關(guān)鍵碼最小的記錄位置。最小的記錄位置。 關(guān)鍵問題：關(guān)鍵問題：如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？indexindex解決方法：解決方法：第第i趟簡單選擇排序的待排序區(qū)間是趟簡單選擇排序的待排序區(qū)間是ri rn，則則ri是無是無序序區(qū)第一個記錄，所以，將區(qū)第一個記錄，所以，將index所記載的關(guān)鍵碼最小的所記載的關(guān)鍵碼最小的記錄與記錄與ri交換交換。選擇排序選擇排序關(guān)鍵問題：如何確定關(guān)鍵問題：如何確定最小記錄的最終位置？最小記錄

40、的最終位置？算法描述：算法描述： if ( (index!=i) ) ririndex; iindexvoid selectsort ( int r , int n) for ( i=1; in; i+) index=i; for (j=i+1; j=n; j+) if (rjrindex) index=j; if (index!=i) ririndex; 簡單選擇排序算法簡單選擇排序算法選擇排序選擇排序 iindex簡單選擇排序算法的性能分析簡單選擇排序算法的性能分析移動次數(shù)：移動次數(shù)：最好情況（正序）：最好情況（正序）：0次次選擇排序選擇排序最壞情況：最壞情況：3(n-1)次次簡單選擇排序

41、算法的性能分析簡單選擇排序算法的性能分析移動次數(shù)：移動次數(shù)：最好情況（正序）：最好情況（正序）：0次次選擇排序選擇排序空間性能：空間性能：需一個輔助空間。需一個輔助空間。穩(wěn)定性：穩(wěn)定性：是一種穩(wěn)定的排序算法。是一種穩(wěn)定的排序算法。比較次數(shù)：比較次數(shù)：)() 1(21211nonninni= =- -= =- - - -= =）（簡單選擇排序的時間復(fù)雜度為簡單選擇排序的時間復(fù)雜度為o(n2)。交換一次元素移動交換一次元素移動3次次堆排序堆排序改進(jìn)的著眼點(diǎn)：改進(jìn)的著眼點(diǎn)：如何如何減少減少關(guān)鍵碼間的關(guān)鍵碼間的比較比較次數(shù)。若次數(shù)。若能利用每趟比較后的結(jié)果，也就是在找出鍵值最小能利用每趟比較后的結(jié)果，

42、也就是在找出鍵值最小記錄的同時，也找出鍵值較小的記錄，則可減少后記錄的同時，也找出鍵值較小的記錄，則可減少后面的選擇中所用的比較次數(shù)，從而提高整個排序過面的選擇中所用的比較次數(shù)，從而提高整個排序過程的效率。程的效率。選擇排序選擇排序減少關(guān)鍵碼間的比較次數(shù)減少關(guān)鍵碼間的比較次數(shù)查找最小值的同時，找出較小值查找最小值的同時，找出較小值堆的定義堆的定義堆是具有下列性質(zhì)的堆是具有下列性質(zhì)的完全二叉樹完全二叉樹：每個結(jié)點(diǎn)的值都：每個結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小根堆小根堆），），或每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值或每個結(jié)點(diǎn)的值都大于或等于其左右

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

44、18281. 大根堆的根結(jié)點(diǎn)是大根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最大者。所有結(jié)點(diǎn)的最大者。2. 較大結(jié)點(diǎn)靠近根結(jié)較大結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。點(diǎn)，但不絕對。堆和序列的關(guān)系堆和序列的關(guān)系選擇排序選擇排序?qū)⒍延庙樞虼鎯Y(jié)構(gòu)來存儲，則堆對應(yīng)一組序列。將堆用順序存儲結(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)造成一個堆，首先將待排序的記錄序列構(gòu)造成一個堆，此時，選出了堆中所有記錄的此時，選出了堆中所有

45、記錄的最大者最大者，然后將它從堆，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個記錄。次小的記錄，以此類推，直到堆中只有一個記錄。 選擇排序選擇排序堆排序堆排序需解決的關(guān)鍵問題需解決的關(guān)鍵問題?如何由一個無序序列建成一個堆（即初始建堆）？如何由一個無序序列建成一個堆（即初始建堆）？如何處理堆頂記錄？如何處理堆頂記錄？如何調(diào)整剩余記錄，成為一個新堆（即重建堆）？如何調(diào)整剩余記錄，成為一個新堆（即重建堆）？ 堆調(diào)整堆調(diào)整堆調(diào)整：堆調(diào)整：在一棵完全二叉樹中，根結(jié)點(diǎn)的左右子樹均是在一棵完全二叉樹中，根結(jié)點(diǎn)的

46、左右子樹均是堆，如何調(diào)整根結(jié)點(diǎn)，使整個完全二叉樹成為一個堆？堆，如何調(diào)整根結(jié)點(diǎn)，使整個完全二叉樹成為一個堆？選擇排序選擇排序243632161825321618253624321618253624void sift(int r , int k, int m) int i, j, temp; i=k; j=2*i; /置置i i為要篩的結(jié)點(diǎn)，為要篩的結(jié)點(diǎn)，j j為為i i的左孩子的左孩子 while (j=m) /篩選還沒有進(jìn)行到葉子篩選還沒有進(jìn)行到葉子 if (jm & rjrj) break; /根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者 else temp=r

47、i; ri=rj; rj=temp; /將根結(jié)點(diǎn)與結(jié)點(diǎn)將根結(jié)點(diǎn)與結(jié)點(diǎn)j j交換交換 i=j; j=2*i; /被篩結(jié)點(diǎn)位于原來結(jié)點(diǎn)被篩結(jié)點(diǎn)位于原來結(jié)點(diǎn)j j的位置的位置 選擇排序選擇排序堆調(diào)整堆調(diào)整算法描述：算法描述：243632161825void sift ( int r , int k, int m ) i=k; j=2*i; temp=ri; /將篩選記錄暫存將篩選記錄暫存 while (j=m ) /篩選還沒有進(jìn)行到葉子篩選還沒有進(jìn)行到葉子 if (jm & rjrj) break; else ri=rj; i=j; j=2*i; ri=temp; /將篩選記錄移到正確位置將

48、篩選記錄移到正確位置選擇排序選擇排序堆調(diào)整堆調(diào)整算法描述：算法描述：243632161825選擇排序選擇排序關(guān)鍵問題：關(guān)鍵問題：如何由一個無序序列建成一個堆？如何由一個無序序列建成一個堆？282516321836163216282518362532162818362528323628161825算法描述：算法描述：for (i=n/2; i=1; i-) sift(r, i, n) ; 選擇排序選擇排序關(guān)鍵問題：關(guān)鍵問題：如何由一個無序序列建成一個堆？如何由一個無序序列建成一個堆？最后一個結(jié)點(diǎn)（葉子）的序號是最后一個結(jié)點(diǎn)（葉子）的序號是n，則最后一個分支結(jié)點(diǎn)即為結(jié)點(diǎn)則最后一個分支結(jié)點(diǎn)即為結(jié)點(diǎn)n

49、的雙親，的雙親，其序號是其序號是n/2。282516321836選擇排序選擇排序關(guān)鍵問題：關(guān)鍵問題：如何處理堆頂記錄？如何處理堆頂記錄？32362816182536 28 32 25 18 161 2 3 4 5 6對對應(yīng)應(yīng)交換交換16 28 32 25 18 361 2 3 4 5 6對對應(yīng)應(yīng)321628361825算法描述：算法描述：r1rn-i+1; 選擇排序選擇排序關(guān)鍵問題：關(guān)鍵問題：如何處理堆頂記錄？如何處理堆頂記錄？解決方法：解決方法：第第 i 次處理堆頂是將堆頂記錄次處理堆頂是將堆頂記錄r1與序列中第與序列中第n-i+1個個記錄記錄rn-i+1交換。交換。16 28 32 25

50、18 361 2 3 4 5 6對對應(yīng)應(yīng)321628361825321628361825選擇排序選擇排序關(guān)鍵問題：關(guān)鍵問題：如何調(diào)整剩余記錄，成為一個新堆？如何調(diào)整剩余記錄，成為一個新堆？16281632361825283236181625解決方法：解決方法：第第 i 次調(diào)整剩余記錄，此時，剩余記錄有次調(diào)整剩余記錄，此時，剩余記錄有n-i個，調(diào)整個，調(diào)整根結(jié)點(diǎn)至第根結(jié)點(diǎn)至第n-i個記錄。個記錄。選擇排序選擇排序關(guān)鍵問題：關(guān)鍵問題：如何調(diào)整剩余記錄，成為一個新堆？如何調(diào)整剩余記錄，成為一個新堆？算法描述：算法描述：sift(r, 1, n-i);堆排序算法堆排序算法void heapsort (

51、 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); /重建堆重建堆 選擇排序選擇排序32362816182536 28 32 25 18 161 2 3 4 5 6堆排序算法的性能分析堆排序算法的性能分析第第1個個for循環(huán)是初始建堆，需要循環(huán)是初始建堆，需要o(n)時間；時間；第第2個個for循環(huán)是輸出堆頂重建堆，共需要取循環(huán)是輸出堆頂重建堆，共需要取n-1次堆頂次堆頂記錄，第記錄，第 i 次取堆頂記錄重建

52、堆需要次取堆頂記錄重建堆需要o(log2i)時間，需時間，需要要o(nlog2n)時間；時間；因此整個時間復(fù)雜度為因此整個時間復(fù)雜度為o(nlog2n)，這是堆排序的這是堆排序的最好最好、最壞最壞和和平均平均的時間代價。的時間代價。選擇排序選擇排序歸并排序歸并排序歸并排序的主要操作是歸并排序的主要操作是歸并歸并，其主要思想是：，其主要思想是：將若干有序序列逐步歸并，最終得到一個有序?qū)⑷舾捎行蛐蛄兄鸩綒w并，最終得到一個有序序列。序列。 歸并排序歸并排序歸并：歸并：將兩個或兩個以上的有序序列合并成一個有序?qū)蓚€或兩個以上的有序序列合并成一個有序序列的過程。序列的過程。 60203154455652

53、0 605 3144 556560 20 31 5 44 55 65基本思想：基本思想：將一個具有將一個具有n個待排序記錄的序列看成個待排序記錄的序列看成是是n個長度為個長度為1的有序序列，然后進(jìn)行兩兩歸并，得的有序序列，然后進(jìn)行兩兩歸并，得到到n/2個長度為個長度為2的有序序列，再進(jìn)行兩兩歸并，得的有序序列，再進(jìn)行兩兩歸并，得到到n/4個長度為個長度為4的有序序列，的有序序列，直至得到一個，直至得到一個長度為長度為n的有序序列為止。的有序序列為止。二路歸并排序二路歸并排序歸并排序歸并排序需解決的關(guān)鍵問題需解決的關(guān)鍵問題?如何將兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序列？

54、怎樣完成一趟歸并？怎樣完成一趟歸并？如何控制二路歸并的結(jié)束？如何控制二路歸并的結(jié)束？602031544556520 605 3144 556560 20 31 5 44 55 65關(guān)鍵問題：關(guān)鍵問題：如何將兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序列？歸并排序歸并排序602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60關(guān)鍵問題：關(guān)鍵問題：如何將兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序列？歸并排序歸并排序602031544556520 605 3144 5565 60 20 31 5

55、 44 55 65ij5kj20i31j60歸并可以就地進(jìn)行嗎歸并可以就地進(jìn)行嗎?在歸并過程中，可能會破壞原在歸并過程中，可能會破壞原來的有序序列，所以，將來的有序序列，所以，將歸并歸并的結(jié)果存入另外一個數(shù)組中的結(jié)果存入另外一個數(shù)組中。 關(guān)鍵問題：關(guān)鍵問題：如何將兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序列？歸并排序歸并排序602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60關(guān)鍵問題：關(guān)鍵問題：如何將兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序列？歸并排序歸并排序60203154455

56、6520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60子序列的長度一定相等嗎子序列的長度一定相等嗎?關(guān)鍵問題：關(guān)鍵問題：如何將兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序列？歸并排序歸并排序602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60關(guān)鍵問題：關(guān)鍵問題：如何將兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序列？歸并排序歸并排序設(shè)相鄰的有序序列為設(shè)相鄰的有序序列為rs rm和和rm+1 rt，歸并，歸并成一個有序序列成一個有序序列r1s

57、r1t s m m+1 t r s t r1 ijkvoid 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)鍵問題：關(guān)鍵問題：如何將兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序

58、列？算法描述：算法描述：20 605 31 ij5k20 31 60歸并排序歸并排序關(guān)鍵問題：關(guān)鍵問題：怎樣完成一趟歸并？怎樣完成一趟歸并？602031544556520 605 3144 556560 20 31 5 44 55 65 5 20 31 60 44 55 65在一趟歸并中，除最后一個有序序列外，其它有序在一趟歸并中，除最后一個有序序列外，其它有序序列中記錄的個數(shù)相同，用長度序列中記錄的個數(shù)相同，用長度h表示。表示。歸并排序歸并排序關(guān)鍵問題：關(guān)鍵問題：怎樣完成一趟歸并？怎樣完成一趟歸并？設(shè)參數(shù)設(shè)參數(shù)i指向待歸并序列的第一個記錄，歸并的步長是指向待歸并序列的第一個記錄，歸并的步長是

59、2h，在歸并過程中，有以下三種情況：在歸并過程中，有以下三種情況：若若in-2h+1，則相鄰兩個有序表的長度均為則相鄰兩個有序表的長度均為h，執(zhí)行執(zhí)行一次歸并，完成后一次歸并，完成后i加加2h，準(zhǔn)備進(jìn)行下一次歸并；準(zhǔn)備進(jìn)行下一次歸并；20 605 3144 5565ihi=1n-2h+1=4n-2h+1歸并排序歸并排序關(guān)鍵問題：關(guān)鍵問題：怎樣完成一趟歸并？怎樣完成一趟歸并？設(shè)參數(shù)設(shè)參數(shù)i指向待歸并序列的第一個記錄，歸并的步長是指向待歸并序列的第一個記錄，歸并的步長是2h，在歸并過程中，有以下三種情況：，在歸并過程中，有以下三種情況：若若in-2h+1，則相鄰兩個有序表的長度均為則相鄰兩個有序表

60、的長度均為h，執(zhí)行執(zhí)行一次歸并，完成后一次歸并，完成后i加加2h，準(zhǔn)備進(jìn)行下一次歸并；準(zhǔn)備進(jìn)行下一次歸并；算法描述：算法描述：while (in-2h+1) merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h;歸并排序歸并排序關(guān)鍵問題：關(guān)鍵問題：怎樣完成一趟歸并？怎樣完成一趟歸并？設(shè)參數(shù)設(shè)參數(shù)i指向待歸并序列的第一個記錄，歸并的步長是指向待歸并序列的第一個記錄，歸并的步長是2h，在歸并過程中，有以下三種情況：，在歸并過程中，有以下三種情況：若若in-h+1，則表示仍有兩個相鄰有序表，一個長則表示仍有兩個相鄰有序表，一個長度為度為h，另一個長度小于另一個長度小于h，則執(zhí)行兩個有序表的歸并，則執(zhí)行兩個有序表的歸并，完成后退出一趟歸并。完成后退出一