參考：

1. Java排序算法(五)：堆排序
2. 【算法與數(shù)據(jù)結(jié)構(gòu)】圖說堆排序
3. 【數(shù)據(jù)結(jié)構(gòu)】排序算法：希爾、歸并、快速、堆排序

0. 完全二叉樹性質(zhì)

1. 在完全二叉樹中，所有大于n/2的節(jié)點都是葉子節(jié)點；
2. 如果2i+1<n,則左孩子節(jié)點序號為2i+1；否則i無左孩子；
   如果2i+2<n,則右孩子節(jié)點序號為2i+2；否則i無有孩子；

1. 算法說明

堆排序是對簡單排序的一種改進(jìn)；

• 簡單排序的缺點：
  簡單排序要從n條記錄中找出一個最小的記錄，需要比較n-1次。
  但是這樣的操作并沒有把每一趟的比較結(jié)果都保存下來，在后一趟比較過程中，有許多比較在前一趟中已經(jīng)做過了，但由于前一趟并未保存這些比較結(jié)果，所以后一趟排序又重復(fù)執(zhí)行了這些比較操作，因而比較次數(shù)較多。

• 堆排序是一顆完全二叉樹。

  • 大頂堆：每個節(jié)點都>=其左右孩子節(jié)點的值；
  • 小頂堆：每個節(jié)點都<=其左右孩子節(jié)點的值；

大頂堆和小頂堆

2. 算法思想

• 步驟：
  將待排序的序列構(gòu)造成一個大頂堆。此時，整個序列的最大值，就是堆頂?shù)母?jié)點。將它移走（和堆數(shù)組的最后元素交換，此時末尾的元素就是最大值 ），將剩余的n-1個元素重新構(gòu)建成一個堆，就會得到n個元素中的次大值。如此反復(fù)，就能得到一個有序序列。

• 問題：

  1. 如何將一個無序序列構(gòu)建成一個堆？
  2. 如何在輸出堆頂元素之后，調(diào)整剩余的元素成為一個新堆？

3. java代碼實現(xiàn)

堆排序

建堆/調(diào)整堆過程

測試方法

結(jié)果

4.時間復(fù)雜度

• O(nlogn)
• 堆排序是不穩(wěn)定排序；