JS實作堆疊排序-js教程-PHP中文網

JS實作堆疊排序

不言

發布： 2018-07-07 17:50:38

原創

1837 人瀏覽過

這篇文章主要介紹了關於JS實現堆排序，有著一定的參考價值，現在分享給大家，有需要的朋友可以參考一下

堆的預備知識

堆是一個完全二元樹。
完全二元樹：二元樹除開最後一層，其他層結點數都達到最大，最後一層的所有結點都集中在左邊（左邊結點排列滿的情況下，右邊才能缺結點）。
大頂堆：根結點為最大值，每個結點的值大於或等於其孩子結點的值。
小頂堆：根結點為最小值，每個結點的值小於或等於其孩子結點的值。
堆的儲存：堆由陣列來實現，相當於對二元樹做層序遍歷。如下圖：

JS實作堆疊排序

#對於結點i ，其子結點為2i 1 與2i 2 。

堆排序演算法

JS實作堆疊排序

現在需要對如上二元樹做升序排序，總共分成三個步驟：

將初始二元樹轉換為大頂堆（heapify），此時根結點為最大值，將其與最後一個結點交換。
除開最後一個結點，將其餘節點組成的新堆轉換為大頂堆，此時根結點為次最大值，將其與最後一個結點交換。
重複步驟2，直到堆中元素個數為1（或其對應陣列的長度為1），排序完成。

下面詳細圖解這個過程：

步驟1：

初始化大頂堆，首先選取最後一個非葉子結點(我們只需要調整父節點和孩子節點之間的大小關係，葉子結點之間的大小關係無需調整)。設數組為arr，則第一個非葉結點的下標為：i = Math.floor(arr.length/2 - 1) = 1，也就是數字4，如圖中虛線框，找出三個數字的最大值，與父節點交換。

JS實作堆疊排序

然後，下標 i 依序減1（即從第一個非葉子結點開始，從右至左，從下至上遍歷所有非葉子節點）。後面的每一次調整都是如此：找到父子結點中的最大值，做交換。

JS實作堆疊排序

這一步驟中數字6、1交換後，數字[1,5,4]組成的堆順序不對，需要執行一步調整。因此需要注意，每次調整一個非葉子結點後，都要觀察是否會影響子堆順序！

JS實作堆疊排序

這次調整後，根節點為最大值，形成了一個大頂堆，將根節點與最後一個結點交換。

步驟2：

除開目前最後一個結點6(即最大值)，將其餘結點[4,5,3,1]組成新堆轉化為大頂堆(注意觀察，此時根節點以外的其他結點，都滿足大頂堆的特徵，所以可以從根節點4開始調整，即找到4應該處於的位置即可)。

JS實作堆疊排序

#步驟3：

接下來重複執行步驟2，直到堆中元素個數為1：

JS實作堆疊排序

#堆中元素個數為1，排序完成。

JavaScript實作

// 交换两个节点
function swap(A, i, j) {
  let temp = A[i];
  A[i] = A[j];
  A[j] = temp; 
}

// 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
// 假设 结点 i 以下的子堆已经是一个大顶堆，adjustheap 函数实现的
// 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。后面
// 将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点
// 都执行 adjustheap 操作，所以就满足了结点 i 以下的子堆已经是一大
//顶堆
function adjustHeap(A, i, length) {
  let temp = A[i]; // 当前父节点
// j<length function>=0; i--) {
    adjustHeap(A, i, A.length);
  }
  // 排序，每一次for循环找出一个当前最大值，数组长度减一
  for(let i = Math.floor(A.length-1); i>0; i--) {
    swap(A, 0, i); // 根节点与最后一个节点交换
    adjustHeap(A, 0, i); // 从根节点开始调整，并且最后一个结点已经为当
                         // 前最大值，不需要再参与比较，所以第三个参数
                         // 为 i，即比较到最后一个结点前一个即可
  }
}

let Arr = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
heapSort(Arr);
alert(Arr);</length>

登入後複製

程式註解：將i 結點以下的堆整理為大頂堆，注意這一步實現的基礎其實是：假設結點i 以下的子堆已經是一個大頂堆，adjustHeap 函數實現的功能是實際上是：找到結點i 在包含結點i 的堆中的正確位置。後面做第一次堆化時，heapSort 中寫了一個for 循環，從第一個非葉子結點開始，對每一個非葉子結點都執行adjustHeap 操作，所以就滿足了每一次adjustHeap 中，結點i 以下的子堆已經是一大頂堆。

複雜度分析：adjustHeap 函數中相當於堆的每一層只遍歷一個結點，因為
具有n個結點的完全二叉樹的深度為[log2n] 1，所以adjustHeap 的複雜度為O(logn)，而外層循環共有f(n) 次，所以最終的複雜度為O(nlogn)。