堆排序
堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特征使得在當前無序區中選取最大(或最小)關鍵字的記錄變得
簡單
()用大根堆排序的基本思想
① 先將初始文件R[n]建成一個大根堆此堆為初始的無序區
② 再將關鍵字最大的記錄R[](即堆頂)和無序區的最後一個記錄R[n]交換由此得到新的無序區R[n]和有序區R[n]且滿足
R[n]keys≤R[n]key
③ 由於交換後新的根R[]可能違反堆性質故應將當前無序區R[n]調整為堆然後再次將R[n]中關鍵字最大的記錄
R[]和該區間的最後一個記錄R[n]交換由此得到新的無序區R[n]和有序區R[nn]且仍滿足關系R[n
]keys≤R[nn]keys同樣要將R[n]調整為堆
……
直到無序區只有一個元素為止
()大根堆排序算法的基本操作
① 初始化操作將R[n]構造為初始堆;
② 每一趟排序的基本操作將當前無序區的堆頂記錄R[]和該區間的最後一個記錄交換然後將新的無序區調整為堆(亦稱重建堆
)
注意
①只需做n趟排序選出較大的n個關鍵字即可以使得文件遞增有序
②用小根堆排序與利用大根堆類似只不過其排序結果是遞減有序的堆排序和直接選擇排序相反在任何時刻堆排序中無序區總
是在有序區之前且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止
()堆排序的算法
void HeapSort(SeqIAst R)
{ //對R[n]進行堆排序不妨用R[]做暫存單元
int i;
BuildHeap(R); //將R[n]建成初始堆
for(i=n;i>;i){ //對當前無序區R[i]進行堆排序共做n趟
R[]=R[];R[]=R[i];R[i]=R[]; //將堆頂和堆中最後一個記錄交換
Heapify(Ri); //將R[i]重新調整為堆僅有R[]可能違反堆性質
} //endfor
} //HeapSort
From:http://tw.wingwit.com/Article/program/sjjg/201311/23780.html
