K到Kn是堆在Kn+加入後將KKn+調成堆設c=n+f=ëc/û若Kf<=Kc則調整完成否則Kf與Kc交換之後c=ff=ëc/û繼續比較直到Kf<=Kc或f=即為根結點調整結束
()①child=child+; ②child/ ()不能調為大堆
()不需要因為建堆後R[]到R[n]是堆將R[]與R[n]交換後R[]到R[n]仍是堆故對R[]到R[n]只需從R[]往下篩選即可
() 堆是n個元素的序列堆可以看作是n個結點的完全二叉樹而樹型排序是n個元素作葉子結點的完全二叉樹因此堆占用的空間小調堆時利用堆本身就可以存放輸出的有序數據只需要一個記錄大小供交換用的輔助空間排序後heap數組中的關鍵字序列與堆是大堆還是小堆有關若利用大堆則為升序若利用小堆則為降序
最高位優先(MSD)法先對最高位關鍵字K進行排序將序列分成若干子序列每個子序列中的記錄都具有相同的K值然後分別就每個子序列對關鍵字K進行排序按K值不同再分成若干更小的子序列……依次重復直至最後對最低位關鍵字排序完成將所有子序列依次連接在一起成為一個有序子序列
最低位優先(LSD)法先對最低位關鍵字Kd進行排序然後對高一級關鍵字Kd進行排序依次重復直至對最高位關鍵字K排序後便成為一個有序序列進行排序時不必分成子序列對每個關鍵字都是整個序列參加排序但對Ki(<=i<d)排序時只能用穩定的排序方法另一方面按LSD進行排序時可以不通過關鍵字比較實現排序而是通過若干次分配和收集來實現排序
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23184.html
