Javascript堆排序算法詳解

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

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

堆排序分為兩個(gè)過程：

1.建堆。

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

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

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

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

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

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

function headAdjust(elements, pos, len){

  //將當(dāng)前節(jié)點(diǎn)值進(jìn)行保存

  var swap = elements[pos];

  //定位到當(dāng)前節(jié)點(diǎn)的左邊的子節(jié)點(diǎn)

  var child = pos * 2 + 1;

  //遞歸，直至沒有子節(jié)點(diǎn)為止

  while(child < len){

    //如果當(dāng)前節(jié)點(diǎn)有右邊的子節(jié)點(diǎn)，并且右子節(jié)點(diǎn)較大的場(chǎng)合，采用右子節(jié)點(diǎn)

    //和當(dāng)前節(jié)點(diǎn)進(jìn)行比較

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

      child += 1;

    }

    //比較當(dāng)前節(jié)點(diǎn)和最大的子節(jié)點(diǎn)，小于則進(jìn)行值交換，交換后將當(dāng)前節(jié)點(diǎn)定位

    //于子節(jié)點(diǎn)上

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

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

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

  //直至構(gòu)建出大頂堆（升序?yàn)榇箜?，降序?yàn)樾№敚?br />
  for(var i=elements.length/2; i>=0; i--){

    headAdjust(elements, i, elements.length);

  }

}

function sort(elements){

  //構(gòu)建堆

  buildHeap(elements);

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

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

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

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

    var swap = elements[i];

    elements[i] = elements[0];

    elements[0] = swap;

    //進(jìn)行調(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);