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