第十章內(nèi)部排序(文件)
【正文】 r[s]。 WHILE (i＜ j) AND (r[i].key≤x) DO i:=i+1。 38 65， 快速排序結(jié)果為 : 38 4939。 選擇排序 一 .簡單選擇排序 ⒈ 基本思想 ： 對文件進行 n1趟排序，第 i趟(i=1,2,...n1)是在從 i到 n的 ni+1個記錄中選擇關(guān)鍵字最小的記錄，并將它與第 i個記錄進行交換。 IF k≠i THEN r[i]←→r[k] ] ENDP。 選擇排序 二 . 堆排序 ⒈ 堆的定義 ： n個元素的序列 {K1,K2,...,Kn} 若滿足： Ki≤K2i 或 Ki≥K2i Ki≤K2i +1 Ki≥K2i+1 (i=1, 2,... n/2) 稱為堆。 關(guān)鍵要解決⑴和⑶，即如何由一個無序序列建成一個堆 ? 如何調(diào)整余下的元素成為一個新堆 ? 選擇排序 ⒊ 調(diào)整方法 ⑴ 將堆頂元素和堆的最后一個元素位置交換； ⑵ 然后以當(dāng)前堆頂元素和其左 、 右子樹的根結(jié)點進行比較 (此時 ， 左 、 右子樹均為堆 )， 并與值較小的結(jié)點進行交換； ⑶ 重復(fù) ⑵ ， 繼續(xù)調(diào)整被交換過的子樹 ， 直到葉結(jié)點或沒進行交換為止 。 { 已知 v[k..m]是以 r[k]為根的完全二叉樹 , 以 r[2k]和 r[2k+1] 為根的左 、 右子樹是堆 。 t:=r[k]。 i:=j。 FOR i:= └ n/2┘ DOWNTO 1 DO shift(r,i,n)。 歸并排序 ⒈ 歸并概念 ： 把 2 個有序子文件合并成一個有序文件的過程 ， 稱為 2路歸并 。VAR r2:listtype)。 WHILE (i≤m) AND (j≤n) DO [ k:=k+1。 IF i≤m THEN r2[k+1..n]:=r[i..m]。 ⒈ 基數(shù)排序方法 ：基數(shù)排序是按組成關(guān)鍵字的各位的值進行分配和收集 ， 與前面介紹的排序方法不同 ，它無需進行關(guān)鍵字之間的比較 。 基數(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ù)字，則需要設(shè)立 10個隊列，若每位由小寫字母組成，則要設(shè)立 26個隊列 。 {merge} 歸并排序是穩(wěn)定的，時間復(fù)雜度為 O(nlogn)， 需要和待排序記錄相等數(shù)量的輔助空間 r2。 i:=i+1] ELSE [ r2[k]:=r[j]。 j:=m+1。 ⒉ 歸并排序過程 PROC merge(r:listtype。 {堆頂與堆中最后一個記錄交換 } shift(r,1,i1) {使 r[1..i1]成為堆 } ] ENDP。 {sift} 選擇排序 ⒌ 無序序列建堆過程 方法：從完全二叉樹的最后一個非終端結(jié)點└ n/2┘開始 ， 反復(fù)調(diào)用篩選過程 ， 直到第一個結(jié)點 ， 則得到一個堆 。 WHILE (j≤m) AND NOT finished DO [ IF (j＜ m) AND (r[j].key＞ r[j+1].key) THEN j:=j+1。 j:=2*i。 選擇排序 例： 27 13 76 38 49’ 97 65 49 輸出 13 27 97 76 38 49’ 13 65 49 篩選 49 27 76 38 49’ 13 65 97 篩選結(jié)果 輸出 27 49 97 76 38 49’ 13 65 27 1 2 49 38 76 49’ 97 13 65 27 選擇排序 選擇排序 ⒋ 篩選過程 PROC shift(VAR r:listtype。 堆頂元素 (即完全二叉樹的根 )是序列中最
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1