數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：Chapter Nine Sorting

1、數(shù)據(jù)結(jié)構(gòu)Chapter Nine Sorting引基本術(shù)語插入排序交換排序選擇排序 堆排序(Heap Sort) 二路歸并排序 基數(shù)排序外排序 排序：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。 數(shù)據(jù)表(datalist): 它是待排序數(shù)據(jù)對象的有限集合。關(guān)鍵碼(key): 通常數(shù)據(jù)對象有多個屬性域，即多個數(shù)據(jù)成員組成，其中有一個屬性域可用來區(qū)分對象，作為排序依據(jù)。該域即為關(guān)鍵碼。每個數(shù)據(jù)表用哪個屬性域作為關(guān)鍵碼，要視具體的應(yīng)用需要而定。即使是同一個表，在解決不同問題的場合也可能取不同的域做關(guān)鍵碼。1、基本術(shù)語主關(guān)鍵碼: 如果在數(shù)據(jù)表中各個對象的關(guān)鍵碼互不相同，這種關(guān)鍵碼即主關(guān)鍵碼。按照主關(guān)

2、鍵碼進行排序，排序的結(jié)果是唯一的。次關(guān)鍵碼: 數(shù)據(jù)表中有些對象的關(guān)鍵碼可能相同，這種關(guān)鍵碼稱為次關(guān)鍵碼。按照次關(guān)鍵碼進行排序，排序的結(jié)果可能不唯一。排序算法的穩(wěn)定性: 如果在對象序列中有兩個對象ri和rj，它們的關(guān)鍵碼 ki = kj，且在排序之前，對象ri排在rj前面。如果在排序之后，對象ri仍在對象rj的前面，則稱這個排序方法是穩(wěn)定的，否則稱這個排序方法是不穩(wěn)定的。1、基本術(shù)語內(nèi)排序與外排序: 內(nèi)排序是指在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對象個數(shù)太多，不能同時存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動的排序。排序的時間開銷: 排序的時間開銷是衡

3、量算法好壞的最重要的標(biāo)志。排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。各節(jié)給出算法運行時間代價的大略估算一般都按平均情況進行估算。對于那些受對象關(guān)鍵碼序列初始排列及對象個數(shù)影響較大的，需要按最好情況和最壞情況進行估算。1、基本術(shù)語靜態(tài)排序: 排序的過程是對數(shù)據(jù)對象本身進行物理地重排，經(jīng)過比較和判斷，將對象移到合適的位置。這時，數(shù)據(jù)對象一般都存放在一個順序的表中。動態(tài)排序: 給每個對象增加一個鏈接指針，在排序的過程中不移動對象或傳送數(shù)據(jù)，僅通過修改鏈接指針來改變對象之間的邏輯順序，從而達到排序的目的。算法執(zhí)行時所需的附加存儲: 評價算法好壞的另一標(biāo)準(zhǔn)。靜態(tài)排序過程中所用到的數(shù)

4、據(jù)表類定義，體現(xiàn)了抽象數(shù)據(jù)類型的思想。1、基本術(shù)語基本思想：2、插入排序每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。包括：直接插入排序 (Insert Sort)折半插入排序(Binary Insert sort)鏈表插入排序希爾排序 (Shell Sort)直接插入排序 (Insert Sorting)2、插入排序直接插入排序基本思想：僅有一個記錄的表總是有序的，因此，對n個記錄的表，可從第二個記錄開始直到第n個記錄，逐個向有序表中進行插入操作，從而得到n個記錄按關(guān)鍵碼有序的表。i=7 (13 38 49 65 76 97) 27

5、9776654938272、插入排序直接插入排序49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( ) 27jjjjjj (13 27 38 49 65 76 97)排序結(jié)果：算法圖示：算法： (insertSort.cpp)2、插入排序直接插入排序typedef struct int key; float

6、info; JD;void insertsort(JD r,int n) int i,j; for(i=2;i=n;i+) r0=ri; j=i-1; while(r0.keyrj.key) rj+1=rj; j-; rj+1=r0; 2、插入排序直接插入排序算法評估：最好情況下：排序前對象已經(jīng)按關(guān)鍵碼大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械淖詈笠粋€對象的關(guān)鍵碼比較 1 次，移動 2 次對象，總的關(guān)鍵碼比較次數(shù)為 n-1，對象移動次數(shù)為 2(n-1)。2、插入排序直接插入排序算法評估：最壞情況下：第 i 趟時第 i 個對象必須與前面 i 個對象都做關(guān)鍵碼比較，并且每做 1 次比較就要做

7、 1 次數(shù)據(jù)移動。則總的關(guān)鍵碼比較次數(shù)KCN 和對象 移動次數(shù)RMN分別為2、插入排序直接插入排序算法評估：若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵碼比較次數(shù)和對象移動次數(shù)約為 n2/4。因此，直接插入排序的時間復(fù)雜度為 o(n2)。直接插入排序是一種穩(wěn)定的排序方法。2、插入排序折半插入排序折半插入排序 (Insert Sorting)基本思想：直接插入排序的插入位置的確定通過對有序表中記錄按關(guān)鍵碼逐個比較得到的，平均情況下總比較次數(shù)約為n2/4。既然是在有序表中確定插入位置，可以不斷折半查找來確定插入位置。算法圖示：i=1 (3

8、0) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20.i=8 20 (6 13 30 39 42 70 85 ) 20LHMi=8 20 (6 13 30 39 42 70 85 ) 20LHMMLHi=8 20 (6 13 30 39 42 70 85 ) 20i=8 20 (6 13 30 39 42 70 85 ) 20LHi=8 20 (6 13 20 30 39 42 70 85 )2、插入排序折半插入排序2、插入排序折半插入排序算法： (binarySort.cpp)

9、void binsort(JD r,int n) int i, k ; int high,low,mid;for(i=2;i=n;i+) r0=ri; low=1; high=i-1; while(low=high) mid=(low+high)/2;if(ri.key=low;k-) rk+1=rk; rlow=r0; 2、插入排序折半插入排序算法評估：對分查找比順序查找快，所以對分插入排序就平均性能來說比直接插入排序要快。它所需要的關(guān)鍵碼比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān)，僅依賴于對象個數(shù)。在插入第 i 個對象時，需要經(jīng)過 log2i +1 次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置。因此，

10、將 n 個對象（為推導(dǎo)方便，設(shè)為 n=2k )用對分插入排序所進行的關(guān)鍵碼比較次數(shù)為：nlog2n2、插入排序折半插入排序算法評估：當(dāng) n 較大時，總關(guān)鍵碼比較次數(shù)比直接插入排序的最壞情況要好得多，但比其最好情況要差。 在對象的初始排列已經(jīng)按關(guān)鍵碼排好序或接近有序時，直接插入排序比對分插入排序執(zhí)行的關(guān)鍵碼比較次數(shù)要少。對分插入排序的對象移動次數(shù)與直接插入排序相同，依賴于對象的初始排列。 折半插入排序是一個穩(wěn)定的排序方法。2、插入排序表插入排序折半插入排序 (Insert Sorting)基本思想：通過鏈接指針，按關(guān)鍵碼的大小，實現(xiàn)從小到大的鏈接過程，為此需增設(shè)一個指針項操作方法與直接插入排序類

11、似，所不同的是直接插入排序要移動記錄，而表插入排序是修改鏈接指針。以靜態(tài)鏈表說明，結(jié)構(gòu)如下： struct NODE int key ; int next ; float info ; 算法圖示：2、插入排序表插入排序算法圖示： （接上頁）2、插入排序表插入排序2、插入排序表插入排序算法： (tableSort.cpp)void tablesort(JD r,int n) int i,j , k;for(i=2;in ;i+) j = r0.next ; k = 0 ;/k為前置指針 while(rj.key = ri.key & j != 0 ) k= j; j= rj.next; ri.n

12、ext = rk.next ; rk.next = i ; 2、插入排序表插入排序算法評估：表插入排序的基本操作是將一個記錄插入到已排好序的有序鏈表中，設(shè)有序表長度為i，則需要比較至多i+1次，修改指針兩次。因此，總比較次數(shù)與直接插入排序相同，修改指針總次數(shù)為2n次。所以，時間復(fù)雜度仍為O(n2) 。2、插入排序希爾排序希爾排序 (Shells Sorting)基本思想：希爾排序方法又稱為縮小增量排序?；舅枷胧牵涸O(shè)待排序?qū)ο笮蛄杏?n 個對象，首先取一個整數(shù) gap n 作為間隔，將全部對象分為 gap 個子序列，所有距離為 gap 的對象放在同一個子序列中，在每一個子序列中分別施行直接插入

13、排序。然后縮小間隔 gap，例如取 gap = gap/2，重復(fù)上述的子序列劃分和排序工作。直到最后取 gap = 1，將所有對象放在同一個序列中排序為止。2、插入排序希爾排序取d3=1三趟分組：13 27 48 55 4 49 38 65 97 76三趟排序：4 13 27 38 48 49 55 65 76 97初始：49 38 65 97 76 13 27 48 55 4一趟排序：13 27 48 55 4 49 38 65 97 76二趟排序：13 4 48 38 27 49 55 65 97 76取d1=5一趟分組：49 38 65 97 76 13 27 48 55 4取d2=3二

14、趟分組：13 27 48 55 4 49 38 65 97 76 算法圖示1：例49 38 65 97 76 13 27 48 55 4#define T 3 int d =5,3,1;ji49133827一趟排序：13 27 48 55 4 49 38 65 97 76jiji274jiji5538jijiji二趟排序：13 4 48 38 27 49 55 65 97 76jiji6548ji9755ji7642、插入排序希爾排序 算法圖示2：2、插入排序希爾排序算法： (binarySort.cpp)void shellsort(JD r,int n,int dT) int i,j,k;

15、 JD x; k=0; while(kT) for(i=dk+1;i0)&(x.key0)&(flag=1) flag=0; for(j=1;jrj+1.key) flag=1; r0=rj; rj=rj+1; rj+1=r0; n-; 3、交換排序冒泡排序算法評估：在對象的初始排列已經(jīng)按關(guān)鍵碼從小到大排好序時，此算法只執(zhí)行一趟起泡，做 n-1 次關(guān)鍵碼比較，不移動對象。這是最好的情形。3、交換排序冒泡排序算法評估：最壞的情形是算法執(zhí)行了n-1趟起泡，第 i 趟 (1 i n) 做了 n- i 次關(guān)鍵碼比較，執(zhí)行了n-i 次對象交換。這樣在最壞情形下總的關(guān)鍵碼比較次數(shù)KCN和對象移動次數(shù)RMN

16、為：3、交換排序冒泡排序算法評估：起泡排序需要一個附加對象以實現(xiàn)對象值的對換。起泡排序是一個穩(wěn)定的排序方法。3、交換排序冒泡排序快速排序 ( Quick Sorting)基本思想：快速排序是通過比較關(guān)鍵碼、交換記錄，以某個記錄為界(該記錄稱為支點)，將待排序列分成兩部分。其中，一部分所有記錄的關(guān)鍵碼大于等于支點記錄的關(guān)鍵碼，另一部分所有記錄的關(guān)鍵碼小于支點記錄的關(guān)鍵碼。我們將待排序列按關(guān)鍵碼以支點記錄分成兩部分的過程，稱為一次劃分。對各部分不斷劃分，直到整個序列按關(guān)鍵碼有序 。3、交換排序快速排序3、交換排序快速排序初始關(guān)鍵字： 49 38 65 97 76 13 27 50 ijxji 完成

17、一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij算法圖示：算法： (quickSort.cpp)void quicksort(JD r,int low,int high) int l=low, h= high ; if (low = high) return ; r0=rlow; while(low high ) while(low = r0.key) high-; if

18、(low high ) rlow=rhigh , low+; while( (low high) & (rlow.key = r0.key) low+; if(low high ) rhigh=rlow , high-; rlow=r0; quicksort(r, l , high-1 ); quicksort(r, high+1, h ); 3、交換排序快速排序算法分析：算法quicksort是一個遞歸的算法，其遞歸樹如圖所示。3、交換排序快速排序 如：序列 49 14 38 74 96 65 8 49 55 27 第一次搜索交換 27 14 38 8 49 65 96 49 55 74 。

19、 算法評估：從快速排序算法的遞歸樹可知，快速排序的趟數(shù)取決于遞歸樹的深度。3、交換排序快速排序如果每次劃分對一個對象定位后，該對象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對兩個長度減半的子序列進行排序，這是最理想的情況。算法評估：在n個元素的序列中，對一個對象定位所需時間為 O(n)。若設(shè) t(n) 是對 n 個元素的序列進行排序所需的時間，而且每次對一個對象正確定位后，正好把序列劃分為長度相等的兩個子序列，此時，總的計算時間為：o(n log2n )3、交換排序快速排序算法評估：在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個

20、比上一次少一個對象的子序列。這樣，必須經(jīng)過 n-1 趟才能把所有對象定位，而且第 i 趟需要經(jīng)過 n-i 次關(guān)鍵碼比較才能找到第 i 個對象的安放位置，總的關(guān)鍵碼比較次數(shù)將達到：3、交換排序快速排序算法評估：其排序速度退化到簡單排序的水平，比直接插入排序還慢。占用附加存儲(即棧)將達到o(n)。若能更合理地選擇基準(zhǔn)對象，使得每次劃分所得的兩個子序列中的對象個數(shù)盡可能地接近，可以加速排序速度，但是由于對象的初始排列次序是隨機的，這個要求很難辦到。3、交換排序快速排序有一種改進辦法：取每個待排序?qū)ο笮蛄械牡谝粋€對象、最后一個對象和位置接近正中的3個對象，取其關(guān)鍵碼居中者作為基準(zhǔn)對象。算法評估：快速

21、排序是遞歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)。最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為 log2(n+1) 。因此，要求存儲開銷為 o(log2n)。3、交換排序快速排序算法評估：對于 n 較大的平均情況而言，快速排序是“快速”的，但是當(dāng) n 很小時，這種排序方法往往比其它簡單排序方法還要慢。3、交換排序快速排序快速排序方法是一個不穩(wěn)定的排序方法4、選擇排序基本思想：每一趟 (例如第 i 趟，i = 0, 1, , n-2) 在后面 n-i 個待排序?qū)ο笾羞x出關(guān)鍵碼最小的對象, 作為有序?qū)ο笮蛄械牡?i 個對象。待到第 n-2 趟作完，待排序?qū)ο笾皇Ｏ?個，就不用再選了。包

22、括：直接選擇排序 (Select Sort)錦標(biāo)賽排序(Tournament Tree Sort)堆排序 (heap sort)直接選擇排序 (Select Sort)基本思想： 在一組對象vivn-1中選擇具有最小關(guān)鍵碼的對象；若它不是這組對象中的第一個對象，則將它與這組對象中的第一個對象對調(diào)； 在這組對象中剔除這個具有最小關(guān)鍵碼的對象，在剩下的對象vi+1vn-1中重復(fù)執(zhí)行第、步，直到剩余對象只有一個為止。4、選擇排序直接選擇排序4、選擇排序直接選擇排序初始： 49 38 65 97 76 13 27 jjjjjji=11349一趟： 13 38 65 97 76 49 27 i=2kkj

23、jjjj2738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 排序結(jié)束： 13 27 38 49 65 76 97 算法圖示：算法： (selectSort.cpp)void selectsort(JD r,int n) int i,j,k; for(i=1;in;i+) k=i; for(j=i+1;j=n;j+) if(rj.keyrk.key) k=j; if(i!=k) r0=ri;

24、ri=rk; rk=r0; 4、選擇排序直接選擇排序算法評估：直接選擇排序的關(guān)鍵碼比較次數(shù)KCN與對象的初始排列無關(guān)。第 i 趟選擇具有最小關(guān)鍵碼對象所需的比較次數(shù)總是 n-i-1 次，此處假定整個待排序?qū)ο笮蛄杏?n 個對象。因此，總的關(guān)鍵碼比較次數(shù)為:4、選擇排序直接選擇排序算法評估：對象的移動次數(shù)與對象序列的初始排列有關(guān)。當(dāng)這組對象的初始狀態(tài)是按其關(guān)鍵碼從小到大有序的時候，對象的移動次數(shù)RMN = 0，達到最少。4、選擇排序直接選擇排序最壞情況是每一趟都要進行交換，總的對象移動次數(shù)為RMN = 3(n-1)。 直接選擇排序是一種不穩(wěn)定的排序方法。錦標(biāo)賽排序 (Tournament Tre

25、e Sort)基本思想：它的思想與體育比賽時的淘汰賽類似。首先取得 n 個對象的關(guān)鍵碼，進行兩兩比較，得到 n/2 個比較的優(yōu)勝者(關(guān)鍵碼小者)，作為第一步比較的結(jié)果保留下來。然后對這 n/2 個對象再進行關(guān)鍵碼的兩兩比較，如此重復(fù)，直到選出一個關(guān)鍵碼最小的對象為止。4、選擇排序錦標(biāo)賽排序在圖例中，最下面是對象排列的初始狀態(tài)，相當(dāng)于一棵滿二叉樹的葉結(jié)點，它存放的是所有參加排序的對象的關(guān)鍵碼。如果 n 不是2的 k 次冪，則讓葉結(jié)點數(shù)補足到滿足 2k-1 n 2k 的2k個。葉結(jié)點上面一層的非葉結(jié)點是葉結(jié)點關(guān)鍵碼兩兩比較的結(jié)果。最頂層是樹的根。08Winner 2108086325*212125

26、4925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14勝者樹的概念每次兩兩比較的結(jié)果是把關(guān)鍵碼小者作為優(yōu)勝者上升到雙親結(jié)點，稱這種比賽樹為勝者樹。位于最底層的葉結(jié)點叫做勝者樹的外結(jié)點，非葉結(jié)點稱為勝者樹的內(nèi)結(jié)點。每個結(jié)點除了存放對象的關(guān)鍵碼 data 外，還存放了此對象是否要參選的標(biāo)志 Active 和此對象在滿二叉樹中的序號index。勝者樹最頂層是樹的根，表示最后選擇出來的具有最小關(guān)鍵碼的對象。08Winner (勝者)2108086325*2121254925*160863tree7 tree8 tree9 tree

27、10 tree11 tree12 tree13 tree14 形成初始勝者樹（最小關(guān)鍵碼上升到根）a0關(guān)鍵碼比較次數(shù) : 6 16Winner (勝者)2116166325*2121254925*1663tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14輸出冠軍并調(diào)整勝者樹后樹的狀態(tài)a1關(guān)鍵碼比較次數(shù) : 2 21Winner (勝者)21636325*2121254925*63tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14輸出亞軍并調(diào)整勝者樹后樹的狀態(tài)a2關(guān)鍵碼比較次數(shù) : 2 2

28、5Winner (勝者)25636325*25254925*63tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14輸出第三名并調(diào)整勝者樹后樹的狀態(tài)a3關(guān)鍵碼比較次數(shù) : 2 25*Winner (勝者)25*636325*4925*63tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14輸出第四名并調(diào)整勝者樹后樹的狀態(tài)a4關(guān)鍵碼比較次數(shù) : 2 63Winner (勝者)636363tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14全部

29、比賽結(jié)果輸出時樹的狀態(tài)a6關(guān)鍵碼比較次數(shù) : 2 4、選擇排序錦標(biāo)賽排序算法評估：錦標(biāo)賽排序構(gòu)成的樹是滿的完全二叉樹，其深度為 log2(n+1)，其中 n 為待排序元素個數(shù)。除第一次選擇具有最小關(guān)鍵碼的對象需要進行 n-1 次關(guān)鍵碼比較外，重構(gòu)勝者樹選擇具有次小、再次小關(guān)鍵碼對象所需的關(guān)鍵碼比較次數(shù)均為 O(log2n)?？傟P(guān)鍵碼比較次數(shù)為O(nlog2n)。對象的移動次數(shù)不超過關(guān)鍵碼的比較次數(shù)，所以錦標(biāo)賽排序總的時間復(fù)雜度為O(nlog2n)。這種排序方法雖然減少了許多排序時間，但是使用了較多的附加存儲。4、選擇排序錦標(biāo)賽排序算法評估：如果有 n 個對象，必須使用至少 2n-1 個結(jié)點來存

30、放勝者樹。最多需要找到滿足 2k-1 n 2k 的k，使用 2*2k-1 個結(jié)點。每個結(jié)點包括關(guān)鍵碼、對象序號和比較標(biāo)志三種信息。錦標(biāo)賽排序是一個穩(wěn)定的排序方法。堆排序 (heap Sort)基本概念： 4、選擇排序堆排序小頂堆： Ki K2i and K 2i+1大頂堆： Ki K2i and K 2i+1大頂堆小頂堆堆排序 (heap Sort)基本思路： 若以一維數(shù)組存儲一個堆，則堆對應(yīng)一棵完全二叉樹，且所有非葉結(jié)點的值均不大于(或不小于)其子女的值，根結(jié)點的值是最小(或最大)的。設(shè)有n個元素，將其按關(guān)鍵碼排序。首先將這n個元素按關(guān)鍵碼建成堆，將堆頂元素輸出，得到n個元素中關(guān)鍵碼最小(或

31、最大)的元素。然后，再對剩下的n-1個元素建成堆，輸出堆頂元素，得到n個元素中關(guān)鍵碼次小(或次大)的元素。如此反復(fù)，便得到一個按關(guān)鍵碼有序的序列。稱這個過程為堆排序。 4、選擇排序堆排序堆排序 (heap Sort)需要解決兩個問題： 4、選擇排序堆排序1、如何將n個元素的序列按關(guān)鍵碼建成堆 ？2、輸出堆頂元素后，怎樣調(diào)整剩余n-1個元素，使其按關(guān)鍵碼成為一個新堆 ？例 含8個元素的無序序列（49，38，65，97，76，13，27，50）496538271376975049653827137650974913382765765097491338276576509713273849657650

32、971、如何將n個元素的序列按關(guān)鍵碼建成堆 ？4、選擇排序堆排序小頂堆示例13273849657650972、 輸出堆頂元素后，怎樣調(diào)整剩余n-1個元素，使其按關(guān)鍵碼成為一個新堆 ？4、選擇排序堆排序小頂堆示例13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13 273849502765769713輸出：13 276549502738769713輸出：13 27 384965502738769713輸出：13 27 387665502738499713輸出：13 27 38 4950657

33、62738499713輸出：13 27 38 499765762738495013輸出：13 27 38 49 506597762738495013輸出：13 27 38 49 509765762738495013輸出：13 27 38 49 50 657665972738495013輸出：13 27 38 49 50 659765762738495013輸出：13 27 38 49 50 65 769765762738495013輸出：13 27 38 49 50 65 76 974、選擇排序堆排序大頂堆示例212525*49160801234521 25 49 25* 16 08初始關(guān)鍵碼

34、集合1、建立初始的最大堆212525*491608012345i212525*164908025431i21 25 49 25* 16 08初始關(guān)鍵碼集合21 25 49 25* 16 08i = 2 時的局部調(diào)整212525*491608012345i492525*16210802543121 25 49 25* 16 0849 25 21 25* 16 08i = 0 時的局部調(diào)整形成最大堆i = 1 時的局部調(diào)整492525*211608012345082525*16214902543149 25 21 25* 16 0808 25 21 25* 16 49交換 0 號與 5 號對象,5

35、 號對象就位初始最大堆2、基于初始堆進行堆排序2525*082116490123451625*0825214902543125 25* 21 08 16 4916 25* 21 08 25 49交換 0 號與 4 號對象,4 號對象就位從 0 號到 4 號 重新調(diào)整為最大堆25*1608212549012345081625*25214902543125* 16 21 08 25 4908 16 21 25* 25 49交換 0 號與 3 號對象,3 號對象就位從 0 號到 3 號 重新調(diào)整為最大堆211625*082549012345081625*25214902543121 16 08 25

36、* 25 4908 16 21 25* 25 49交換 0 號與 2 號對象,2 號對象就位從 0 號到 2 號 重新調(diào)整為最大堆160825*212549012345081625*25214902543116 08 21 25* 25 4908 16 21 25* 25 49交換 0 號與 1 號對象,1 號對象就位從 0 號到 1 號 重新調(diào)整為最大堆算法分析若設(shè)堆中有 n 個結(jié)點，且 2k-1 n 2k，則對應(yīng)的完全二叉樹有 k 層。在第 i 層上的結(jié)點數(shù) 2i (i = 0, 1, , k-1)。在第一個形成初始堆的for循環(huán)中對每一個非葉結(jié)點調(diào)用了一次堆調(diào)整算法FilterDown(

37、 )，因此該循環(huán)所用的計算時間為：其中，i 是層序號，2i 是第 i 層的最大結(jié)點數(shù)，(k-i-1)是第 i 層結(jié)點能夠移動的最大距離。在第二個for循環(huán)中，調(diào)用了n-1次FilterDown( )算法，該循環(huán)的計算時間為O(nlog2n)。因此，堆排序的時間復(fù)雜性為O(nlog2n)。該算法的附加存儲主要是在第二個for循環(huán)中用來執(zhí)行對象交換時所用的一個臨時對象。因此，該算法的空間復(fù)雜性為O(1)。堆排序是一個不穩(wěn)定的排序方法。5、歸并排序 Merge Sort 基本思想：歸并，是將兩個或兩個以上的有序表合并成一個新的有序表。對象序列 initList 中有兩個有序表Vl Vm和Vm+1 V

38、n。它們可歸并成一個有序表，存于另一對象序列 mergedList 的Vl Vn中。這種歸并方法稱為兩路歸并 (2-way merging)。基本思想是：設(shè)兩個有序表A和B的對象個數(shù)(表長)分別為 al 和 bl，變量 i 和 j 分別是表A和表B的當(dāng)前檢測指針。設(shè)表C是歸并后的新有序表，變量 k 是它的當(dāng)前存放指針。08 21 25 25* 49 62 72 93 16 37 54 l m m+1 ninitListi j08 16 21 25 25* 37 49 54 62 72 93 l nkmergeList當(dāng) i 和 j 都在兩個表的表長內(nèi)變化時，根據(jù)Ai與Bj的關(guān)鍵碼的大小，依次把

39、關(guān)鍵碼小的對象排放到新表Ck中；當(dāng) i 與 j 中有一個已經(jīng)超出表長時，將另一 個表中的剩余部分照抄到新表Ck中。算法圖示：5、歸并排序 Merge Sort 初始關(guān)鍵字： 49 38 65 97 76 13 27一趟歸并后： 38 49 65 97 13 76 27二趟歸并后： 38 49 65 97 13 27 76三趟歸并后： 13 27 38 49 65 76 97算法： (mergeSort.cpp)void mergeTwo(JD* r,int n, int l, JD* t ) int i= 0 ;while ( i + 2*l = n )merge(r,i,i+(l-1),i+

40、(2*l-1),t );i=i+2*l; if( i + l - 1 n) merge(r, i , i+(l-1), n , t ); else while(i=n) ti=ri, i + ;void mergeSort(JD* r,int n) int i , l=1;JD tMAXSIZE;n = n - 1 ;while(ln) mergeTwo(r,n,l,t); l = l * 2; /為教學(xué)清楚，采用如下方法； i=0; while(i = n ) ri=ti , i+;5、歸并排序 Merge Sort 算法評估：在迭代的歸并排序算法中，函數(shù) MergeTwo( ) 做一趟兩路

41、歸并排序，要調(diào)用merge ( )函數(shù) n/(2*len) O(n/len) 次，函數(shù)MergeSort( )調(diào)用MergeTwo( )正好log2n 次，而每次merge( )要執(zhí)行比較O(len)次，所以算法總的時間復(fù)雜度為O(nlog2n)。歸并排序占用附加存儲較多，需要另外一個與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組。這是這個算法的缺點。歸并排序是一個穩(wěn)定的排序方法。5、歸并排序 Merge Sort 6、基數(shù)排序基本思想：基數(shù)排序是一種借助于多關(guān)鍵碼排序的思想，是將單關(guān)鍵碼按基數(shù)分成“多關(guān)鍵碼”進行排序的方法。包括：多關(guān)鍵碼排序鏈?zhǔn)交鶖?shù)排序6、基數(shù)排序多關(guān)鍵碼排序基本思想：例 ：對52張

42、撲克牌按以下次序排序：兩個關(guān)鍵字：花色”地位高于“面值”花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A有：23A23A23A23A6、基數(shù)排序多關(guān)鍵碼排序這就是多關(guān)鍵碼排序。排序后形成的有序序列叫做詞典有序序列。對于上例兩關(guān)鍵碼的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。一般情況下，假定有一個 n 個對象的序列 V0, V1, , Vn-1 ，且每個對象Vi 中含有 d 個關(guān)鍵碼，如果對于序列中任意兩個對象 Vi 和 Vj ( 0 i1) 個歸并段得到 l/2 個歸并段?？倸w并趟數(shù)等于歸并樹的高度 log2m。根據(jù) 2 路歸并樹, 估計 2

43、 路歸并排序時間 tES 的上界為：tES = m*tIS + d*tIO + S*u*tmg 對4500個對象進行排序的例子，各種操作的計算時間如下： 讀18個輸入塊, 內(nèi)部排序6段, 寫18個輸出塊6 tIS36 tIO 成對歸并初始歸并段 R1R6 36 tIO4500 tmg 歸并兩個具有1500個對象的歸并段R12和R34 24 tIO3000 tmg 最后將 R1234 和 R56 歸并成一個歸并段 36 tIO4500 tmg合計 tES6 tIS132 tIO12000 tmg 由于 tIO = tseek + tlatency +trw, 其中，tseek和tlatency是

44、機械動作，而trw、tIS、tmg是電子線路的動作，所以 tIO tIS，tIO tmg。想要提高外排序的速度，應(yīng)著眼于減少 d。若對相同數(shù)目的對象，在同樣頁塊大小的情況下做 3 路歸并或做 6 路歸并(當(dāng)然, 內(nèi)存緩沖區(qū)的數(shù)目也要變化)，則可做大致比較：歸并路數(shù) k 總讀寫磁盤次數(shù) d 歸并趟數(shù) S 2 132 3 3 108 2 6 72 1因此，增大歸并路數(shù)，可減少歸并趟數(shù)，從而減少總讀寫磁盤次數(shù)d。k路平衡歸并 (k-way Balanced merging)做 k 路平衡歸并時，如果有 m 個初始歸并段，則相應(yīng)的歸并樹有 logkm +1 層，需要歸并logkm 趟。下圖給出對有36

45、個初始歸并段的文件做6路平衡歸并時的歸并樹。做內(nèi)部 k 路歸并時，在 k 個對象中選擇最小者，需要順序比較 k-1 次。每趟歸并 u 個對象需要做(u-1)*(k-1)次比較，S 趟歸并總共需要的比較次數(shù)為： S*(u-1)*(k-1) = logkm * (u-1) * (k-1) = log2m * (u-1) * (k-1) / log2k 在初始歸并段個數(shù) m 與對象個數(shù) u 一定時， log2m*(u-1) = const，而 (k-1) / log2k 在 k 增大時趨于無窮大。因此，增大歸并路數(shù) k，會使得內(nèi)部歸并的時間增大。使用“敗者樹”從 k 個歸并段中選最小者，當(dāng) k 較大時 (k 6)，選出關(guān)鍵碼最小的對象只需比較 log2k 次。 S*(u-1)*log2k = logkm * (u-1) * log2k = log2m * (u-1) * log2k / log2k = log2m * (u-1)關(guān)鍵碼比較次數(shù)與 k 無關(guān)，總的內(nèi)部歸并時間不會隨 k 的增大而增大。因此，只要內(nèi)存空間允許, 增大歸并路數(shù) k, 將有效地減少歸并樹深度, 從而減少讀寫磁盤次數(shù) d, 提高外排序的速度。下面討論利用敗者樹在 k 個輸入歸并段中選擇最小者，實現(xiàn)歸并排序的方法。 敗者樹是一棵正則的完全二叉樹。其中每個葉結(jié)點存放各歸并段在歸并過程