【正文】 方法：從完全二叉樹的最后一個非終端結(jié)點└ n/2┘開始 ， 反復(fù)調(diào)用篩選過程 ， 直到第一個結(jié)點 ， 則得到一個堆 。 13 49 76 38 49’ 97 65 27 65 49 76 38 97 49’ 13 27 27 13 76 38 49’ 97 65 49 例： {49， 38， 65， 97， 76， 13， 27， 49’} 選擇排序 ⒍ 堆排序過程 PROC headsort(VAR r:listtype)。 FOR i:= └ n/2┘ DOWNTO 1 DO shift(r,i,n)。 {自第 └ n/2┘開始篩選建堆 } FOR i:=n DOWNTO 2 DO [ r[1]←→r[i]。 {堆頂與堆中最后一個記錄交換 } shift(r,1,i1) {使 r[1..i1]成為堆 } ] ENDP。 {headsort} 堆排序是不穩(wěn)定的，時間復(fù)雜度為 O(nlogn)。 歸并排序 ⒈ 歸并概念 ： 把 2 個有序子文件合并成一個有序文件的過程 ， 稱為 2路歸并 。 歸并排序基本思想：⑴將文件的每個記錄視為一個有序子文件；⑵然后兩兩子文件進(jìn)行 2路歸并；⑶重復(fù)⑵，直到只剩一個長度為 n的有序文件 例：初始關(guān)鍵字： 49 38 65 97 76 13 27 49’ 第一趟后 38 49 65 97 13 76 27 49’ 第二趟后 38 49 65 97 13 27 49’ 76 第三趟后 13 27 38 49 49’ 65 76 97 每個記錄視為一個有序子文件，兩個子文件進(jìn)行歸并，得 4個有序子文件。 ⒉ 歸并排序過程 PROC merge(r:listtype。 l,m,n:integer。VAR r2:listtype)。 { t[s..m]和 r[m+1..n] 為兩個有序子文件 , 歸并結(jié)果存放在 r2[s..n]中 } i:=s。 j:=m+1。 k:=s1。 WHILE (i≤m) AND (j≤n) DO [ k:=k+1。 {k為下一次存入 r2的位置 } IF r[i].key≤r[j].key THEN [ r2[k]:=r[i]。 i:=i+1] ELSE [ r2[k]:=r[j]。 i:=j+1] ]。 IF i≤m THEN r2[k+1..n]:=r[i..m]。 IF j≤n THEN r2[k+1..n]:=r[j..n] {將其中一個文件的余下部分復(fù)制到 r2的尾部 } ENDP。 {merge} 歸并排序是穩(wěn)定的，時間復(fù)雜度為 O(nlogn)， 需要和待排序記錄相等數(shù)量的輔助空間 r2。 基數(shù)排序 基數(shù)排序法是一種用多關(guān)鍵字排序思想對單邏輯關(guān)鍵字進(jìn)行排序 ， 而無需進(jìn)行關(guān)鍵字比較的新排序方法 ， 其基本操作是 “ 分配 ” 和 “ 收集 ” 。 ⒈ 基數(shù)排序方法 ：基數(shù)排序是按組成關(guān)鍵字的各位的值進(jìn)行分配和收集 ， 與前面介紹的排序方法不同 ，它無需進(jìn)行關(guān)鍵字之間的比較 。 設(shè)關(guān)鍵字有 d 位，每位的取值范圍為 r (稱為基數(shù) )，則需要進(jìn)行 d 趟分配與收集，需要設(shè)立 r 個隊列。例如，若每位是十進(jìn)制數(shù)字，則需要設(shè)立 10個隊列，若每位由小寫字母組成，則要設(shè)立 26個隊列 。 基數(shù)排序 2. 基數(shù)排序的步驟 ⑴ 從關(guān)鍵字的低位開始進(jìn)行第 i趟 (i=1,2,...d)分配即將單鏈表中的記錄依次按關(guān)鍵字的第 i位分配到相應(yīng)編號的隊列中； ⑵ 分配完畢后 ， 將各隊列的記錄按隊列編號順序收集成一個單鏈表； ⑶ 重復(fù) ⑴⑵ ， 直到第 d趟收集完畢 ， 所得單鏈表已成為有序表 。 基數(shù)排序 例： 初始 278— 109— 063— 930— 589— 184— 505— 269— 008— 083 0 1 2 3 4 5 6 7 8 9 第一趟分配 269 083 008 589 930 063 184 505 278 109 第一趟收集 930— 063— 083— 184— 505— 278— 008— 109— 589— 269 第二趟分配 109 589 008 269 184 505 930 063 278 083 第二趟收集 505— 008— 109— 930— 063— 269— 278— 083— 184— 589 第三趟分配 083 063 184 278 589 008 109 269 505 930 第三趟收集 008— 063— 083— 109— 184— 269— 278— 505— 589— 930 基數(shù)排序 ⒊ 基數(shù)排序的特點 ⑴ 基數(shù)排序的基本操作是 分配 和 收集 ， 而不是關(guān)鍵字之間的比較； ⑵ 基數(shù)排序是穩(wěn)定的 ， 其時間復(fù)雜度為 O(d(n+rd))，其中 n是記錄數(shù) ， d是關(guān)鍵字的位數(shù) ， r是關(guān)鍵字各位的值域 。 ⑶ 基數(shù)排序要進(jìn)行 d趟分配和收集 ,需 r個隊列