堆排序可以拆成兩個階段。
第一階段:建堆。堆本質上是一棵完全二叉樹,必須滿足:樹中任一非葉節點的關鍵字都不大於(或小於)其左右孩子節點的關鍵字。依此分成大根堆與小根堆——升序排序用大根堆,降序排序用小根堆。以升序為例,透過調整函數把最大值一路推到堆根。
第二階段:反覆取出堆頂。把堆根與尾端元素交換,最大值就此定位在尾部;接著對剩下的序列重新調整,再把新的最大值放到倒數第二個位置,以此類推(-1、-2、…、-i),直到排序完成。
實作如下:
//調整函數
function headAdjust(elements, pos, len){
//將當前節點值進行保存
var swap = elements[pos];
//定位到當前節點的左邊的子節點
var child = pos * 2 + 1;
//遞歸,直至沒有子節點為止
while(child < len){
//如果當前節點有右邊的子節點,並且右子節點較大的場合,采用右子節點
//和當前節點進行比較
if(child + 1 < len && elements[child] < elements[child + 1]){
child += 1;
}
//比較當前節點和最大的子節點,小於則進行值交換,交換後將當前節點定位
//於子節點上
if(elements[pos] < elements[child]){
elements[pos] = elements[child];
pos = child;
child = pos * 2 + 1;
}
else{
break;
}
elements[pos] = swap;
}
}
//構建堆
function buildHeap(elements){
//從最後一個擁有子節點的節點開始,將該節點連同其子節點進行比較,
//將最大的數交換與該節點,交換後,再依次向前節點進行相同交換處理,
//直至構建出大頂堆(升序為大頂,降序為小頂)
for(var i=elements.length/2; i>=0; i--){
headAdjust(elements, i, elements.length);
}
}
function sort(elements){
//構建堆
buildHeap(elements);
//從數列的尾部開始進行調整
for(var i=elements.length-1; i>0; i--){
//堆頂永遠是最大元素,故,將堆頂和尾部元素交換,將
//最大元素保存於尾部,並且不參與後面的調整
var swap = elements[i];
elements[i] = elements[0];
elements[0] = swap;
//進行調整,將最大)元素調整至堆頂
headAdjust(elements, 0, i);
}
}
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' + elements);
sort(elements);
console.log(' after: ' + elements);
幾個實作細節值得留意。buildHeap 從 length/2 開始往回走,因為只有非葉節點才可能有子節點需要比較,從最後一個非葉節點往前掃即可。headAdjust 裡用 swap 暫存初始值、最後再回填,避免了多餘的寫入次數。而迴圈內把 pos 往子節點移動,實質就是「下沉」的過程。
效率:
時間複雜度:最好 O(n log₂n),最壞 O(n log₂n),平均 O(n log₂n)。
空間複雜度:O(1)。
穩定性:不穩定。