摘要: 大根堆排序的基本思想
① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區
② 再將關鍵字最大的記錄R[1](即堆頂)和無序區的最后一個記錄R[n]交換，
由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key
③ 由于交換后新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。
然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最后一個記錄R[n-1]交換，
由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n- 2].keys≤R[n-1..n].keys，
同樣要將R[1..n-2]調整為堆。
閱讀全文