數(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ù)對(duì)象的有限集合。關(guān)鍵碼(key): 通常數(shù)據(jù)對(duì)象有多個(gè)屬性域，即多個(gè)數(shù)據(jù)成員組成，其中有一個(gè)屬性域可用來區(qū)分對(duì)象，作為排序依據(jù)。該域即為關(guān)鍵碼。每個(gè)數(shù)據(jù)表用哪個(gè)屬性域作為關(guān)鍵碼，要視具體的應(yīng)用需要而定。即使是同一個(gè)表，在解決不同問題的場合也可能取不同的域做關(guān)鍵碼。1、基本術(shù)語主關(guān)鍵碼: 如果在數(shù)據(jù)表中各個(gè)對(duì)象的關(guān)鍵碼互不相同，這種關(guān)鍵碼即主關(guān)鍵碼。按照主關(guān)

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

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

4、據(jù)表類定義，體現(xiàn)了抽象數(shù)據(jù)類型的思想。1、基本術(shù)語基本思想：2、插入排序每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。包括：直接插入排序 (Insert Sort)折半插入排序(Binary Insert sort)鏈表插入排序希爾排序 (Shell Sort)直接插入排序 (Insert Sorting)2、插入排序直接插入排序基本思想：僅有一個(gè)記錄的表總是有序的，因此，對(duì)n個(gè)記錄的表，可從第二個(gè)記錄開始直到第n個(gè)記錄，逐個(gè)向有序表中進(jìn)行插入操作，從而得到n個(gè)記錄按關(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、插入排序直接插入排序算法評(píng)估：最好情況下：排序前對(duì)象已經(jīng)按關(guān)鍵碼大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械淖詈笠粋€(gè)對(duì)象的關(guān)鍵碼比較 1 次，移動(dòng) 2 次對(duì)象，總的關(guān)鍵碼比較次數(shù)為 n-1，對(duì)象移動(dòng)次數(shù)為 2(n-1)。2、插入排序直接插入排序算法評(píng)估：最壞情況下：第 i 趟時(shí)第 i 個(gè)對(duì)象必須與前面 i 個(gè)對(duì)象都做關(guān)鍵碼比較，并且每做 1 次比較就要做

7、 1 次數(shù)據(jù)移動(dòng)。則總的關(guān)鍵碼比較次數(shù)KCN 和對(duì)象 移動(dòng)次數(shù)RMN分別為2、插入排序直接插入排序算法評(píng)估：若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為 n2/4。因此，直接插入排序的時(shí)間復(fù)雜度為 o(n2)。直接插入排序是一種穩(wěn)定的排序方法。2、插入排序折半插入排序折半插入排序 (Insert Sorting)基本思想：直接插入排序的插入位置的確定通過對(duì)有序表中記錄按關(guān)鍵碼逐個(gè)比較得到的，平均情況下總比較次數(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、插入排序折半插入排序算法評(píng)估：對(duì)分查找比順序查找快，所以對(duì)分插入排序就平均性能來說比直接插入排序要快。它所需要的關(guān)鍵碼比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān)，僅依賴于對(duì)象個(gè)數(shù)。在插入第 i 個(gè)對(duì)象時(shí)，需要經(jīng)過 log2i +1 次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置。因此，

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

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

13、排序。然后縮小間隔 gap，例如取 gap = gap/2，重復(fù)上述的子序列劃分和排序工作。直到最后取 gap = 1，將所有對(duì)象放在同一個(gè)序列中排序?yàn)橹埂?、插入排序希爾排序取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、交換排序冒泡排序算法評(píng)估：在對(duì)象的初始排列已經(jīng)按關(guān)鍵碼從小到大排好序時(shí)，此算法只執(zhí)行一趟起泡，做 n-1 次關(guān)鍵碼比較，不移動(dòng)對(duì)象。這是最好的情形。3、交換排序冒泡排序算法評(píng)估：最壞的情形是算法執(zhí)行了n-1趟起泡，第 i 趟 (1 i n) 做了 n- i 次關(guān)鍵碼比較，執(zhí)行了n-i 次對(duì)象交換。這樣在最壞情形下總的關(guān)鍵碼比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN

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

17、一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進(jìn)行快速排序： ( 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是一個(gè)遞歸的算法，其遞歸樹如圖所示。3、交換排序快速排序 如：序列 49 14 38 74 96 65 8 49 55 27 第一次搜索交換 27 14 38 8 49 65 96 49 55 74 。

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

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

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

22、括：直接選擇排序 (Select Sort)錦標(biāo)賽排序(Tournament Tree Sort)堆排序 (heap sort)直接選擇排序 (Select Sort)基本思想： 在一組對(duì)象vivn-1中選擇具有最小關(guān)鍵碼的對(duì)象；若它不是這組對(duì)象中的第一個(gè)對(duì)象，則將它與這組對(duì)象中的第一個(gè)對(duì)象對(duì)調(diào)； 在這組對(duì)象中剔除這個(gè)具有最小關(guān)鍵碼的對(duì)象，在剩下的對(duì)象vi+1vn-1中重復(fù)執(zhí)行第、步，直到剩余對(duì)象只有一個(gè)為止。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、選擇排序直接選擇排序算法評(píng)估：直接選擇排序的關(guān)鍵碼比較次數(shù)KCN與對(duì)象的初始排列無關(guān)。第 i 趟選擇具有最小關(guān)鍵碼對(duì)象所需的比較次數(shù)總是 n-i-1 次，此處假定整個(gè)待排序?qū)ο笮蛄杏?n 個(gè)對(duì)象。因此，總的關(guān)鍵碼比較次數(shù)為:4、選擇排序直接選擇排序算法評(píng)估：對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)這組對(duì)象的初始狀態(tài)是按其關(guān)鍵碼從小到大有序的時(shí)候，對(duì)象的移動(dòng)次數(shù)RMN = 0，達(dá)到最少。4、選擇排序直接選擇排序最壞情況是每一趟都要進(jìn)行交換，總的對(duì)象移動(dòng)次數(shù)為RMN = 3(n-1)。 直接選擇排序是一種不穩(wěn)定的排序方法。錦標(biāo)賽排序 (Tournament Tre

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

26、4925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14勝者樹的概念每次兩兩比較的結(jié)果是把關(guān)鍵碼小者作為優(yōu)勝者上升到雙親結(jié)點(diǎn)，稱這種比賽樹為勝者樹。位于最底層的葉結(jié)點(diǎn)叫做勝者樹的外結(jié)點(diǎn)，非葉結(jié)點(diǎn)稱為勝者樹的內(nèi)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)除了存放對(duì)象的關(guān)鍵碼 data 外，還存放了此對(duì)象是否要參選的標(biāo)志 Active 和此對(duì)象在滿二叉樹中的序號(hào)index。勝者樹最頂層是樹的根，表示最后選擇出來的具有最小關(guān)鍵碼的對(duì)象。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é)果輸出時(shí)樹的狀態(tài)a6關(guān)鍵碼比較次數(shù) : 2 4、選擇排序錦標(biāo)賽排序算法評(píng)估：錦標(biāo)賽排序構(gòu)成的樹是滿的完全二叉樹，其深度為 log2(n+1)，其中 n 為待排序元素個(gè)數(shù)。除第一次選擇具有最小關(guān)鍵碼的對(duì)象需要進(jìn)行 n-1 次關(guān)鍵碼比較外，重構(gòu)勝者樹選擇具有次小、再次小關(guān)鍵碼對(duì)象所需的關(guān)鍵碼比較次數(shù)均為 O(log2n)?？傟P(guān)鍵碼比較次數(shù)為O(nlog2n)。對(duì)象的移動(dòng)次數(shù)不超過關(guān)鍵碼的比較次數(shù)，所以錦標(biāo)賽排序總的時(shí)間復(fù)雜度為O(nlog2n)。這種排序方法雖然減少了許多排序時(shí)間，但是使用了較多的附加存儲(chǔ)。4、選擇排序錦標(biāo)賽排序算法評(píng)估：如果有 n 個(gè)對(duì)象，必須使用至少 2n-1 個(gè)結(jié)點(diǎn)來存

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

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

32、971、如何將n個(gè)元素的序列按關(guān)鍵碼建成堆 ？4、選擇排序堆排序小頂堆示例13273849657650972、 輸出堆頂元素后，怎樣調(diào)整剩余n-1個(gè)元素，使其按關(guān)鍵碼成為一個(gè)新堆 ？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 時(shí)的局部調(diào)整212525*491608012345i492525*16210802543121 25 49 25* 16 0849 25 21 25* 16 08i = 0 時(shí)的局部調(diào)整形成最大堆i = 1 時(shí)的局部調(diào)整492525*211608012345082525*16214902543149 25 21 25* 16 0808 25 21 25* 16 49交換 0 號(hào)與 5 號(hào)對(duì)象,5

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

36、* 25 4908 16 21 25* 25 49交換 0 號(hào)與 2 號(hào)對(duì)象,2 號(hào)對(duì)象就位從 0 號(hào)到 2 號(hào) 重新調(diào)整為最大堆160825*212549012345081625*25214902543116 08 21 25* 25 4908 16 21 25* 25 49交換 0 號(hào)與 1 號(hào)對(duì)象,1 號(hào)對(duì)象就位從 0 號(hào)到 1 號(hào) 重新調(diào)整為最大堆算法分析若設(shè)堆中有 n 個(gè)結(jié)點(diǎn)，且 2k-1 n 2k，則對(duì)應(yīng)的完全二叉樹有 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(

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

38、n。它們可歸并成一個(gè)有序表，存于另一對(duì)象序列 mergedList 的Vl Vn中。這種歸并方法稱為兩路歸并 (2-way merging)?；舅枷胧牵涸O(shè)兩個(gè)有序表A和B的對(duì)象個(gè)數(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 都在兩個(gè)表的表長內(nèi)變化時(shí)，根據(jù)Ai與Bj的關(guān)鍵碼的大小，依次把

39、關(guān)鍵碼小的對(duì)象排放到新表Ck中；當(dāng) i 與 j 中有一個(gè)已經(jīng)超出表長時(shí)，將另一 個(gè)表中的剩余部分照抄到新表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 算法評(píng)估：在迭代的歸并排序算法中，函數(shù) MergeTwo( ) 做一趟兩路

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

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

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

44、機(jī)械動(dòng)作，而trw、tIS、tmg是電子線路的動(dòng)作，所以 tIO tIS，tIO tmg。想要提高外排序的速度，應(yīng)著眼于減少 d。若對(duì)相同數(shù)目的對(duì)象，在同樣頁塊大小的情況下做 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 路平衡歸并時(shí)，如果有 m 個(gè)初始?xì)w并段，則相應(yīng)的歸并樹有 logkm +1 層，需要?dú)w并logkm 趟。下圖給出對(duì)有36

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