新編《數(shù)據(jù)結(jié)構(gòu)用C語(yǔ)言描述》第八章jsp課件

1、概述插入排序交換排序選擇排序歸并排序基數(shù)排序各種內(nèi)排方法比較第八章 排序概 述排序：將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。 數(shù)據(jù)表(datalist): 它是待排序數(shù)據(jù)對(duì)象的有限集合。主關(guān)鍵字(key): 數(shù)據(jù)對(duì)象有多個(gè)屬性域, 即多個(gè)數(shù)據(jù)成員組成, 其中有一個(gè)屬性域可用來(lái)區(qū)分對(duì)象, 作為排序依據(jù)，稱為關(guān)鍵字。也稱為關(guān)鍵字。排序方法的穩(wěn)定性: 如果在對(duì)象序列中有兩 個(gè)對(duì)象ri和rj, 它們的關(guān)鍵字 ki = kj , 且在排序之前, 對(duì)象ri排在rj前面。如果在排序之后, 對(duì)象ri仍在對(duì)象rj的前面, 則稱這個(gè)排序方法是穩(wěn)定的, 否則稱這個(gè)排序方法是不穩(wěn)定的。內(nèi)排序與外排

2、序: 內(nèi)排序是指在排序期間數(shù)據(jù)對(duì)象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對(duì)象個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序過(guò)程的要求，不斷在內(nèi)、外存之間移動(dòng)的排序。排序的時(shí)間開(kāi)銷: 排序的時(shí)間開(kāi)銷是衡量算法好壞的最重要的標(biāo)志。排序的時(shí)間開(kāi)銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來(lái)衡量。typedef struct int key ; datatype other ; rectype; rectype Rn;內(nèi)排序分類依不同原則插入排序、交換排序、選擇排序、歸并排序、和基數(shù)排序等。依所須工作量簡(jiǎn)單排序-時(shí)間復(fù)雜度o(n2)先進(jìn)排序方法-時(shí)間復(fù)雜度o(n logn)基數(shù)排序-時(shí)間復(fù)雜度o(

3、d.n)插入排序 (Insert Sorting)基本思想 當(dāng)插入第i (i 1) 個(gè)對(duì)象時(shí), 前面的R0, R1, , Ri-1已經(jīng)排好序。這時(shí), 用Ri的關(guān)鍵字與Ri-1, Ri-2, 的關(guān)鍵字順序進(jìn)行比較, 找到插入位置即將Ri插入, 原來(lái)位置上的對(duì)象向后順移。 基本思想 每步將一個(gè)待排序的對(duì)象, 按其關(guān)鍵字大小, 插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上, 直到對(duì)象全部插入為止。直接插入排序 (Insert Sort)直接插入排序過(guò)程0 1 2 3 4 5 temp i = 1i = 20 1 2 3 4 5 temp2108254925*162125084925*162521250

4、84925*162125084925*16492125084925*16i = 32125084925*1625*2125084925*16i = 4i = 52125084925*1616162125084925*162125084925*162125084925*1608直接插入排序的算法 InsertSort ( rectype R , int n ) int i, j; for ( i = 2; i n; i+ ) R0= Ri; j = i 1 ; /從后向前順序比較 while ( R0.key Rj.key ) Rj+1 = Rj-; Rj+1 = R0; 算法分析設(shè)待排序?qū)ο髠€(gè)

5、數(shù)為 n, 則該算法的主程序執(zhí)行n-1趟。關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)與對(duì)象關(guān)鍵字的初始排列有關(guān)。最好情況下, 排序前對(duì)象已按關(guān)鍵字從小到大有序, 每趟只需與前面有序?qū)ο笮蛄械淖詈笠粋€(gè)對(duì)象比較1次, 移動(dòng)2次對(duì)象, 總的關(guān)鍵字比較次數(shù)為 n-1, 對(duì)象移動(dòng)次數(shù)為 2(n-1)。最壞情況下, 第 i 趟時(shí)第 i 個(gè)對(duì)象必須與前面 i 個(gè)對(duì)象都做關(guān)鍵字比較, 并且每做1次比較就要做1次數(shù)據(jù)移動(dòng)。則總關(guān)鍵字比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN分別為在平均情況下的關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為 n2/4。因此，直接插入排序的時(shí)間復(fù)雜度為 o(n2)。直接插入排序是一種穩(wěn)定的排序方法。折半插入排序 (B

6、inary Insertsort)基本思想 設(shè)在順序表中有一 個(gè)對(duì)象序列 R0, R1, , Rn-1。其中, R0, R1, , Ri-1 是已經(jīng)排好序的對(duì)象。在插入Ri 時(shí), 利用折半搜索法尋找Ri 的插入位置。折半插入排序的算法typedef int SortData; Roid BinInsSort ( SortData R , int n ) SortData temp; int Left, Right; for ( int i = 1; i n; i+) Left = 0; Right = i-1; temp = Ri; while ( Left = Right ) int mid

7、 = ( Left + Right )/2; if ( temp = Left; k- ) Rk+1 = Rk;/記錄后移 RLeft = temp; /插入 折半插入排序0 1 2 3 4 5 temp i = 1i = 20 1 2 3 4 5 temp52133i = 35521532144i = 4215388i = 52153161684421384516折半搜索比順序搜索查找快, 所以折半插入排序就平均性能來(lái)說(shuō)比直接插入排序要快。它所需的關(guān)鍵字比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o(wú)關(guān), 僅依賴于對(duì)象個(gè)數(shù)。在插入第 i 個(gè)對(duì)象時(shí), 需要經(jīng)過(guò) log2i +1 次關(guān)鍵字比較, 才能確定它

8、應(yīng)插入的位置。因此, 將 n 個(gè)對(duì)象(為推導(dǎo)方便, 設(shè)為 n=2k )用折半插入排序所進(jìn)行的關(guān)鍵字比較次數(shù)為： 算法分析 當(dāng) n 較大時(shí), 總關(guān)鍵字比較次數(shù)比直接插入排序的最壞情況要好得多, 但比其最好情況要差。在對(duì)象的初始排列已經(jīng)按關(guān)鍵字排好序或接近有序時(shí), 直接插入排序比折半插入排序執(zhí)行的關(guān)鍵字比較次數(shù)要少。折半插入排序的對(duì)象移動(dòng)次數(shù)與直接插入排序相同, 依賴于對(duì)象的初始排列。折半插入排序是一個(gè)穩(wěn)定的排序方法。折半插入排序的時(shí)間復(fù)雜度為o(n2)。希爾排序 (Shell Sort)基本思想設(shè)待排序?qū)ο笮蛄杏?n 個(gè)對(duì)象, 首先取一個(gè)整數(shù) gap n 作為間隔, 將全部對(duì)象分為 gap 個(gè)子

9、序列, 所有距離為 gap 的對(duì)象放在同一個(gè)子序列中, 在每一個(gè)子序列中分別施行直接插入排序。然后縮小間隔 gap, 例如取 gap = gap/2，重復(fù)上述的子序列劃分和排序工作。直到最后取 gap = 1, 將所有對(duì)象放在同一個(gè)序列中排序?yàn)橹埂Ｏ柵判蚍椒ㄓ址Q為縮小增量排序。i = 3Gap = 30 1 2 3 4 52108254925*160 1 2 3 4 52108254925*16i = 2Gap = 22108254925*162108254925*16i = 1Gap = 12108254925*162108254925*16希爾排序過(guò)程 ShellSort ( recty

10、pe R , int n ) rectype temp; int gap = n / 2; /gap是間隔 while ( gap != 0 ) /循環(huán),直到gap為零 for ( int i = gap; i = gap; j = j-gap ) if ( temp Rj-gap ) Rj = Rj-gap; else break; Rj = temp; gap = ( int ) ( gap / 2 ); 希爾排序的算法開(kāi)始時(shí) gap 的值較大, 子序列中的對(duì)象較少, 排序速度較快; 隨著排序進(jìn)展, gap 值逐漸變小, 子序列中對(duì)象個(gè)數(shù)逐漸變多, 由于前面大多數(shù)對(duì)象已基本有序, 所以排序

11、速度仍然很快。Gap的取法有多種。 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。對(duì)特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算關(guān)鍵字的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。希爾排序所需的比較次數(shù)和移動(dòng)次數(shù)約為n 1.3當(dāng)n趨于無(wú)窮時(shí)可減少到n(log2 n)2交換排序 ( Exchange Sort )基本方法設(shè)待排序?qū)ο笮蛄兄械膶?duì)象個(gè)數(shù)為n。一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個(gè)記錄地關(guān)鍵字，如果發(fā)生逆序，則交換之，其結(jié)果是這n-i+1個(gè)記錄中，關(guān)鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。 基本思想是兩兩比較待排序?qū)ο蟮年P(guān)鍵字,如發(fā)生逆序(

12、即排列順序與排序后的次序正好相反)，則交換之,直到所有對(duì)象都排好序?yàn)橹?。起泡排?(Bubble Sort)210825492516214925251608214925251608214925251608214925251608初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡排序的過(guò)程210825492516081621254925212516492125084925251621214925251608初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡排序的過(guò)程起泡排序的算法BubbleSort ( rectype

13、R , int n ) int i , j , noswap; rectype temp; for ( i=0; i = i; j- ) if ( Rj+1.key Rj.key ) /逆序 temp = R j+1 ;/交換 R j+1 = R j ; R j =temp; noswap = 0 ; /標(biāo)志置為0,有交換 if ( noswap ) break ; 思考題：如何實(shí)現(xiàn)雙起泡 第i趟對(duì)待排序?qū)ο笮蛄蠷i-1,Ri,Rn-1進(jìn)行排序, 結(jié)果將該序列中關(guān)鍵字最小的對(duì)象交換到序列的第一個(gè)位置(i-1), 其它對(duì)象也都向排序的最終位置移動(dòng)。最多做n-1趟起泡就能把所有對(duì)象排好序。在對(duì)象的

14、初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí),此算法只執(zhí)行一趟起泡,做n-1次關(guān)鍵字比較,不移動(dòng)對(duì)象。這是最好的情形。最壞的情形是算法執(zhí)行n-1趟起泡,第i趟 (1 i n) 做 n- i 次關(guān)鍵字比較, 執(zhí)行 n-i 次對(duì)象交換。這樣在最壞情形下總的關(guān)鍵字比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN為：起泡排序是一個(gè)穩(wěn)定的排序方法?？焖倥判?(Quick Sort)基本思想是任取待排序?qū)ο笮蛄兄械哪硞€(gè)對(duì)象 (例如取第一個(gè)對(duì)象) 作為基準(zhǔn), 按照該對(duì)象的關(guān)鍵字大小,將整個(gè)對(duì)象序列劃分為左右兩個(gè)子序列： 左側(cè)子序列中所有對(duì)象的關(guān)鍵字都小于或等于基準(zhǔn)對(duì)象的關(guān)鍵字 右側(cè)子序列中所有對(duì)象的關(guān)鍵字都大于基準(zhǔn)對(duì)象的關(guān)鍵字基

15、準(zhǔn)對(duì)象則排在這兩個(gè)子序列中間(這也是該對(duì)象最終應(yīng)安放的位置)。然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所有的對(duì)象都排在相應(yīng)位置上為止。基準(zhǔn)對(duì)象也稱為樞軸（或支點(diǎn)）記錄。QuickSort ( List ) if ( List的長(zhǎng)度大于1) 將序列List劃分為兩個(gè)子序列 LeftList 和 Right List; QuickSort ( LeftList );QuickSort ( RightList ); 將兩個(gè)子序列 LeftList 和 RightList 合并為一個(gè)序列List; 快速排序算法描述快速排序的過(guò)程2108254925*16初始關(guān)鍵字08254925*16210825

16、4925*1608254925*1608254925*1608254925*1621prikey一次交換二次交換三次交換四次交換完成一趟排序ijijjiijjiji08254925*1621完成一趟排序分別進(jìn)行快速排序08254925*1621有序序列08254925*1621 快速排序的算法 QuickSort ( rectype R , int low, int high ) /在序列l(wèi)owhigh 中遞歸地進(jìn)行快速排序 if ( low high) int i = Partition ( R, low, high); /劃分 QuickSort ( R, low, i -1); /對(duì)左序

17、列同樣處理 QuickSort ( R, i +1, high); /對(duì)右序列同樣處理 int Partition ( rectype R , int low, int high ) R0=Rlow;/子表的第一個(gè)記錄作基準(zhǔn)對(duì)象 tempkey = Rlow.key; /基準(zhǔn)對(duì)象關(guān)鍵字 While(lowhigh) While(low= tempkey) high-; Rlow = Rhigh; /小于基準(zhǔn)的移到區(qū)間的左側(cè) While(lowhigh& Rlow.key = tempkey) low+; Rhigh = Rlow ; /大于基準(zhǔn)的移到區(qū)間的右側(cè) Rlow = R0; retur

18、n low; 算法quicksort是一個(gè)遞歸的算法, 其遞歸樹(shù)如圖所示。算法partition利用序列第一個(gè)對(duì)象作為基準(zhǔn)，將整個(gè)序列劃分為左右兩個(gè)子序列。算法中執(zhí)行了一個(gè)循環(huán), 只要是關(guān)鍵字小于基準(zhǔn)對(duì)象關(guān)鍵字的對(duì)象都移到序列左側(cè), 最后基準(zhǔn)對(duì)象安放到位, 函數(shù)返回其位置。2125*25490816算法分析快速排序的趟數(shù)取決于遞歸樹(shù)的高度。如果每次劃分對(duì)一個(gè)對(duì)象定位后, 該對(duì)象的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同, 則下 一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序, 這是最理想的情況。在 n個(gè)元素的序列中, 對(duì)一個(gè)對(duì)象定位所需時(shí)間為 O(n)。若設(shè) t (n) 是對(duì) n 個(gè)元素的序列進(jìn)行排序所需的時(shí)

19、間, 而且每次對(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 +2T(n/8) ) = 3cn + 8T(n/8) cn log2n + nT(1) = O(n log2n )可以證明, 函數(shù)quicksort的平均計(jì)算時(shí)間也是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明: 就平均計(jì)算時(shí)間而言, 快速排序是所有內(nèi)排序方法中最好的一個(gè)。快速排序是遞歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù)

20、。最大遞歸調(diào)用層次數(shù)與遞歸樹(shù)的高度一致,理想情況為 log2(n+1) 。因此，要求存儲(chǔ)開(kāi)銷為 O(log2n)。在最壞的情況, 即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵字從小到大排好序的情況下, 其遞歸樹(shù)成為單支樹(shù), 每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列?？偟年P(guān)鍵字比較次數(shù)將達(dá)快速排序是一種不穩(wěn)定的排序方法。 基本思想 每一趟 (例如第 i 趟, i = 0, 1, , n-2) 在后面 n-i 個(gè)待排序記錄中選出關(guān)鍵字最小的記錄, 作為有序序列中的第 i 個(gè)記錄。待到第n-2 趟作完, 待排序記錄只剩下1個(gè),就不用再選了。選擇排序直接選擇排序是一種簡(jiǎn)單的排序方法, 它的基本步驟是： 在一組對(duì)象

21、 RiRn-1 中選擇具有最小關(guān)鍵字的對(duì)象；若它不是這組對(duì)象中的第一個(gè)對(duì)象, 則將它與這組對(duì)象中的第一個(gè)對(duì)象對(duì)調(diào); 在這組對(duì)象中剔除這個(gè)具有最小關(guān)鍵字的對(duì)象。在剩下的對(duì)象Ri+1Rn-1中重復(fù)執(zhí)行第、步, 直到剩余對(duì)象只有一個(gè)為止。直接選擇排序 (Select Sort)21254925*16080 1 2 3 4 52125*i = 0492516251608490825*4921i = 1i = 2081625*2521初始最小者 08交換21,08最小者 16交換25,16最小者 21交換49,21 直接選擇排序的過(guò)程最小者 25*無(wú)交換4925*0 1 2 3 4 525*i = 42

22、516084925*4921結(jié)果i = 308162521最小者 25無(wú)交換25211608各趟排序后的結(jié)果直接選擇排序的算法SelectSort ( rectype R , int n ) int i,j ,k; rectype temp; for ( i = 0; i n-1; i+ ) k = i; /選擇具有最小關(guān)鍵字的對(duì)象 for ( j = i+1; j n; j+) if ( Rj.key Rk.key ) k = j; /當(dāng)前具最小關(guān)鍵字的對(duì)象 if ( k != i ) /對(duì)換到第 i 個(gè)位置 temp =Ri; Ri =Rk ; Rk = temp ; 直接選擇排序的關(guān)鍵字

23、比較次數(shù) KCN 與對(duì)象的初始排列無(wú)關(guān)。設(shè)整個(gè)待排序?qū)ο笮蛄杏?n 個(gè)對(duì)象, 則第 i 趟選擇具有最小關(guān)鍵字對(duì)象所需的比較次數(shù)總是 n-i-1 次?？偟年P(guān)鍵字比較次數(shù)為對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)這組對(duì)象的初始狀態(tài)是按其關(guān)鍵字從小到大有序的時(shí)候, 對(duì)象的移動(dòng)次數(shù)RMN = 0，達(dá)到最少。最壞情況是每一趟都要進(jìn)行交換，總的對(duì)象移動(dòng)次數(shù)為 RMN = 3(n-1)。直接選擇排序是一種不穩(wěn)定的排序方法。堆排序( Heap sort )堆 ( Heap )設(shè)有一個(gè)關(guān)鍵字集合，按完全二叉樹(shù)的順序存儲(chǔ)方式存放在一個(gè)一維數(shù)組中。對(duì)它們從根開(kāi)始，自頂向下，同一層自左向右從 0開(kāi)始連續(xù)編號(hào)。若滿足

24、 Ki K2i & Ki K2i+1或 Ki K2i & Ki K2i+1, 則稱該關(guān)鍵字集合構(gòu)成一個(gè)堆。 前者成為小根堆，后者稱為大根堆。完全二叉樹(shù) 順序表示Ki K2i &Ki K2i+1完全二叉樹(shù) 順序表示Ki K2i &Ki K2i+1090987877878454565653131532323531717堆排序 (Heap Sort)利用堆及其運(yùn)算, 可以很容易地實(shí)現(xiàn)選擇排序的思路。堆排序分為兩個(gè)步驟 根據(jù)初始輸入數(shù)據(jù)，利用堆的調(diào)整算法 SIFT( ) 形成初始堆; 通過(guò)一系列的對(duì)象交換和重新調(diào)整堆進(jìn)行排序。自下向上逐步調(diào)整為小根堆5353171778780923456587i092

25、3456587 i = 4i = 3i初始小根堆的建立過(guò)程5353171778780923456587i0923456587i = 2i53171778780923456587i0923456587i = 1i5353171778780923456587i0923456587i53建成堆初始大根堆的建立過(guò)程212525*491608123456i212525*164908136542i初始關(guān)鍵字集合i = 3 時(shí)的局部調(diào)整212525*491608123456i492525*162108136542i = 1 時(shí)的局部調(diào)整形成大根堆i = 2 時(shí)的局部調(diào)整大根堆的篩選算法SIFT ( rect

26、ype R , int i, int m ) int j =2*i; rectype temp = Ri; while ( j = m) if ( j m & Rj.key = Rj ) break; else Ri = Rj; /大子女上移 i = j; j = 2*i; /向下繼續(xù)調(diào)整 Ri = temp; /回放到合適位置將表轉(zhuǎn)換成堆for ( i = n / 2 ; i = 1; i- ) SIFT ( R, i, n );基于初始堆(大頂堆)進(jìn)行堆排序最大堆堆頂R0具有最大的關(guān)鍵字, 將R0與 Rn-1對(duì)調(diào), 把具有最大關(guān)鍵字的對(duì)象交換到最后, 再對(duì)前面的n-1個(gè)對(duì)象, 使用堆的調(diào)整

27、算法SIFT(0, n-2), 重新建立最大堆, 具有次最大關(guān)鍵字的對(duì)象又上浮到R0位置。再對(duì)調(diào)R0和Rn-2,調(diào)用SIFT(0, n-3), 對(duì)前n-2個(gè)對(duì)象重新調(diào)整，。如此反復(fù)執(zhí)行，最后得到全部排序好的對(duì)象序列。這個(gè)算法即堆排序算法，492525*211608012345082525*16214902543149 25 21 25* 16 0808 25 21 25* 16 49交換 0 號(hào)與 5 號(hào)對(duì)象,5 號(hào)對(duì)象就位初始最大堆基于初始堆進(jìn)行堆排序2525*082116490123451625*0825214902543125 25* 21 08 16 4916 25* 21 08 25

28、 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* 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*252

2908 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)整為最大堆堆排序的算法HeapSort ( rectype R ) /對(duì)表R1到Rn進(jìn)行排序, 使得表中對(duì)象關(guān)鍵字非遞減有序。 int i; rectype temp; for ( i = n / 2; i = 1; i- ) SIFT ( R, i, n ); /初始堆 for ( i = n; i = 1; i-) temp = R1; R1= Ri; /交換 Ri =temp; SIFT ( R, 1, i-1 ); /重建最大堆

30、 若設(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)整算法SIFT( ), 因此該循環(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次SIFT( )算法, 該循環(huán)的計(jì)算時(shí)間為O(nlog2n)。因此, 堆排序的時(shí)間復(fù)雜性為O(nlog2n)。該算法的附加存儲(chǔ)主要是在第二個(gè)for循環(huán)中用來(lái)執(zhí)行對(duì)象交換時(shí)所用

31、的一個(gè)臨時(shí)對(duì)象。因此，該算法的空間復(fù)雜性為O(1)。堆排序是一個(gè)不穩(wěn)定的排序方法。歸并排序 (Merge Sort)歸并將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。兩路歸并 (2-way merging)原始序列R 中兩個(gè)有序表 Rl Rm和Rm+1 Rn，它們可歸并成一個(gè)有序表, 存于另一對(duì)象序列R1的 l n 中。08 21 25 25* 49 62 72 93 16 37 54 low mid mid+1 highR08 16 21 25 25* 37 49 54 62 72 93 low highkR1設(shè)變量 i 和 j 是表Rl m和R m+1 n的當(dāng)前檢測(cè)指針。k 是存放指針。當(dāng)

32、 i 和 j 都在兩個(gè)表的表長(zhǎng)內(nèi)變化時(shí), 根據(jù)對(duì)應(yīng)項(xiàng)的關(guān)鍵字的大小, 依次把關(guān)鍵字小的對(duì)象排放到新表 k 所指位置中；當(dāng) i 與 j 中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí)，將另一 個(gè)表中的剩余部分照抄到新表中。ijmerge ( rectype R , rectype R1 , int low, int mid, int high ) int i = low, j = mid+1, k = low; while ( i = mid & j = high ) /兩兩比較將較小的并入 if ( Ri = Rj ) R1 k = Ri; i+; k+; else R1 k = Rj; j+; k+; while

33、( i = mid ) R1k = Ri; i+; k+; /將mid前剩余的并入 while ( j = high ) R1k = Rj; j+; k+; /將mid后剩余的并入兩路歸并算法一趟歸并排序的情形設(shè)R0到Rn-1中 n 個(gè)對(duì)象已經(jīng)分為一些長(zhǎng)度為 len 的歸并項(xiàng), 將這些歸并項(xiàng)兩兩歸并, 歸并成長(zhǎng)度為 2len 的歸并項(xiàng), 結(jié)果放到R1 中。如果n不是2len的整數(shù)倍, 則一趟歸并到最后,可能遇到兩種情形： 剩下一個(gè)長(zhǎng)度為len的歸并項(xiàng)和另一個(gè)長(zhǎng)度不足len的歸并項(xiàng), 可用merge算法將它們歸并成一個(gè)長(zhǎng)度小于 2len 的歸并項(xiàng)。 只剩下一個(gè)歸并項(xiàng)，其長(zhǎng)度小于或等于 len,

34、將它直接抄到R1 中。迭代的歸并排序算法迭代的歸并排序算法就是利用兩路歸并過(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)；再做兩兩歸并，如此重復(fù)，最后得到一個(gè)長(zhǎng)度為 n 的有序序列。迭代的歸并排序算法212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*62377249935416375

35、4627293len=1len=2len=4len=8len=16 MergePass ( rectype R , rectype R1 , int len ) int i = 0; while (i+2*len-1 = n-1) merge( R, R1, i, i+len-1, i+2*len-1); i += 2 * len; /循環(huán)兩兩歸并 if ( i+len = n-1 ) merge( R, R1, i, i+len-1, n-1); else for ( int j = i; j = n-1; j+) R1 j = Rj; 歸并排序的主算法 MergeSort ( rectype R , int n ) /按對(duì)象關(guān)鍵字非遞減的順序?qū)Ρ碇袑?duì)象排序 rectype R1n; int len = 1; while ( len n ) MergePass ( R, R1, len ); len *= 2;MergePass ( R1, R, len ); len *= 2; 在迭代的歸并排序算法中, 函數(shù)Me