[理學(xué)]9排序技術(shù)-資料下載頁(yè)
2025-01-19 14:37本頁(yè)面
【正文】 堆的示意圖（堆頂元素最大） ? 序列（ 91， 85， 53， 36， 47， 30， 24， 12）是一個(gè)堆，如圖： 91 85 53 36 47 30 24 12 ? 在一棵具有 n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（用一維數(shù)組 H(1:n)表示）中，假設(shè)結(jié)點(diǎn) H（ m）的左右子樹(shù)均為堆，現(xiàn)要將 H（ m）為根結(jié)點(diǎn)的子樹(shù)也調(diào)整為堆，這就是調(diào)整建堆的過(guò)程。 調(diào)整建堆示意圖 （ａ） （ｂ） （ｃ） 47 91 53 85 30 12 24 36 91 47 53 85 30 12 24 36 91 85 53 47 30 12 24 36 ? 調(diào)整建堆的過(guò)程總是將根結(jié)點(diǎn)值與左右子數(shù)的根結(jié)點(diǎn)值進(jìn)行比較，若不滿(mǎn)足堆的條件，則將左右子樹(shù)根結(jié)點(diǎn)值中的大者與根結(jié)點(diǎn)值交換，該過(guò)程一直到所有子樹(shù)均為堆為止。 [算法 ] 調(diào)整建堆 輸入：完全二叉樹(shù)數(shù)組 H(1:n)。其中結(jié)點(diǎn) H(m)的左、右子樹(shù)均為堆。 輸出：以 H(m)為根結(jié)點(diǎn)的子樹(shù)為堆。 PROCEDURE SIFT（ H， n， m） t=H(m)。j=2m WHILE (j≤n) DO { IF(jn)and(H(j)H(j+1)) THEN j=j+1 IF (tH(j)) THEN { H(m)=H(j)。m=j。j=2m } else j=n+1 } H(m)=t RETURN 完全二叉樹(shù)中的所有結(jié)點(diǎn)值是從根結(jié)點(diǎn)開(kāi)始一層一層地從 左到右存儲(chǔ)在一維數(shù)組 H中。而對(duì)于完全二叉樹(shù)的順序存 儲(chǔ)結(jié)構(gòu)來(lái)說(shuō)，結(jié)點(diǎn) k的左子樹(shù)根結(jié)點(diǎn)為 2k，右子樹(shù)的根結(jié)點(diǎn) 為 2k+1。因此算法中沒(méi)有用到指針運(yùn)算，而只用到數(shù)組的 下標(biāo)運(yùn)算。 ? 有了調(diào)整建堆的算法后，就可以將一個(gè)無(wú)序序列建成為堆。 ? 假設(shè)無(wú)序序列 H(1:n)以完全二叉樹(shù)表示。從完全二叉樹(shù)的最后一個(gè)非葉子結(jié)點(diǎn)（即第 n/2個(gè)元素）開(kāi)始，直到根結(jié)點(diǎn)（即第一個(gè)元素）為止，對(duì)每一個(gè)結(jié)點(diǎn)進(jìn)行調(diào)整建堆，最后就可以得到與該序列對(duì)應(yīng)的堆。 堆排序 (1)首先將一個(gè)無(wú)序序列建成堆。 (2)然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最大項(xiàng)應(yīng)該在序列的最后）。 不考慮已經(jīng)換到最后的那個(gè)元素，只考慮前 n－ 1個(gè)元素構(gòu)成的子序列，顯然，該子序列已不是堆，但左、右子樹(shù)仍為堆，可以將該子序列調(diào)整為堆。 反復(fù)做第 (2)步，直到剩下的子序列為空為止。 [算法 ] 堆排序 輸入：無(wú)序序列 H(1:n) 輸出：有序序列 H(1:n) PROCEDURE HEAPSORT（ H， n） k=n/2 FOR i=k TO 1 BY 1 DO SIFT(H,n,i) /*無(wú)序序列建堆 */ FOR i=n TO 2 BY 1 DO { t=H(1)。H(1)=H(i)。H(i)=t /*堆頂元素?fù)Q到最后 */ SIFT(H,i1,1) /*調(diào)整建堆 */ } RETURN 堆排序的方法對(duì)于規(guī)模較小的線性表并不適合，但對(duì)于 較大規(guī)模的線性表來(lái)說(shuō)是很有效的。 排序操作是線性表上一種十分常用的操作，所以人們對(duì)排序方法作了大量的深入研究，已發(fā)明的排序算法遠(yuǎn)不止書(shū)上所介紹這些，它們各有特點(diǎn)和優(yōu)缺點(diǎn)，沒(méi)有一種方法在各種情況下都是最好的。 排序算法總結(jié) 排 序 算 法 冒泡排序 快速排序 簡(jiǎn)單插入排序 希爾排序 簡(jiǎn)單選擇排序 堆排序 時(shí)間復(fù)雜性 平均情況 最好情況 最壞情況 穩(wěn) 定 性 O(n2) O(n) O(n2) O(nlogn) O(nlogn) O(n2) O(n2) O(n) O(n2) O() O(n) O() O(n2) O(n2) O(n2) O(nlogn) O(nlogn) O(nlogn) 穩(wěn)定 不穩(wěn)定 穩(wěn)定 不穩(wěn)定 不穩(wěn)定 不穩(wěn)定 ? 在選擇排序算法時(shí)，需要考慮許多因素，如：線性表的長(zhǎng)度、數(shù)據(jù)元素本身的大小、關(guān)鍵字的結(jié)構(gòu)、對(duì)穩(wěn)定性的要求、存儲(chǔ)空間的限制、所使用的算法語(yǔ)言和計(jì)算機(jī)等等，不能簡(jiǎn)單地把算法的時(shí)間復(fù)雜性當(dāng)作唯一的選擇標(biāo)準(zhǔn)，必須對(duì)這些因素加以綜合考慮。 ? 實(shí)際上，如果待排序的數(shù)據(jù)量很小，最好選擇比較簡(jiǎn)單的排序算法，這些算法往往在處理較短線性表時(shí)具有很高的效率。反之，如果待處理的數(shù)據(jù)量很大，則必須選擇比較復(fù)雜的、時(shí)間復(fù)雜性較低的算法，它們?cè)谔幚泶罅繑?shù)據(jù)時(shí)的效率遠(yuǎn)遠(yuǎn)高于那些簡(jiǎn)單的排序算法。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1