DIV CSS 佈局教程網

 DIV+CSS佈局教程網 >> 網頁腳本 >> JavaScript入門知識 >> 關於JavaScript >> Javascript堆排序算法詳解
Javascript堆排序算法詳解
編輯:關於JavaScript     

堆排序分為兩個過程:

1.建堆。

堆實質上是完全二叉樹,必須滿足:樹中任一非葉子結點的關鍵字均不大於(或不小於)其左右孩子(若存在)結點的關鍵字。

堆分為:大根堆和小根堆,升序排序采用大根堆,降序排序采用小根堆。

如果是大根堆,則通過調整函數將值最大的節點調整至堆根。

2.將堆根保存於尾部,並對剩余序列調用調整函數,調整完成後,再將最大跟保存於尾部-1(-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);

效率:

時間復雜度:最好:O(nlog2n),最壞:O(nlog2n),平均:O(nlog2n)。

空間復雜度:O(1)。

穩定性:不穩定

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved