[理學]9排序技術(shù)(參考版)
2025-01-22 14:37本頁面
【正文】 反之，如果待處理的數(shù)據(jù)量很大，則必須選擇比較復(fù)雜的、時間復(fù)雜性較低的算法，它們在處理大量數(shù)據(jù)時的效率遠遠高于那些簡單的排序算法。 排序算法總結(jié) 排 序 算 法 冒泡排序 快速排序 簡單插入排序 希爾排序 簡單選擇排序 堆排序 時間復(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ù)據(jù)元素本身的大小、關(guān)鍵字的結(jié)構(gòu)、對穩(wěn)定性的要求、存儲空間的限制、所使用的算法語言和計算機等等，不能簡單地把算法的時間復(fù)雜性當作唯一的選擇標準，必須對這些因素加以綜合考慮。H(i)=t /*堆頂元素換到最后 */ SIFT(H,i1,1) /*調(diào)整建堆 */ } RETURN 堆排序的方法對于規(guī)模較小的線性表并不適合，但對于 較大規(guī)模的線性表來說是很有效的。 [算法 ] 堆排序 輸入：無序序列 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) /*無序序列建堆 */ FOR i=n TO 2 BY 1 DO { t=H(1)。 不考慮已經(jīng)換到最后的那個元素，只考慮前 n－ 1個元素構(gòu)成的子序列，顯然，該子序列已不是堆，但左、右子樹仍為堆，可以將該子序列調(diào)整為堆。 堆排序 (1)首先將一個無序序列建成堆。 ? 假設(shè)無序序列 H(1:n)以完全二叉樹表示。因此算法中沒有用到指針運算，而只用到數(shù)組的 下標運算。j=2m } else j=n+1 } H(m)=t RETURN 完全二叉樹中的所有結(jié)點值是從根結(jié)點開始一層一層地從 左到右存儲在一維數(shù)組 H中。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)。 輸出：以 H(m)為根結(jié)點的子樹為堆。 [算法 ] 調(diào)整建堆 輸入：完全二叉樹數(shù)組 H(1:n)。 堆排序?qū)儆谶x擇類的排序方法 堆的示意圖（堆頂元素最大） ? 序列（ 91， 85， 53， 36， 47， 30， 24， 12）是一個堆，如圖： 91 85 53 36 47 30 24 12 ? 在一棵具有 n個結(jié)點的完全二叉樹（用一維數(shù)組 H(1:n)表示）中，假設(shè)結(jié)點 H（ m）的左右子樹均為堆，現(xiàn)要將 H（ m）為根結(jié)點的子樹也調(diào)整為堆，這就是調(diào)整建堆的過程。 ? 堆（ Heap）是與二叉排序樹不同的一種二叉樹，它的定義為： 一個完全二叉樹，它的每個結(jié)點對應(yīng)于原始數(shù)據(jù)的一個元素，且規(guī)定如果一個結(jié)點有兒子結(jié)點，此結(jié)點數(shù)據(jù)必須大于或等于其兒子結(jié)點數(shù)據(jù)。 由堆的定義可以看出，堆頂元素 (即第一個元素 )必為最大項。 } 堆的定義： 具有 n個元素的序列 (h1， h2， … ， hn)，當且僅當滿足 堆排序定義 hi = h2i hi = h2i+1 hi = h2i hi = h2i+1 或 (i＝ 1， 2， … ， n/2) 時稱之為堆。p[k]=d。 if(k!=i) { d=p[i]。j=n1。i++) { k=i。 for(i=0。P(k)=d } } RETURN 簡單選擇排序算法的 C語言描述： insort（ ET P[]， int n） { int j,k。 簡單選擇排序過程示意圖 原序列 89 21 56 48 85 16 19 47 第一遍選擇 16 21 56 48 85 89 19 47 第二遍選擇 16 19 56 48 85 89 21 47 第三遍選擇 16 19 21 48 85 89 56 47 第四遍選擇 16 19 21 47 85 89 56 48 第五遍選擇 16 19 21 47 48 89 56 85 第六遍選擇 16 19 21 47 48 56
教學課件相關(guān)推薦
鄂ICP備17016276號-1