堆排序

堆排序是一種原地的、時(shí)間復(fù)雜度為 O(nlogn) 的排序算法。

什么是堆

• 堆是一個(gè)完全二叉樹（除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都是滿的，最后一層的節(jié)點(diǎn)都靠左排列）；
• 堆中每一個(gè)節(jié)點(diǎn)的值都必須大于等于（或小于等于）其子樹中每個(gè)節(jié)點(diǎn)的值

分類

堆分為大頂堆和小頂堆。
大頂堆是所有父節(jié)點(diǎn)都大于其子節(jié)點(diǎn)大
小頂堆所有父節(jié)點(diǎn)都小于其子節(jié)點(diǎn)
1 是大頂堆
3 是小頂堆

image

如何實(shí)現(xiàn)一個(gè)堆

完全二叉樹比較適合用數(shù)組來存儲。用數(shù)組來存儲完全二叉樹是非常節(jié)省存儲空間的。因?yàn)槲覀儾恍枰鎯ψ笥易庸?jié)點(diǎn)的指針，單純地通過數(shù)組的下標(biāo)，就可以找到一個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)和父節(jié)點(diǎn)。

堆化（插入一個(gè)數(shù)，調(diào)整，維持堆的特性）非常簡單，就是順著節(jié)點(diǎn)所在的路徑，向上或者向下，對比，然后交換。

image

如何基于堆實(shí)現(xiàn)排序

我們可以把堆排序的過程大致分解成三大步驟，建堆、堆化、堆排序。

建堆

首先將數(shù)組原地建成一個(gè)堆。所謂“原地”就是，不借助另一個(gè)數(shù)組，就在原數(shù)組上操作。就是按照數(shù)組的順序，放到對應(yīng)數(shù)的位置上， 不需要進(jìn)行額外操作。

堆化

以大頂堆為例，一般按照從下往上、從右向左進(jìn)行堆化操作，先找到最后一個(gè)端節(jié)點(diǎn)（非子節(jié)點(diǎn)），將其與子節(jié)點(diǎn)進(jìn)行對比，比端節(jié)點(diǎn)大的與端節(jié)點(diǎn)進(jìn)行交換，確保端節(jié)點(diǎn)以下的節(jié)點(diǎn)都比端節(jié)點(diǎn)小，以此類推，層層向上堆化，確保頂級元素最大。

堆排序

調(diào)整堆，調(diào)整過程需要保證堆序性質(zhì)：在一個(gè)二叉堆中任意父節(jié)點(diǎn)大于其子節(jié)點(diǎn)。

1、堆排序，取出位于堆頂?shù)牡谝粋€(gè)數(shù)據(jù)（最大堆則為最大數(shù)，最小堆則為最小數(shù)），與最后一個(gè)元素進(jìn)行交換，對剩余元素進(jìn)行堆化
2、繼續(xù)按照步驟1進(jìn)行，取出堆最低層節(jié)點(diǎn)與根節(jié)點(diǎn)互換，再進(jìn)行堆化。
3、最后輸出排序好的數(shù)組。

image

評價(jià)

評價(jià)算法好壞
堆排序是非穩(wěn)定的排序算法

分類：排序算法

數(shù)據(jù)結(jié)構(gòu)：數(shù)組

最優(yōu)時(shí)間復(fù)雜度：O(n*log(n))，當(dāng)keys 的值都不一樣；O(n)，當(dāng)keys 的值都一樣

最壞時(shí)間復(fù)雜度：O(n*log(n))

平均時(shí)間復(fù)雜度：O(n*log(n))

最壞空間復(fù)雜度：輔助O(1)

時(shí)間復(fù)雜度

image

代碼實(shí)現(xiàn)

// 調(diào)整堆 調(diào)整為大頂堆
function heapAjust(data, i, len) {
  let child = 2 * i + 1; // 左子節(jié)點(diǎn)

  while(child <= len) {
    // 如果右子節(jié)點(diǎn)存在 且大于左節(jié)點(diǎn)值，child指向右節(jié)點(diǎn)
    if (child + 1 <= len && data[child] < data[child + 1]) {
      child = child + 1;
    }
    // 入股當(dāng)前節(jié)點(diǎn)值小于子節(jié)點(diǎn) 互換
    if (data[child] > data[i]) {
      [data[i], data[child]] = [data[child], data[i]];
      i = child;
      child = 2 * i + 1;
    } else {
      break;
    }
  }
}
// 堆排序
function heapSort(A) {
  // 建堆 從后往前 從右向左 構(gòu)建大頂堆
  for(let i = Math.floor((A.length - 2) / 2); i >= 0; i--) {
    heapAjust(A, i, A.length);
  }
  // 堆排序 最下面元素與堆頂元素交換
  for(let j = A.length - 1; j > 0; j--) {
    [A[j], A[0]] = [A[0], A[j]];
    // 大頂推排序 從頂向下調(diào)整堆 移到尾部的不參與排序 最后效果從小到大排序
    heapAjust(A, 0, j - 1);
  }
  return A;
}

heapSort([10,3,22,3,233,34,55,6])

參考文檔

• 堆排序
• 選擇排序