參考：
- Java排序算法(五)：堆排序
- 【算法與數(shù)據(jù)結(jié)構(gòu)】圖說(shuō)堆排序
- 【數(shù)據(jù)結(jié)構(gòu)】排序算法：希爾、歸并水慨、快速蔚叨、堆排序
0. 完全二叉樹(shù)性質(zhì)
- 在完全二叉樹(shù)中，所有大于n/2的節(jié)點(diǎn)都是葉子節(jié)點(diǎn)粥诫；
- 如果2i+1<n,則左孩子節(jié)點(diǎn)序號(hào)為2i+1油航；否則i無(wú)左孩子；
如果2i+2<n,則右孩子節(jié)點(diǎn)序號(hào)為2i+2怀浆；否則i無(wú)有孩子谊囚；
1. 算法說(shuō)明
堆排序是對(duì)簡(jiǎn)單排序的一種改進(jìn)；
簡(jiǎn)單排序的缺點(diǎn)：
簡(jiǎn)單排序要從n條記錄中找出一個(gè)最小的記錄执赡，需要比較n-1次镰踏。
但是這樣的操作并沒(méi)有把每一趟的比較結(jié)果都保存下來(lái)，在后一趟比較過(guò)程中沙合，有許多比較在前一趟中已經(jīng)做過(guò)了奠伪，但由于前一趟并未保存這些比較結(jié)果，所以后一趟排序又重復(fù)執(zhí)行了這些比較操作，因而比較次數(shù)較多绊率。-
堆排序是一顆完全二叉樹(shù)谨敛。
- 大頂堆：每個(gè)節(jié)點(diǎn)都>=其左右孩子節(jié)點(diǎn)的值；
- 小頂堆：每個(gè)節(jié)點(diǎn)都<=其左右孩子節(jié)點(diǎn)的值滤否；
大頂堆和小頂堆
2. 算法思想
步驟：
將待排序的序列構(gòu)造成一個(gè)大頂堆脸狸。此時(shí)，整個(gè)序列的最大值藐俺，就是堆頂?shù)母?jié)點(diǎn)炊甲。將它移走（和堆數(shù)組的最后元素交換，此時(shí)末尾的元素就是最大值 ）欲芹，將剩余的n-1個(gè)元素重新構(gòu)建成一個(gè)堆卿啡，就會(huì)得到n個(gè)元素中的次大值。如此反復(fù)耀石，就能得到一個(gè)有序序列牵囤。-
問(wèn)題：
- 如何將一個(gè)無(wú)序序列構(gòu)建成一個(gè)堆爸黄？
- 如何在輸出堆頂元素之后滞伟，調(diào)整剩余的元素成為一個(gè)新堆？
3. java代碼實(shí)現(xiàn)
堆排序
建堆/調(diào)整堆過(guò)程
測(cè)試方法
結(jié)果
4.時(shí)間復(fù)雜度
- O(nlogn)
- 堆排序是不穩(wěn)定排序炕贵；
