DIV CSS 佈局教程網

JavaScript 堆排序(Heap Sort)原理與實作全解
編輯:JavaScript基礎知識     

堆排序的整個流程可以切成兩段:先把資料整理成「堆」,再反覆把堆頂的最大值搬到尾端。

第一步:建立堆

堆在本質上是一棵完全二元樹,但用陣列表示即可,不必真的建立節點。它必須滿足堆序性質:任一非葉節點的值都不小於(大根堆)或不於(小根堆)其左右子節點。

以索引 i 表示某節點時,其左子節點為 2i + 1、右子節點為 2i + 2。升序排序用大根堆,降序排序則用小根堆。建堆的做法是從「最後一個擁有子節點的節點」開始,一路往前對每個節點執行下沉調整,把最大值換到該子樹的根。

第二步:反覆取出堆頂

堆建立完成後,堆頂就是全域最大值。把它和陣列尾端交換,最大值就固定在尾端且不再參與後續調整;接著對剩下的 0 … i-1 區間重新下沉調整,讓新的最大值浮到堆頂。以此類推,尾端會依序填入第 2 大、第 3 大……直到排序完成。

程式碼實作

// 下沉調整:讓 pos 位置的元素沿著較大的子節點往下換,直到符合大根堆
function headAdjust(elements, pos, len) {
  var current = elements[pos];
  var child = pos * 2 + 1;              // 左子節點
  while (child < len) {
    // 若右子節點存在且更大,改與右子節點比較
    if (child + 1 < len && elements[child] < elements[child + 1]) {
      child += 1;
    }
    // 父節點已不小於最大的子節點,堆序恢復,收工
    if (current >= elements[child]) break;

    elements[pos] = elements[child];    // 子節點上移
    pos = child;
    child = pos * 2 + 1;
  }
  elements[pos] = current;              // 原值放到最終落點
}

// 建堆:從最後一個有子節點的節點往前掃
function buildHeap(elements) {
  for (var i = Math.floor(elements.length / 2) - 1; 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);         // 對縮短後的區間重新調整
  }
  return elements;
}

var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' + elements);
sort(elements);
console.log('after : ' + elements);

相比原始寫法,這裡把建堆的起點改成 Math.floor(length / 2) - 1(第一個非葉節點),並把下沉過程簡化為「記住原值、一路把子節點上提、最後一次寫入」,比較次數明顯下降,也更不容易寫錯。

效率分析

  • 時間複雜度:最佳、平均、最差皆為 O(n log n)。這正是堆排序最大的優勢——它不會像快速排序那樣退化到 O(n²)。
  • 空間複雜度:O(1),原地排序。
  • 穩定性:不穩定。長距離搬移會破壞相同值的相對順序。
XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved