Javascript堆排序算法詳解

更新時間：2014年12月03日 14:50:03 投稿：hebedich

這篇文章主要介紹了Javascript堆排序算法及其示例，非常實用,需要的朋友可以參考下

堆排序分為兩個過程：

1.建堆。

堆實質(zhì)上是完全二叉樹，必須滿足：樹中任一非葉子結(jié)點的關(guān)鍵字均不大于（或不小于）其左右孩子（若存在）結(jié)點的關(guān)鍵字。

堆分為：大根堆和小根堆，升序排序采用大根堆，降序排序采用小根堆。

如果是大根堆，則通過調(diào)整函數(shù)將值最大的節(jié)點調(diào)整至堆根。

2.將堆根保存于尾部，并對剩余序列調(diào)用調(diào)整函數(shù)，調(diào)整完成后，再將最大跟保存于尾部-1（-1，-2，...，-i），再對剩余序列進行調(diào)整，反復(fù)進行該過程，直至排序完成。

復(fù)制代碼代碼如下:

//調(diào)整函數(shù)

function headAdjust(elements, pos, len){

  //將當前節(jié)點值進行保存

  var swap = elements[pos];

  //定位到當前節(jié)點的左邊的子節(jié)點

  var child = pos * 2 + 1;

  //遞歸，直至沒有子節(jié)點為止

  while(child < len){

    //如果當前節(jié)點有右邊的子節(jié)點，并且右子節(jié)點較大的場合，采用右子節(jié)點

    //和當前節(jié)點進行比較

    if(child + 1 < len && elements[child] < elements[child + 1]){

      child += 1;

    }

    //比較當前節(jié)點和最大的子節(jié)點，小于則進行值交換，交換后將當前節(jié)點定位

    //于子節(jié)點上

    if(elements[pos] < elements[child]){

      elements[pos] = elements[child];

      pos = child;

      child = pos * 2 + 1;

    }

    else{

      break;

    }

    elements[pos] = swap;

  }

}

//構(gòu)建堆

function buildHeap(elements){

  //從最后一個擁有子節(jié)點的節(jié)點開始，將該節(jié)點連同其子節(jié)點進行比較，

  //將最大的數(shù)交換與該節(jié)點,交換后，再依次向前節(jié)點進行相同交換處理，

  //直至構(gòu)建出大頂堆（升序為大頂，降序為小頂）

  for(var i=elements.length/2; i>=0; i--){

    headAdjust(elements, i, elements.length);

  }

}

function sort(elements){

  //構(gòu)建堆

  buildHeap(elements);

  //從數(shù)列的尾部開始進行調(diào)整

  for(var i=elements.length-1; i>0; i--){

    //堆頂永遠是最大元素，故，將堆頂和尾部元素交換，將

    //最大元素保存于尾部，并且不參與后面的調(diào)整

    var swap = elements[i];

    elements[i] = elements[0];

    elements[0] = swap;

    //進行調(diào)整，將最大）元素調(diào)整至堆頂

    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);