【正文】
/87 begin88 If (J M) And R[J].Key R[J+1].Key Then89 J := J + 1 //令J指向關(guān)鍵字較大的右孩子//90 //J指向R的左、右孩子中關(guān)鍵字較大者//91 If R[J].Key Then //孩子結(jié)點(diǎn)關(guān)鍵字較大//92 begin93 R := R[J]。 //將R[J]換到雙親位置上//94 I := J 。 J := 2*I //繼續(xù)以R[J]為當(dāng)前被調(diào)整結(jié)點(diǎn)往下層調(diào)整//95 end。96 Else97 Exit//調(diào)整完畢,退出循環(huán)//98 end99 R := X。//將最初被調(diào)整的結(jié)點(diǎn)放入正確位置//100 End。//Sift//復(fù)制代碼101 Procedure HeapSort(Var R : FileType)。 //對(duì)R[1..N]進(jìn)行堆排序//102 Begin103 For I := N Div Downto 1 Do //建立初始堆//104 Sift(R, I , N)105 For I := N Downto 2 do //進(jìn)行N1趟排序//106 begin107 T := R[1]。 R[1] := R。 R := T。//將當(dāng)前堆頂記錄和堆中最后一個(gè)記錄交換//108 Sift(R, 1, I1) //將R[1..I1]重成堆//109 end110 End。 //HeapSort//復(fù)制代碼六、幾種排序算法的比較和選擇1. 選取排序方法需要考慮的因素:(1) 待排序的元素?cái)?shù)目n;(2) 元素本身信息量的大小;(3) 關(guān)鍵字的結(jié)構(gòu)及其分布情況;(4) 語言工具的條件,輔助空間的大小等。2. 小結(jié):(1) 若n較小(n = 50),則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記錄移動(dòng)操作較直接選擇排序多,因而當(dāng)記錄本身信息量較大時(shí),用直接選擇排序較好。(2) 若文件的初始狀態(tài)已按關(guān)鍵字基本有序,則選用直接插入或冒泡排序?yàn)橐恕?3) 若n較大,則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法:快速排序、堆排序或歸并排序??焖倥判蚴悄壳盎诒容^的內(nèi)部排序法中被認(rèn)為是最好的方法。(4) 在基于比較排序方法中,每次比較兩個(gè)關(guān)鍵字的大小之后,僅僅出現(xiàn)兩種可能的轉(zhuǎn)移,因此可以用一棵二叉樹來描述比較判定過程,由此可以證明:當(dāng)文件的n個(gè)關(guān)鍵字隨機(jī)分布時(shí),任何借助于比較的排序算法,至少需要O(nlog2n)的時(shí)間。這句話很重要 它告訴我們自己寫的算法 是有改進(jìn)到最優(yōu) 當(dāng)然沒有必要一直追求最優(yōu)(5) 當(dāng)記錄本身信息量較大時(shí),為避免耗費(fèi)大量時(shí)間移動(dòng)記錄,可以用鏈表作為存儲(chǔ)結(jié)構(gòu)。