數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：第7章 排序

1、概述插入排序交換排序選擇排序歸并排序基數(shù)排序外排序第7章 排序1概述數(shù)據(jù)表(datalist): 它是待排序數(shù)據(jù)對(duì)象的有限集合。關(guān)鍵碼(key): 通常數(shù)據(jù)對(duì)象有多個(gè)屬性域, 即多個(gè)數(shù)據(jù)成員組成, 其中有一個(gè)屬性域可用來(lái)區(qū)分對(duì)象, 作為排序依據(jù)。該域即為關(guān)鍵碼。每個(gè)數(shù)據(jù)表用哪個(gè)屬性域作為關(guān)鍵碼，要視具體的應(yīng)用需要而定。2排序：將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)。排序問(wèn)題確切定義：給定一組記錄r1, r2, rn，其排序碼分別為k1, k2, ，kn，將這些記錄排成順序?yàn)閞s1,rs2,rsn 的一個(gè)序列S，滿足條件ks1ks2ksn 或ks1ks2 ksn 。3排序的目的：便于查找內(nèi)

2、排序與外排序: 內(nèi)排序是指在排序期間數(shù)據(jù)對(duì)象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對(duì)象個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序過(guò)程的要求，不斷在內(nèi)、外存之間移動(dòng)的排序。4排序算法好壞的衡量： 1）時(shí)間效率 2）空間效率 3）穩(wěn)定性排序的時(shí)間開(kāi)銷: 排序的時(shí)間開(kāi)銷是衡量算法好壞的最重要的標(biāo)志。排序的時(shí)間開(kāi)銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來(lái)衡量。算法運(yùn)行時(shí)間代價(jià)的大略估算一般都按平均情況進(jìn)行估算。對(duì)于那些受對(duì)象排序碼序列初始排列及對(duì)象個(gè)數(shù)影響較大的，需要按最好情況和最壞情況進(jìn)行估算。5算法執(zhí)行時(shí)所需的附加存儲(chǔ): 評(píng)價(jià)算法好壞的另一標(biāo)準(zhǔn)。排序算法的穩(wěn)定性: 如果在對(duì)象序列中有兩

3、 個(gè)對(duì)象ri和rj, 它們的排序碼 ki = kj , 且在排序之前, 對(duì)象ri排在rj前面。如果在排序之后, 對(duì)象ri仍在對(duì)象rj的前面, 則稱這個(gè)排序方法是穩(wěn)定的, 否則稱這個(gè)排序方法是不穩(wěn)定的。6插入排序 (Insert Sorting) 基本方法是 : 每步將一個(gè)待排序的對(duì)象, 按其排序碼大小, 插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上, 直到對(duì)象全部插入為止。共做n趟排序，第i趟排序的過(guò)程如下:有序序列r1.i-1ri無(wú)序序列 ri.n有序序列r1.i無(wú)序序列 ri+1.n7直接插入排序 (Insert Sort)基本思想是 : 當(dāng)插入第i (i 1) 個(gè)對(duì)象時(shí), 前面的V0, V

4、1, , Vi-1已經(jīng)排好序。這時(shí), 用Vi的排序碼與Vi-1, Vi-2, 的排序碼順序進(jìn)行比較, 找到插入位置即將Vi插入, 原來(lái)位置上的對(duì)象向后順移。插入過(guò)程分為兩步:1、利用 “順序查找”實(shí)現(xiàn)“在V1.i-1中查找Vi的插入位置”2、插入8例：關(guān)鍵字序列T= （21，25，49，25*，16，08），請(qǐng)寫出直接插入排序的具體實(shí)現(xiàn)過(guò)程。*表示后一個(gè)25解：假設(shè)該序列已存入一維數(shù)組R7中，將R0作為緩沖或暫存單元（Temp）。則程序執(zhí)行過(guò)程為：i=121254925*16080 1 2 3 4 5 6暫存21i=2i=3i=5i=4i=625252549494925*25*49161625

5、*08084921254925*21初態(tài)：164925*25211608完成!考慮:若記錄是鏈表結(jié)構(gòu),插入排序是否可行?直接插入不僅可行，而且還無(wú)需移動(dòng)元素，時(shí)間效率更高！9設(shè)待排序?qū)ο髠€(gè)數(shù)為currentSize = n, 則該算法的主程序執(zhí)行n-1趟。排序碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)與對(duì)象排序碼的初始排列有關(guān)。最好情況下（關(guān)鍵字在記錄序列中順序有序）, 每趟只需與前面有序?qū)ο笮蛄械淖詈笠粋€(gè)對(duì)象比較1次, 移動(dòng)2次對(duì)象, 總的排序 碼比較次數(shù)為 n-1, 對(duì)象移動(dòng)次數(shù)為2(n-1) 。直接插入排序的算法分析10 最壞情況下（關(guān)鍵字在記錄序列中逆序有序）, 第 i 趟時(shí)第 i 個(gè)對(duì)象必須與前面 i

6、 個(gè)對(duì)象都做排序碼比較, 并且每做1次比較就要做1次數(shù)據(jù)移動(dòng)。則總排序碼比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN分別為平均情況下排序的時(shí)間復(fù)雜度為 O(n2)。直接插入排序是一種穩(wěn)定的排序方法。11折半插入排序 (Binary Insertsort)有序序列R1.i-1Ri無(wú)序序列 Ri.n基本思想：因?yàn)?R1.i-1 是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“在R1.i-1中查找Ri的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉?214 36 49 52 8058 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 7

7、5ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r13折半搜索比順序搜索查找快, 所以折半插入排序就平均性能來(lái)說(shuō)比直接插入排序要快。它所需的排序碼比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o(wú)關(guān), 僅依賴于對(duì)象個(gè)數(shù)。在插入第 i 個(gè)對(duì)象時(shí), 需要經(jīng)過(guò) log2i +1 次排序碼比較, 才能確定它應(yīng)插入的位置。因此, 將 n 個(gè)對(duì)象(為推導(dǎo)方便, 設(shè)為 n=2k )用折半插入排序所進(jìn)行的排序碼比較次數(shù)為：折半插入排序是一個(gè)穩(wěn)定的排序方法。14當(dāng) n 較大時(shí), 總排序碼比較次數(shù)比直接插入排序的最壞情況要好得多, 但比其最好情況要差。在對(duì)象的初始排列已經(jīng)按排序碼排好序或接近

8、有序時(shí), 直接插入排序比折半插入排序執(zhí)行的排序碼比較次數(shù)要少。折半插入排序的對(duì)象移動(dòng)次數(shù)與直接插入排序相同, 依賴于對(duì)象的初始排列。討論：若記錄是鏈表結(jié)構(gòu)，折半插入排序可行嗎？鏈表無(wú)法“折半”！15希爾排序 (Shell Sort)希爾排序方法又稱為縮小增量排序。該方法的基本思想是 :對(duì)待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。 每一趟排序：將待排序序列分成若干子序列。子序列的構(gòu)成不是簡(jiǎn)單地“逐段分割”，而是將相隔某個(gè)增量的記錄組成一個(gè)子序列，然后對(duì)每個(gè)子序列進(jìn)行插入排序。 下一趟開(kāi)始前讓增量逐趟縮短（例如依次取5,3,1），直到增量1,用直接插入法做微觀調(diào)整。16例：關(guān)鍵字序列 T=(

9、49，38，65，97, 76, 13, 27, 49*，55, 04），請(qǐng)寫出希爾排序的具體實(shí)現(xiàn)過(guò)程。分析：開(kāi)始時(shí)dk 的值較大，子序列中的對(duì)象較少，排序速度較快,讓關(guān)鍵字值小的元素能很快前移，使序列基本有序；隨著排序進(jìn)展，dk 值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，只做局部調(diào)整即可，所以排序速度仍然很快。380123456789gap4938659776132749*5504531初態(tài)：第1趟 第2趟 第3趟 4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*

10、763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 ri17Gap的取法有多種。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。knuth 提出取 gap = gap/3 +1。還有人提出都取奇數(shù)為好，也有人提出各 gap 互質(zhì)為好。對(duì)特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算排序碼的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。18交換排序 ( Exchange Sort ) 基本思想是兩兩比較待排序?qū)ο蟮呐判虼a,如果發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之。直到所有對(duì)象都排好序?yàn)橹埂?9起泡排序 (

11、Bubble Sort)基本方法是：設(shè)待排序?qū)ο笮蛄兄械膶?duì)象個(gè)數(shù)為 n。最多作 n-1 趟，i = 1, 2, , n-1 。在第 i 趟中從后向前，j = n-1, n-2, , i，順次兩兩比較Vj-1.key和Vj.key。如果發(fā)生逆序，則交換Vj-1和Vj。優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能冒出一個(gè)最小值 (最大值)到最前(后)面位置，還能同時(shí)部分理順其他元素；一旦下趟沒(méi)有交換發(fā)生，還可以提前結(jié)束排序。20例如:2553157989i=613i=5i=n1221第i趟對(duì)待排序?qū)ο笮蛄蠽i-1,Vi,Vn-1進(jìn)行排序, 結(jié)果將該序列中排序碼最小(大)的對(duì)象交換到序列的第一個(gè)位置(i-1), 其它對(duì)

12、象也都向排序的最終位置移動(dòng)。在個(gè)別情形, 對(duì)象可能在排序中途向相反的方向移動(dòng)。最多做n-1趟起泡就能把所有對(duì)象排好序。起泡排序是一個(gè)穩(wěn)定的排序方法。22在對(duì)象的初始排列已經(jīng)按排序碼從小到大排好序時(shí),此算法只執(zhí)行一趟起泡,做n-1次排序碼比較,不移動(dòng)對(duì)象。這是最好的情形。最壞的情形是算法執(zhí)行n-1趟起泡,第i趟 (1 i n) 做 n- i 次排序碼比較, 執(zhí)行 n-i 次對(duì)象交換。這樣在最壞情形下總的排序碼比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN為：23快速排序 (Quick Sort)基本思想是任取待排序?qū)ο笮蛄兄械哪硞€(gè)對(duì)象 (例如取第一個(gè)對(duì)象) 作為基準(zhǔn), 按照該對(duì)象的排序碼大小, 將整個(gè)對(duì)象序

13、列劃分為左右兩個(gè)子序列： 左側(cè)子序列中所有對(duì)象的排序碼都小于或等于基準(zhǔn)對(duì)象的排序碼 。右側(cè)子序列中所有對(duì)象的排序碼都大于基準(zhǔn)對(duì)象的排序碼。24然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到每個(gè)子序列的元素只剩一個(gè)。此時(shí)便為有序序列了。優(yōu)點(diǎn)：因?yàn)槊刻丝梢源_定不止一個(gè)元素的位置，而且呈指數(shù)增加，所以特別快！25例：關(guān)鍵字序列 T=(21，25，49，25*，16，08），快速排序的算法步驟:( )21， 25， 49， 25*，16， 08初態(tài)：第1趟：第2趟：第3趟： 08， 16， 21，25* ， 25，(49)2108，16,，( )25* ，25，4908， (16)，21， 25* ，(

14、25，49)26算法quicksort是一個(gè)遞歸的算法, 其遞歸樹(shù)如圖所示。2125*25490816那么：一趟排序過(guò)程如何實(shí)現(xiàn)?27例：快速排序算法的一趟實(shí)現(xiàn)過(guò)程:21， 25， 49， 25*，16， 08初態(tài)：第1趟：(08，16)，21，(25*，25 ，49)21， 25， 49， 25*，16， 08初始序列： 0 1 2 3 4 5pivotposlowi21， 16， 49， 25*，25， 08循環(huán)4：pivotposi21， 16， 08， 25*，25， 49循環(huán)5：pivotpos(08 ，16)，21，(25*，25，49)出循環(huán)：pivotposlow28算法分析從

15、快速排序算法的遞歸樹(shù)可知, 快速排序的趟數(shù)取決于遞歸樹(shù)的高度。如果每次劃分對(duì)一個(gè)對(duì)象定位后, 該對(duì)象的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同, 則下 一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序, 這是最理想的情況。29在 n個(gè)元素的序列中, 對(duì)一個(gè)對(duì)象定位所需時(shí)間為 O(n)。若設(shè) T (n) 是對(duì) n 個(gè)元素的序列進(jìn)行排序所需的時(shí)間, 而且每次對(duì)一個(gè)對(duì)象正確定位后, 正好把序列劃分為長(zhǎng)度相等的兩個(gè)子序列, 此時(shí), 總的計(jì)算時(shí)間為：T(n) cn + 2T(n/2 ) / c 是一個(gè)常數(shù) cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4) 2cn + 4 ( cn/4 +

16、2T(n/8) ) = 3cn + 8T(n/8) cn log2n + nT(1) = O(n log2n )30快速排序是遞歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù)。最大遞歸調(diào)用層次數(shù)與遞歸樹(shù)的高度一致,理想情況為 log2(n+1) 。因此，要求存儲(chǔ)開(kāi)銷為 O(log2n)。31在最壞的情況, 即待排序?qū)ο笮蛄幸呀?jīng)按其排序碼從小到大排好序的情況下, 其遞歸樹(shù)成為單支樹(shù), 每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列。必須經(jīng)過(guò)n-1 趟才能把所有對(duì)象定位, 而且第 i 趟需要經(jīng)過(guò) n-i 次排序碼比較才能找到第 i 個(gè)對(duì)象的安放位置，總的排序碼比較次數(shù)將達(dá)到快速排序退化32用第一個(gè)

17、對(duì)象作為基準(zhǔn)對(duì)象 快速排序退化的例子 08 16 21 25 25* 49080 1 2 3 4 5 pivot初始 16 21 25 25* 49 0816 21 25 25* 4921 08 1625 25 25* 49 08 16 21 25* 4925* 08 16 21 2549 08 16 21 25 25*i = 1i = 2i = 3i = 4i = 533其排序速度退化到簡(jiǎn)單排序的水平, 比直接插入排序還慢。占用附加存儲(chǔ)(棧)將達(dá)到O(n)。改進(jìn)辦法: 取每個(gè)待排序?qū)ο笮蛄械牡谝粋€(gè)對(duì)象、最后一個(gè)對(duì)象和位置接近正中的 3 個(gè)對(duì)象，取其排序碼居中者作為基準(zhǔn)對(duì)象。34快速排序是一種

18、不穩(wěn)定的排序方法。對(duì)于 n 較大的平均情況而言, 快速排序是“快速”的, 但是當(dāng) n 很小時(shí), 這種排序方法往往比其它簡(jiǎn)單排序方法還要慢。用居中排序碼對(duì)象作為基準(zhǔn)對(duì)象 08 16 21 25 25* 490 1 2 3 4 5 pivot21初始 08 16 21 25 25* 490825* 08 16 21 25 25*49i = 1i = 235 基本思想是: 每一趟 (例如第 i 趟, i = 0, 1, , n-2) 在后面 n-i 個(gè)待排序?qū)ο笾羞x出排序碼最小的對(duì)象, 作為有序?qū)ο笮蛄械牡?i 個(gè)對(duì)象。待到第 n-2 趟作完, 待排序?qū)ο笾皇Ｏ?個(gè), 就不用再選了。選擇排序有序序列

19、r1.i-1無(wú)序序列 ri.n有序序列r1.i無(wú)序序列 ri+1.nrirk其排序碼最小36基本步驟： 在一組對(duì)象 ViVn-1 中選擇具有最小排序碼的對(duì)象； 若它不是這組對(duì)象中的第一個(gè)對(duì)象, 則將它與這組對(duì)象中的第一個(gè)對(duì)象對(duì)調(diào); 在這組對(duì)象中剔除這個(gè)具有最小排序碼的對(duì)象。在剩下的對(duì)象Vi+1Vn-1中重復(fù)執(zhí)行第、步, 直到剩余對(duì)象只有一個(gè)為止。直接選擇排序 (Select Sort)37例：關(guān)鍵字序列T= （21，25，49，25*，16，08），請(qǐng)給出簡(jiǎn)單選擇排序的具體實(shí)現(xiàn)過(guò)程。原始序列： 21，25，49，25*，16，08第1趟第2趟第3趟第4趟第5趟08，25，49，25*，16，2

20、108，16, 49，25*，25，2108，16, 21，25*，25，4908，16, 21，25*，25，4908，16, 21，25*，25，4938討論：能否利用（或記憶）首趟的n-1次比較所得信息，從而盡量減少后續(xù)比較次數(shù)呢？ 能！錦標(biāo)賽排序和堆排序！時(shí)間效率： O(n2)共n-1趟，第i趟比較n-i次。 空間效率： 無(wú)需任何附加單元！算法的穩(wěn)定性：不穩(wěn)定因?yàn)榕判驎r(shí)，25*到了25的前面。算法分析39錦標(biāo)賽排序 (Tournament Tree Sort)它的思想與體育比賽時(shí)的淘汰賽類似。首先取得 n 個(gè)對(duì)象的排序碼, 進(jìn)行兩兩比較, 得到 n/2 個(gè)比較的優(yōu)勝者(排序碼小者),

21、作為第一步比較的結(jié)果保留下來(lái)。然后對(duì)這 n/2 個(gè)對(duì)象再進(jìn)行排序碼的兩兩比較, , 如此重復(fù), 直到選出一個(gè)排序碼最小的對(duì)象為止。40勝者樹(shù)的概念每次兩兩比較的結(jié)果是把排序碼小者作為優(yōu)勝者上升到雙親結(jié)點(diǎn)，稱這種比賽樹(shù)為勝者樹(shù)。位于最底層的葉結(jié)點(diǎn)叫做勝者樹(shù)的外結(jié)點(diǎn)，非葉結(jié)點(diǎn)稱為勝者樹(shù)的內(nèi)結(jié)點(diǎn)。勝者樹(shù)最頂層是樹(shù)的根，表示最后選擇出來(lái)的具有最小排序碼的對(duì)象。4108Winner (勝者)2108086325*2121254925*160863r1初態(tài)：補(bǔ)足葉子結(jié)點(diǎn)，使其為滿二叉樹(shù)第一趟：勝者樹(shù)例：關(guān)鍵字序列T= （21，25，49，25*，16，08，63），請(qǐng)給出錦標(biāo)賽排序的具體實(shí)現(xiàn)過(guò)程。42第二

22、趟：082108086325*2121254925*160863161616r2Winner (勝者)令其Active 0,不參與比較43令其Active 0,不參與比較第三趟：162116166325*2121254925*160863r3Winner (勝者)632144082108086325*2121254925*1608636321第四趟：r4Winner (勝者)25252545082108086325*2121254925*1608631616166321252525第五趟：r5Winner (勝者)25*25*46082108086325*2121254925*16086316

23、1616632125252525*25*第六趟：r6Winner (勝者)49494947082108086325*2121254925*160863161616632125252525*25*494949第七趟：r7Winner (勝者)6348錦標(biāo)賽排序構(gòu)成的勝者樹(shù)是滿的完全二叉樹(shù), 其深度為 log2n , 其中 n 為待排序元素個(gè)數(shù)。除第一次選擇具有最小排序碼的對(duì)象需要進(jìn)行 n-1 次排序碼比較外, 重構(gòu)勝者樹(shù)選擇具有次小、再次小排序碼對(duì)象所需的排序碼比較次數(shù)均為 O(log2n)。總排序碼比較次數(shù)為O(nlog2n)。對(duì)象的移動(dòng)次數(shù)不超過(guò)排序碼的比較次數(shù)，所以錦標(biāo)賽排序總時(shí)間復(fù)雜度為

24、O(nlog2n)。49這種排序方法雖然減少了許多排序時(shí)間, 但是使用了較多的附加存儲(chǔ)。如果有 n 個(gè)對(duì)象，必須使用至少 2n-1 個(gè)結(jié)點(diǎn)來(lái)存放勝者樹(shù)。最多需要找到滿足 2k-1 n 2k 的k，使用 2*2k-1 個(gè)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)包括排序碼、結(jié)點(diǎn)序號(hào)和比較標(biāo)志三種信息。錦標(biāo)賽排序是一個(gè)穩(wěn)定的排序方法。50堆 ( Heap )優(yōu)先級(jí)隊(duì)列 線性結(jié)構(gòu)：隊(duì)尾插入，隊(duì)頭刪除 每次出隊(duì)列的是優(yōu)先權(quán)最高（低）的元素 數(shù)組表示，效率低堆排序51堆的定義098778456531532317012345678098778456531235317012345678完全二叉樹(shù)順序表示，滿足：Ki K2i+1 & K

25、i K2i+1 &Ki K2i+2 Ki K2i+252最小堆的類定義# define DefaultSize 10 ;template class MinHeap : public MinPQ private: Type * heap; /存放最小堆元素的數(shù)組 int CurrentSize; /最小堆當(dāng)前元素個(gè)數(shù) int MaxHeapSize; /最多允許元素個(gè)數(shù) void FilterDown ( int i, int m ); /從 i 到m自頂向下進(jìn)行調(diào)整成為最小堆 53 void FilterUp ( int i ); /從 i 到0自底向上進(jìn)行調(diào)整成為最小堆public: Mi

26、nHeap ( int sz ); /構(gòu)造函數(shù) : 建立空堆 MinHeap ( Type arr , int n ); /構(gòu)造函數(shù) MinHeap ( ) delete heap; const MinHeap & operator = (const MinHeap &R) int Insert ( const Type& x ); /插入 int RemoveMin ( Type& x ); /刪除 54 int IsEmpty ( ) const /判堆空否 return CurrentSize = 0; int IsFull ( ) const /判堆滿否 return CurrentS

27、ize = MaxHeapSize; void MakeEmpty ( ) CurrentSize = 0; 55堆的建立1. 建一個(gè)空堆template MinHeap :MinHeap ( int maxSize ) /根據(jù)給定大小maxSize,建立堆對(duì)象 MaxHeapSize = DefaultSize maxSize ? maxSize : DefaultSize; /確定堆的大小 heap = new Type MaxHeapSize; CurrentSize = 0; 562. 復(fù)制數(shù)組并加以調(diào)整形成堆template MinHeap : MinHeap ( Type arr

28、, int n ) /根據(jù)給定數(shù)組中的數(shù)據(jù)和大小,建立堆對(duì)象 MaxHeapSize = DefaultSize = 0 ) /從下到上逐步擴(kuò)大,形成堆 FilterDown ( currentPos, CurrentSize-1 ); /從currentPos開(kāi)始,到CurrentSize止, /調(diào)整 currentPos-; 5317780923456587icurrentPos = i = 30123456758最小堆的向下調(diào)整算法template void MinHeap : FilterDown ( int start, int EndOfHeap ) int i = start,

29、j = 2*i+1; / j 是 i 的左子女 Type temp = heapi; while ( j = EndOfHeap ) if ( j heapj+1 ) j+; /兩子女中選小者 if ( temp.key = heapj.key ) break; else heapi = heapj; i = j; j = 2*j+1; heapi = temp; 59自下向上逐步調(diào)整為最小堆將一組用數(shù)組存放的任意數(shù)據(jù)調(diào)整成堆5317780923456587icurrentPos = i = 3012345675317780923456587currentPos = i = 2i0123456

30、7605317780923456587icurrentPos = i = 1012345675317780923456587i01234567615317780923456587icurrentPos = i = 00123456717780923456587i0901334567536217780923456587i17012345675317780923456587i012345675363堆的插入template int MinHeap : Insert ( const Type &x ) /在堆中插入新元素 x if ( CurrentSize = MaxHeapSize ) /堆滿

31、cerr 堆已滿 endl; return 0; heapCurrentSize = x; /插在最后 FilterUp (CurrentSize); /向上調(diào)整為堆 CurrentSize+; /堆計(jì)數(shù)增1 return 1;64最小堆的向上調(diào)整算法template void MinHeap : FilterUp ( int start ) /從 start 開(kāi)始,向上直到0,調(diào)整堆 int j = start, i = (j-1)/2; / i 是 j 的雙親 Type temp = heapj; while ( j 0 ) if ( heapi = temp ) break; else

32、heapj = heapi; j = i; i = (i -1)/2; heapj = temp;6517780923456587i11在堆中插入新元素1153j最小堆的向上調(diào)整0123456785317780923456587j23i0123456781166177809456587j53i2317531178092345658723ji0123456781167最小堆的刪除算法template int MinHeap :Remove ( Type &x ) if ( !CurrentSize ) cout “ 堆已空 endl; return 0; x = heap0; /最小元素出隊(duì)列

33、heap0 = heapCurrentSize-1; /用最后元素 CurrentSize-; /填補(bǔ) FilterDown ( 0, CurrentSize-1 ); /調(diào)整 return 1;68利用堆及其運(yùn)算, 可以很容易地實(shí)現(xiàn)選擇排序的思路。堆排序分為兩個(gè)步驟 根據(jù)初始輸入數(shù)據(jù)，利用堆的調(diào)整算法 FilterDown( ) 形成初始堆; 通過(guò)一系列的對(duì)象交換和重新調(diào)整堆進(jìn)行排序。堆排序 (Heap Sort)69建立初始的最大堆212525*491608012345i21 25 49 25* 16 08初始排序碼集合i212525*16490802543121 25 49 25* 16

34、 08i = 2 時(shí)的局部調(diào)整70i212525*49160801234521 25 49 25* 16 08i = 1 時(shí)的局部調(diào)整492525*16210802543149 25 21 25* 16 08i = 0 時(shí)的局部調(diào)整形成最大堆71基于初始堆進(jìn)行堆排序最大堆堆頂V0具有最大的排序碼, 將V0與 Vn-1對(duì)調(diào), 把具有最大排序碼的對(duì)象交換到最后, 再對(duì)前面的n-1個(gè)對(duì)象, 使用堆的調(diào)整算法FilterDown(0, n-2), 重新建立最大堆, 具有次最大排序碼的對(duì)象又上浮到V0位置。再對(duì)調(diào)V0和Vn-2,調(diào)用FilterDown(0, n-3), 對(duì)前n-2個(gè)對(duì)象重新調(diào)整，。如此

35、反復(fù)執(zhí)行，最后得到全部排序好的對(duì)象序列。這個(gè)算法即堆排序算法。72082525*16214902543108 25 21 25* 16 49交換 0 號(hào)與 5 號(hào)對(duì)象,5 號(hào)對(duì)象就位492525*21160801234549 25 21 25* 16 08初始最大堆731625*0825214902543116 25* 21 08 25 49交換 0 號(hào)與 4 號(hào)對(duì)象,4 號(hào)對(duì)象就位2525*0821164901234525 25* 21 08 16 49從 0 號(hào)到 4 號(hào) 重新調(diào)整為最大堆74081625*25214902543108 16 21 25* 25 49交換 0 號(hào)與 3 號(hào)對(duì)

36、象,3 號(hào)對(duì)象就位25*160821254901234525* 16 21 08 25 49從 0 號(hào)到 3 號(hào) 重新調(diào)整為最大堆753211625*08254901234521 16 08 25* 25 49從 0 號(hào)到 2 號(hào) 重新調(diào)整為最大堆081625*2521490254108 16 21 25* 25 49交換 0 號(hào)與 2 號(hào)對(duì)象,2 號(hào)對(duì)象就位76081625*25214902543108 16 21 25* 25 49交換 0 號(hào)與 1 號(hào)對(duì)象,1 號(hào)對(duì)象就位160825*21254901234516 08 21 25* 25 49從 0 號(hào)到 1 號(hào) 重新調(diào)整為最大堆77若

37、設(shè)堆中有 n 個(gè)結(jié)點(diǎn), 且 2k-1 n 2k, 則對(duì)應(yīng)的完全二叉樹(shù)有 k 層。在第 i 層上的結(jié)點(diǎn)數(shù) 2i (i = 0, 1, , k-1)。 在第一個(gè)形成初始堆的 for 循環(huán)中對(duì)每一個(gè)非葉結(jié)點(diǎn)調(diào)用了 一次堆調(diào)整算法FilterDown( ), 因此該循環(huán)所用的計(jì)算時(shí)間為：其中, i 是層序號(hào), 2i 是第 i 層的最大結(jié)點(diǎn)數(shù), (k-i-1)是第 i 層結(jié)點(diǎn)能夠移動(dòng)的最大距離。78第二個(gè)for循環(huán)中調(diào)用了n-1次FilterDown( )算法, 該循環(huán)的計(jì)算時(shí)間為O(nlog2n)。因此, 堆排序的時(shí)間復(fù)雜性為O(nlog2n)。該算法的附加存儲(chǔ)主要是在第二個(gè)for循環(huán)中用來(lái)執(zhí)行對(duì)象交

38、換時(shí)所用的一個(gè)臨時(shí)對(duì)象。因此，該算法的空間復(fù)雜性為O(1)。堆排序是一個(gè)不穩(wěn)定的排序方法。79歸并排序 (Merge Sort)歸并，是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。例:對(duì)象序列initList中兩個(gè)有序表Vl Vm和Vm+1 Vn。它們可歸并成一個(gè)有序表, 存于另一對(duì)象序列mergedList的Vl Vn中。這種歸并方法稱為兩路歸并(2-way merging)。設(shè)變量 i 和 j 分別是表Vl Vm和Vm+1 Vn的當(dāng)前檢測(cè)指針。變量 k 是存放指針。8008 21 25 25* 49 62 72 93 16 37 54 left mid mid+1 rightinitLi

39、sti j08 16 21 25 25* 37 49 54 62 72 93 left rightkmergeList當(dāng) i 和 j 都在兩個(gè)表的表長(zhǎng)內(nèi)變化時(shí), 根據(jù)對(duì)應(yīng)項(xiàng)的排序碼的大小, 依次把排序碼小的對(duì)象排放到新表 k 所指位置中；當(dāng) i 與 j 中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí)，將另一 個(gè)表中的剩余部分照抄到新表中。81迭代的歸并排序算法迭代的歸并排序算法就是利用兩路歸并過(guò)程進(jìn)行排序的。其基本思想是：假設(shè)初始對(duì)象序列有 n 個(gè)對(duì)象，首先把它看成是 n 個(gè)長(zhǎng)度為 1 的有序子序列 (歸并項(xiàng))，先做兩兩歸并，得到 n / 2 個(gè)長(zhǎng)度為 2 的歸并項(xiàng) (如果 n 為奇數(shù)，則最后一個(gè)有序子序列的長(zhǎng)度為1

40、)；再做兩兩歸并，如此重復(fù)，最后得到一個(gè)長(zhǎng)度為 n 的有序序列。82迭代的歸并排序算法212525*9362720837165449len=1212525*4962930872163754len=2212525*4908627293len=416375408212525*49627293len=80816212525*374954627293len=1616375483在迭代的歸并排序算法中, 函數(shù)MergePass( ) 做一趟兩路歸并排序, 要調(diào)用merge ( )函數(shù) n/(2*len) O(n/len) 次, 函數(shù)MergeSort( )調(diào)用MergePass( )正好log2n 次,

41、而每次merge( )要執(zhí)行比較O(len)次, 所以算法總的時(shí)間復(fù)雜度為O(nlog2n)。歸并排序占用附加存儲(chǔ)較多, 需要另外一個(gè)與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組。這是這個(gè)算法的缺點(diǎn)。歸并排序是一個(gè)穩(wěn)定的排序方法。84遞歸的表歸并排序與快速排序類似，歸并排序也可以利用劃分為子序列的方法遞歸實(shí)現(xiàn)。在遞歸的歸并排序方法中，首先要把整個(gè)待排序序列劃分為兩個(gè)長(zhǎng)度大致相等的部分，分別稱之為左子表和右子表。對(duì)這些子表分別遞歸地進(jìn)行排序，然后再把排好序的兩個(gè)子表進(jìn)行歸并。圖示：待排序?qū)ο笮蛄械呐判虼a為 21, 25, 49, 25*,16, 08 ，先是進(jìn)行子表劃分，待到子表中只有一個(gè)對(duì)象時(shí)遞歸到底

42、。再是實(shí)施歸并，逐步退出遞歸調(diào)用的過(guò)程。8521 25 49 25* 16 08 21 25 49 25* 16 08 21 25 49 25 49 21 25* 16 08 25* 16 08 21 25 49 25* 16 08 16 08 25* 25 49 21 遞歸 21 25* 16 08 49 25 25* 16 08 21 25 49 回退86基數(shù)排序 (Radix Sort)基數(shù)排序是采用“分配”與“收集”的辦法，用對(duì)多排序碼進(jìn)行排序的思想實(shí)現(xiàn)對(duì)單排序碼進(jìn)行排序的方法。多排序碼排序以撲克牌排序?yàn)槔Ｃ繌垞淇伺朴袃蓚€(gè)“排序碼”：花色和面值。其有序關(guān)系為： 花色： 面值：2 3

43、4 5 6 7 8 9 10 J Q K A87如果我們把所有撲克牌排成以下次序： 2, , A, 2, , A, 2, , A, 2, , A這就是多排序碼排序。排序后形成的有序序列叫做詞典有序序列。對(duì)于上例兩排序碼的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。一般情況下，假定有一個(gè) n 個(gè)對(duì)象的序列 V0, V1, , Vn-1 ，且每個(gè)對(duì)象Vi 中含有 d 個(gè)排序碼。88如果對(duì)于序列中任意兩個(gè)對(duì)象Vi 和Vj (0 i j n-1 ) 都滿足：則稱序列對(duì)排序碼 (K1, K2, , Kd) 有序。其中，K1 稱為最高位排序碼，Kd 稱為最低位排序碼。如果排

44、序碼是由多個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)項(xiàng)組，則依據(jù)它進(jìn)行排序時(shí)就需要利用多排序碼排序。89實(shí)現(xiàn)多排序碼排序有兩種常用的方法最高位優(yōu)先MSD ( Most Significant Digit first )。最低位優(yōu)先LSD ( Least Significant Digit first)。90最高位優(yōu)先法通常是一個(gè)遞歸的過(guò)程：先根據(jù)最高位排序碼 K1排序, 得到若干對(duì)象組, 對(duì)象組中各對(duì)象都有相同排序碼K1。再分別對(duì)每組中對(duì)象根據(jù)排序碼 K2 進(jìn)行排序, 按 K2 值的不同, 再分成若干個(gè)更小的子組, 每個(gè)子組中的對(duì)象具有相同的 K1和 K2值。依此重復(fù), 直到對(duì)排序碼Kd完成排序?yàn)橹埂?最后, 把所有

45、子組中的對(duì)象依次連接起來(lái)，就得到一個(gè)有序的對(duì)象序列。91最低位優(yōu)先法首先依據(jù)最低位排序碼Kd對(duì)所有對(duì)象進(jìn)行一趟排序，再依據(jù)次低位排序碼Kd-1對(duì)上一趟排序的結(jié)果再排序，依次重復(fù)，直到依據(jù)排序碼K1最后一趟排序完成，就可以得到一個(gè)有序的序列。使用這種排序方法對(duì)每一個(gè)排序碼進(jìn)行排序時(shí)，不需要再分組，而是整個(gè)對(duì)象組都參加排序。LSD和MSD方法也可應(yīng)用于對(duì)一個(gè)排序碼進(jìn)行的排序。此時(shí)可將單排序碼 Ki 看作是一個(gè)子排序碼組：92基數(shù)排序是典型的LSD排序方法, 利用“分配”和“收集”對(duì)單排序碼進(jìn)行排序。在這種方法中，把單排序碼 Ki 看成是一個(gè)d元組：其中的每一個(gè)分量 ( 1 j d ) 也可看成是一

46、個(gè)排序碼。鏈?zhǔn)交鶖?shù)排序93分量 (1 j d) 有radix種取值, 稱radix為基數(shù)。例如, 排序碼984可以看成是一個(gè)3元組(9, 8, 4), 每一位有 0, 1, , 9 等10種取值, 基數(shù)radix = 10。排序碼data可以看成是一個(gè)4元組(d, a, t, a), 每一位有a, b, , z等26種取值，radix = 26。針對(duì)d元組中的每一位分量, 把對(duì)象序列中的所有對(duì)象, 按 的取值，先“分配”到rd個(gè)隊(duì)列中去。然后再按各隊(duì)列的順序，依次把對(duì)象從隊(duì)列中“收集”起來(lái)，這樣所有對(duì)象按取值 排序完成。94如果對(duì)于所有對(duì)象的排序碼K0, K1, , Kn-1, 依次對(duì)各位的分

47、量, 讓 j = d, d-1, , 10, 分別用“分配”、“收集”的運(yùn)算逐趟進(jìn)行排序，在最后一趟“分配”、“收集” 完成后, 所有對(duì)象就按其排序碼的值從小到大排好序了。各隊(duì)列采用鏈?zhǔn)疥?duì)列結(jié)構(gòu), 分配到同一隊(duì)列的排序碼用鏈接指針鏈接起來(lái)。每一隊(duì)列設(shè)置兩 個(gè)隊(duì)列指針： int front radix指示隊(duì)頭， int rear radix 指向隊(duì)尾。為了有效地存儲(chǔ)和重排 n 個(gè)待排序?qū)ο螅造o態(tài)鏈表作為它們的存儲(chǔ)結(jié)構(gòu)。95基數(shù)排序的“分配”與“收集”過(guò)程 第一趟614921485637738101215530790306第一趟分配（按最低位 i = 3 ）re0 re1 re2 re3 re4

48、 re5 re6 re7 re8 re9614738921485637101215530790306fr0 fr1 fr2 fr3 fr4 fr5 fr6 fr7 fr8 fr9第一趟收集53079092110161448521530663773896基數(shù)排序的“分配”與“收集”過(guò)程 第二趟614921485637738101215530790306第二趟分配（按次低位 i = 2 ）re0 re1 re2 re3 re4 re5 re6 re7 re8 re9614738921485637101215530790306fr0 fr1 fr2 fr3 fr4 fr5 fr6 fr7 fr8 f

49、r9第二趟收集53079092110161448521530663773897基數(shù)排序的“分配”與“收集”過(guò)程 第三趟614921485637738101215530790306第三趟分配（按最高位 i = 1 ）re0 re1 re2 re3 re4 re5 re6 re7 re8 re9614738921485637101215530790306fr0 fr1 fr2 fr3 fr4 fr5 fr6 fr7 fr8 fr9第三趟收集53079092110161448521530663773898各種排序方法的比較99外排序100 當(dāng)待排序的對(duì)象數(shù)目特別多時(shí)，在內(nèi)存中不能一次處理。必須把它們

50、以文件的形式存放于外存，排序時(shí)再把它們一部分一部分調(diào)入內(nèi)存進(jìn)行處理。這樣，在排序過(guò)程中必須不斷地在內(nèi)存與外存之間傳送數(shù)據(jù)。這種基于外部存儲(chǔ)設(shè)備（或文件）的排序技術(shù)就是外排序。當(dāng)對(duì)象以文件形式存放于磁盤上的時(shí)候, 通常是按物理塊存儲(chǔ)的。物理塊也叫做頁(yè)塊。每個(gè)頁(yè)塊可存放幾個(gè)對(duì)象。操作系統(tǒng)按頁(yè)塊對(duì)磁盤信息進(jìn)行讀寫。磁盤通常是指由若干片磁盤組成的磁盤組, 各個(gè)盤片安裝在同一主軸上高速旋轉(zhuǎn)。各個(gè)盤面上半徑相同的磁道構(gòu)成了柱面。各盤面設(shè)置一個(gè)讀寫磁頭，它們裝在同一動(dòng)臂上，可以徑向從一個(gè)柱面移到另一個(gè)柱面上。外排序的基本過(guò)程101為了訪問(wèn)某一頁(yè)塊, 先尋找柱面: 移動(dòng)動(dòng)臂使讀寫磁頭移到指定柱面上: 尋查(s

51、eek)。再根據(jù)磁道號(hào)(盤面號(hào))選擇相應(yīng)讀寫磁頭, 等待指定頁(yè)塊轉(zhuǎn)到讀寫磁頭下: 等待(latency)。 在磁盤組上存取一個(gè)頁(yè)塊的時(shí)間：102tiotseektlatencytrw基于磁盤進(jìn)行的排序多使用歸并排序方法。其排序過(guò)程主要分為兩個(gè)階段： 建立用于外排序的內(nèi)存緩沖區(qū)。根據(jù)它們的大小將輸入文件劃分為若干段, 用某種內(nèi)排序方法對(duì)各段進(jìn)行排序。經(jīng)過(guò)排序的段叫做初始?xì)w并段或初始順串 (Run)。當(dāng)它們生成后就被寫到外存中去。 仿照歸并樹(shù)模式, 把 生成的初始?xì)w并段加以歸并, 一趟趟地?cái)U(kuò)大歸并段和減少歸并段個(gè)數(shù), 直到最后歸并成一個(gè)大歸并段(有序文件)為止。103示例：設(shè)有一個(gè)包含4500個(gè)對(duì)

52、象的輸入文件?，F(xiàn)用一臺(tái)其內(nèi)存至多可容納750個(gè)對(duì)象的計(jì)算機(jī)對(duì)該文件進(jìn)行排序。輸入文件放在磁盤上,磁盤每個(gè)頁(yè)塊可容納250個(gè)對(duì)象, 這樣全部對(duì)象可存儲(chǔ)在 4500 / 25018 個(gè)頁(yè)塊中。輸出文件也放在磁盤上, 用以存放歸并結(jié)果。由于內(nèi)存中可用于排序的存儲(chǔ)區(qū)域能容納750 個(gè)對(duì)象, 因此內(nèi)存中恰好能存3個(gè)頁(yè)塊的對(duì)象。在外排序一開(kāi)始, 把18塊對(duì)象, 每3塊一組, 讀入內(nèi)存。利用某種內(nèi)排序方法進(jìn)行內(nèi)排序, 形成初始?xì)w并段, 再寫回外存。總共可得到6個(gè)初始?xì)w并段。然后一趟一趟進(jìn)行歸并排序。104兩路歸并排序的歸并樹(shù)R1 750 R2 750 R3 750 R4 750 R5 750 R6 750初

53、始?xì)w并段R12 1500 R34 1500 R56 1500R1234 3000R123456 4500第一趟歸并結(jié)果 第二趟歸并結(jié)果 第三趟歸并結(jié)果 105若把內(nèi)存區(qū)域等份地分為 3 個(gè)緩沖區(qū)。其中的兩個(gè)為輸入緩沖區(qū), 一個(gè)為輸出緩沖區(qū), 可以在內(nèi)存中利用簡(jiǎn)單 2 路歸并函數(shù) merge( ) 實(shí)現(xiàn) 2 路歸并。首先, 從參加歸并排序的兩個(gè)輸入歸并段 R1 和 R2 中分別讀入一塊, 放在輸入緩沖區(qū)1 和輸入緩沖區(qū)2 中。然后在內(nèi)存中進(jìn)行 2 路歸并，歸并結(jié)果順序存放到輸出緩沖區(qū)中。106輸入緩沖區(qū) 2輸入緩沖區(qū) 1輸出緩沖區(qū)k路平衡歸并 (k-way Balanced merging)做

54、k 路平衡歸并時(shí), 如果有 m 個(gè)初始?xì)w并段, 則相應(yīng)的歸并樹(shù)有 logkm +1 層, 需要?dú)w并logkm 趟。下圖給出對(duì)有 36 個(gè)初始?xì)w并段的文件做 6 路平衡歸并時(shí)的歸并樹(shù)。107做內(nèi)部 k 路歸并時(shí), 在 k 個(gè)對(duì)象中選擇最小者，需要順序比較 k-1 次。每趟歸并 n 個(gè)對(duì)象需要做(n-1)*(k-1)次比較, S 趟歸并總共需要的比較次數(shù)為: S*(n-1)*(k-1) = logkm * (n-1) * (k-1) = log2m * (n-1) * (k-1) / log2k 在初始?xì)w并段個(gè)數(shù) m 與對(duì)象個(gè)數(shù) n 一定時(shí), log2m*(n-1) = const, 而 (k-1

55、) / log2k 在 k 增大時(shí)趨于無(wú)窮大。因此, 增大歸并路數(shù) k, 會(huì)使得內(nèi)部歸并的時(shí)間增大。108使用“敗者樹(shù)”從 k 個(gè)歸并段中選最小者, 當(dāng) k 較大時(shí) (k 6)，選出排序碼最小的對(duì)象只需比較 log2k 次。 S*(n-1)*log2k = logkm * (n-1) * log2k = log2m * (n-1) * log2k / log2k = log2m * (n-1)排序碼比較次數(shù)與 k 無(wú)關(guān), 總的內(nèi)部歸并時(shí)間不會(huì)隨 k 的增大而增大。下面討論利用敗者樹(shù)在 k 個(gè)輸入歸并段中選擇最小者，實(shí)現(xiàn)歸并排序的方法。109 敗者樹(shù)是一棵完全二叉樹(shù)。其中 每個(gè)葉結(jié)點(diǎn)存放各歸并段

56、在歸并過(guò)程中當(dāng)前參加比較的對(duì)象； 每個(gè)非葉結(jié)點(diǎn)記憶它兩個(gè)子女結(jié)點(diǎn)中對(duì)象排序碼小的結(jié)點(diǎn)(即敗者)；因此，根結(jié)點(diǎn)中記憶樹(shù)中當(dāng)前對(duì)象排序碼最小的結(jié)點(diǎn) (最小對(duì)象)。示例：設(shè)有 5 個(gè)初始?xì)w并段, 它們中各對(duì)象的排序碼分別是：110 111Run0: 17, 21, Run1: 05, 44, Run2: 10, 12, Run3: 29, 32, Run4: 15, 56, 29321556172105441012151005172930241k3k4k0k1k2Run3Run4Run0Run1Run2ls1ls0ls2ls4ls3冠軍 (最小對(duì)象),輸出段1當(dāng)前對(duì)象選中輸出段1最小對(duì)象，段1下一對(duì)

57、象參選，調(diào)整敗者樹(shù)11229321556172105441012151044172930142k3k4k0k1k2Run3Run4Run0Run1Run2ls1ls0ls2ls4ls3次最小對(duì)象選中初始?xì)w并段的生成 (Run Generation)為減少讀寫磁盤次數(shù), 除增加歸并路數(shù) k 外, 還可減少初始?xì)w并段個(gè)數(shù)m。在總對(duì)象數(shù)n 一定時(shí), 要減少m, 必須增大初始?xì)w并段長(zhǎng)度。如果規(guī)定每個(gè)初始?xì)w并段等長(zhǎng), 則此長(zhǎng)度應(yīng)根據(jù)生成它的內(nèi)存工作區(qū)空間大小而定, 因而m的減少也就受到了限制。為了突破這個(gè)限制, 可采用敗者樹(shù)來(lái)生成初始?xì)w并段。在使用同樣大內(nèi)存工作區(qū)的情況下, 可以生成平均比原來(lái)等長(zhǎng)情況下大一倍的初始?xì)w并段, 從而減少初始?xì)w并段個(gè)數(shù)。113設(shè)輸入文件FI中各對(duì)象的排序碼序列為 17, 21, 05, 44, 10, 12, 56, 32, 29 。選擇和置換過(guò)程的步驟如下： 從輸入文件FI中把 k 個(gè)對(duì)象讀入內(nèi)存中, 并構(gòu)造敗者樹(shù)。(內(nèi)存中存放對(duì)象的數(shù)組r可容納的對(duì)象個(gè)數(shù)為 k )。 利用敗者樹(shù)在 r 中選擇一個(gè)