堆排序和快速排序一樣也是一個O(n logn)的排序算法
但是二者是不一樣的實現(xiàn)原理
[這是肯定的，不要pia我]
從分類上來看
快速排序 屬于交換排序
堆排序（heap sort）屬于選擇排序
前些日子接到一個電面，上來就問堆排序摊册，我一臉懵逼志于，我真的不記得贵少，我只能一臉懵逼的說我不會
超級尷尬有沒有镰烧！所以為了以后避免這種情況的發(fā)生乔询，先好好學(xué)堆排序吧谎砾。
先說原理：
1. 首先說一下堆
<u>堆heap</u>:
首先邏輯上的結(jié)構(gòu)是一個完全二叉樹(如果不知道什么是完全二叉樹的可以去百度)
然后按照父節(jié)點(diǎn)比子女節(jié)點(diǎn)都大/都小 分為大根堆和小根堆（也叫大頂堆 和 小頂堆）
大根堆：該完全二叉樹的節(jié)點(diǎn)任意一個非葉子節(jié)點(diǎn)的value都比它的子女節(jié)點(diǎn)大（>=）
小根堆：該完全二叉樹的節(jié)點(diǎn)任意一個非葉子節(jié)點(diǎn)的value都比它的子女節(jié)點(diǎn)蟹瓯丁（<=）
主要到前面的那個邏輯上了么？
因為目前遇到的堆排序其實很少是在樹這個數(shù)據(jù)結(jié)構(gòu)上進(jìn)行的(或者說是真正的在java/c中創(chuàng)建一個TreeNode類或者結(jié)構(gòu)體) 而是用數(shù)據(jù)/list 來存儲節(jié)點(diǎn)的（特指完全二叉樹景图，因為完全二叉樹的結(jié)構(gòu)真的是太完美了）较雕。
哎呀呀，忍不住來說一下一些很簡單的數(shù)組和完全二叉樹的轉(zhuǎn)化
其實就算是當(dāng)成游戲來找找規(guī)律挚币，這個轉(zhuǎn)化也不是很困難亮蒋，其實數(shù)組就是完全二叉樹的水平遍歷出來的。
然后不難發(fā)現(xiàn)在生成的數(shù)組中
array[0]其實是相當(dāng)于樹的根節(jié)點(diǎn)妆毕，然后她的子節(jié)點(diǎn)是array[1]和array[2]
array[1]子節(jié)點(diǎn)是array[3] array[4]
array[2]子節(jié)點(diǎn)是array[5] array[6]
………………………………….....
以此類推
非葉節(jié)點(diǎn)的子節(jié)點(diǎn)在數(shù)組中的體現(xiàn)就是
array[i]的子節(jié)點(diǎn)是 array[2i+1]和array[2i+2];
那么
大根堆就是：array[i] >= array[2i+1] && array[i] >= array[2i+2]
小根堆就是：array[i] <= array[2i+1] && array[i] <= array[2i+2]
算法詳細(xì)解釋
根據(jù)上面的對于堆的描述我們不難發(fā)現(xiàn)慎玖，
如果是一個大頂堆，那么根元素是最大的值
如果是一個小頂堆笛粘，那么跟元素是最小的值
但是堆也不是<u>有序</u>的趁怔，它只能保障節(jié)點(diǎn)的值比它的子女們大/小，但是他們子女們的大小順序是沒有保障的
因此需要通過排序薪前，才能實現(xiàn)堆的排序
2. 正式講堆排序的算法內(nèi)容：
①润努、首先構(gòu)造一個堆，堆排序是建立在堆的基礎(chǔ)上的(無序堆)
②示括、根據(jù)構(gòu)建的堆铺浇，將堆中第一個元素(堆頂/根節(jié)點(diǎn))和最后一個元素交換位置
那么最后一個元素就是一個最值，然后排除這個最后一個元素垛膝，將剩下的完全二叉樹重新調(diào)整為堆(無序堆)鳍侣，重復(fù)步驟②丁稀，直到只剩下一個元素為止
因此，
如果是以大頂堆來構(gòu)建 那么最后得到的是水平遍歷后是從小到大的完全二叉樹(有序小頂堆)
如果是以小頂堆來構(gòu)建 那么最后得到的是水平遍歷后是從大到小的完全二叉樹(有序大頂堆)
現(xiàn)在其實核心的算法并不難理解
而且看到重復(fù)步驟②這種口吻倚聚，我們也不難發(fā)現(xiàn)實現(xiàn)原理就是通過遞歸或者循環(huán)的方式
3. 其次要注意的是：
只有在步驟①的時候才會對初始化的數(shù)組進(jìn)行建堆线衫，而在步驟②的每次循環(huán)中只需要對堆進(jìn)行調(diào)整(adjust)就可以了，畢竟每次只是將根節(jié)點(diǎn)改變秉沼，只需要對根節(jié)點(diǎn)進(jìn)行重新調(diào)整為一個堆就好桶雀，要是還是按照步驟①那樣子建堆的話，會浪費(fèi)很多不必要的邏輯開銷唬复。
[具體的建堆和調(diào)整堆矗积，下面會慢慢講，不要著急敞咧，心急吃不了熱豆腐]
/**
* nums需要排序的堆數(shù)組
**/
public void sort(int[] nums){
//首先定義出口 當(dāng)只剩一個元素的時候 就可以出去了
if(start==(end-1)){
return;
}
//對[start,end)建堆
buildeHeap(nums);
for(int i = nums.length ; i < nums.length ; i--){
//交換 start位置和end-1位置上的值
}
swap()
sort(nums,start,end-1);
}
public void buildHeap(int [] nums){
//coding;
};
那么接下來比較重點(diǎn)的就是如何構(gòu)建一個最大堆/最小堆以及堆的調(diào)整
按照堆排序的思路完整流程走一遍：
建立堆棘捣，首先將數(shù)組直接按照水平遍歷的方式建立一個樹：[如下例]
數(shù)組int [] nums如下圖：
這個數(shù)組先建立一個完全二叉樹，如下
然后開始倒著遍歷非葉節(jié)點(diǎn)：
根據(jù)數(shù)組和樹之間的映射關(guān)系休建，不難發(fā)現(xiàn)乍恐，最后一個非葉節(jié)點(diǎn)是14那個節(jié)點(diǎn)，數(shù)數(shù)在數(shù)組中的index是不是4测砂？ 數(shù)組的長度length是不是11茵烈？
然后找規(guī)律：
不難發(fā)現(xiàn) 完全二叉樹中（完全二叉樹，看清限制條件）
非葉節(jié)點(diǎn)的個數(shù) = length/2
葉節(jié)點(diǎn)的個數(shù) = (length+1)/2
最后一個非葉節(jié)點(diǎn)在對應(yīng)數(shù)組中的index = length/2 - 1
【后來樓主試了一下砌些，前兩條性質(zhì)符合所有的二叉樹】
【樓主自認(rèn)沒啥大本事呜投，這種規(guī)律記住就好了，以后沒準(zhǔn)會用這個規(guī)律去推其他規(guī)律存璃，但是這個規(guī)律我是真的不知道咋推出來的了仑荐。。纵东。ORZ 有大神可以告知一下】
以構(gòu)建大根堆為例子：
第一個非葉節(jié)點(diǎn): 以及調(diào)整后的情形
第二個
第三個[由于滿足條件 所以不需要交換]
第四個 [換了之后發(fā)現(xiàn)粘招，5換后的位置依然不滿足要求需要再接著和下層換]
第五個 也就是最后一個：
這樣就構(gòu)造出來了一個最大堆，我們不難看出來偎球，其實堆并不是有序的洒扎，你水平遍歷一下就知道，這是無序的衰絮，因此這是一個無序堆逊笆，但是不論什么堆，只要是堆岂傲，那么他的根節(jié)點(diǎn)，絕對是一個最值(如本例是最大堆所以頂部就是一個最大值)
然后開始排序吧
首先將根元素和尾元素swap(互換一下)
如圖這樣子就相當(dāng)于排好一個元素了[20]
然后默認(rèn)從數(shù)組中刪除最后一個元素[去掉排好序的元素] [對于圖中來說不考慮藍(lán)色的節(jié)點(diǎn)]
對剩余節(jié)點(diǎn)進(jìn)行調(diào)整為堆子檀，但是我們不難發(fā)現(xiàn)镊掖，由于其他元素在構(gòu)建堆的時候已經(jīng)滿足堆的需求的了所以沒必要從最后一個非葉子節(jié)點(diǎn)處進(jìn)行重構(gòu)堆乃戈，只需要對第一個元素[5] (剛才互換的節(jié)點(diǎn)) 進(jìn)行調(diào)整使其滿足堆的性質(zhì)就會又構(gòu)建成一個堆，因此不難發(fā)現(xiàn)亩进，調(diào)整比構(gòu)建堆簡單得很症虑。
然后再把第一個元素和最后一個元素[邏輯概念上就是 19 和 5 , 20還是存在的，只不是過我剛才說過就是你就當(dāng)它不存在归薛，藍(lán)色都是不存在的谍憔，那么第一個節(jié)點(diǎn)是19 第二個節(jié)點(diǎn)是5 互換了之后如下]
這樣就相當(dāng)于排好兩個元素了，再對剩下的元素(除了藍(lán)色的節(jié)點(diǎn)) 如法炮制 -> 調(diào)整堆 -> 互換位置 -> 調(diào)整堆 -> 互換位置 ………………直到只剩一個元素為止主籍，那么也沒有調(diào)整的必要了 233333333
<font color=blue>終于講完了算法了习贫，自己也通了一遍，可以開開心心地寫代碼了</font>
擼主講的思路都這么清楚了千元，代碼就一帶而過好了苫昌，搞懂思路，代碼也就比較容易寫了幸海。
package HeapSort;
import java.util.Arrays;
import javax.xml.transform.Templates;
/**
* 主要是構(gòu)建最大堆
* 最后生成從小到大排序的序列
* 算法復(fù)雜度為O(N*logN)
* @author mengf
*
*/
public class HeapSort {
public static void main(String[] args) {
HeapSort sort = new HeapSort();
int[] nums = {12,5,17,9,14,13,2,4,19,8,20};
sort.heapSort(nums);
System.out.println(Arrays.toString(nums));
}
/**
* 構(gòu)建最大堆
* @param nums
*/
public void heapSort(int[] nums){
if (nums.length<=1) {
//數(shù)量<=1 的數(shù)組排序的意義在哪祟身？ exo me？
//你的良心不會痛么Ｎ锒馈Ｍ嗔颉！挡篓！
return;
}
buildHeap(nums);
//其實都知道調(diào)整的次數(shù)為多少的
//i 其實就是swap后剩下的節(jié)點(diǎn)的個數(shù) 也就是length
for(int i = nums.length-1 ; i >= 1 ; i--){
//System.out.println("到這里了");
//swap
swap(nums, i, 0);
//adjust
adjustHeap(nums, 0 ,i);
}
}
private void buildHeap(int[] nums) {
//創(chuàng)建最大堆
int length = nums.length;
//index = n/2 -1 ;
int index = length/2 -1 ;
//最后一個非葉節(jié)點(diǎn)的index
//調(diào)整為最大堆
for(int i = index ; i >= 0 ; i--){
adjustHeap(nums, i, length);
}
}
/**
*
* @param nums 表示這個數(shù)組
* @param i 表示想要調(diào)整的對應(yīng)的位置
* @param length 表示這個堆對應(yīng)數(shù)組的長度 注意不一定是nums的長度哦 婉陷，可能是剩余沒排好序的長度
*/
private void adjustHeap(int[] nums,int i,int length){
int left = 2 * i + 1;
int right = 2 * i + 2;
int temp = i;
int tempMax = nums[i];
while (true) {
//System.out.println(temp);
if (right < length && tempMax < nums[right]) {
tempMax = nums[right];
temp = right;
}
if (left < length && tempMax < nums[left]) {
tempMax = nums[left];
temp = left;
}
//如果最大的位置還是i的話 那就不用換了
if (temp == i) {
break;
}else {
swap(nums, temp, i);
//交換完 后 重新初始化 right left 以及默認(rèn)的位置為i 默認(rèn)最大值為nums[temp]
left = 2* temp + 1;
right = 2 * temp +2;
i = temp;
tempMax = nums[temp];
}
}
}
private void swap(int nums[], int i,int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
琢磨了好久，都去參考了一下網(wǎng)上的代碼才寫出來的瞻凤，看來還是不行憨攒，需要多練，懂了原理是一碼事情阀参，會踐行到代碼中又是一件事情肝集，看來要每天寫一發(fā)了！蛛壳！
