今天我們來介紹八大排序算法之中的最后一種，堆排序炫惩。堆排序是指利用堆積樹（堆）這種 數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法僻弹，它是選擇排序的一種。
這些概念我覺得是不用太過領(lǐng)會的他嚷，我們只需要記住幾個特點(diǎn)蹋绽，就可以實(shí)現(xiàn)堆排序了.
堆實(shí)際上是一棵完全二叉樹，其任何一非葉節(jié)點(diǎn)滿足性質(zhì)：
Key[i] <= key[2i+1] && Key[i] <= key[2i+2] 或者 Key[i] >= Key[2i+1] && key>=key[2i+2]
即任何一非葉節(jié)點(diǎn)的關(guān)鍵字不大于或者不小于其左右孩子節(jié)點(diǎn)的關(guān)鍵字筋蓖。堆分為大頂堆和小頂堆卸耘，
滿足 Key[i] >= Key[2i+1] && key >= key[2i+2] 稱為大頂堆，
滿足 Key[i] <= key[2i+1] && Key[i] <= key[2i+2] 稱為小頂堆粘咖。
由上述性質(zhì)可知大頂堆的堆頂?shù)年P(guān)鍵字肯定是所有關(guān)鍵字中最大的蚣抗，小頂堆的堆頂?shù)年P(guān)鍵字是所有關(guān)鍵字中最小的。
我們下面演示小頂堆排序的過程：
（1）從最后一個非葉子節(jié)點(diǎn)開始瓮下，每三個節(jié)點(diǎn)做一次大小比較翰铡，最小的做根，如果移動過程中如果子樹上的順序被破壞了讽坏，子樹上重新調(diào)整三個節(jié)點(diǎn)的位置锭魔。
（2）取走整個樹的根節(jié)點(diǎn)，把最后一個葉子作為根節(jié)點(diǎn)路呜。
（3）重復(fù)（1）和（2）的過程迷捧，知道樹中的所有節(jié)點(diǎn)全部被取走為止。
下面舉例說明：
給定一個整形數(shù)組a[]={6, 3, 9, 2, 4, 5, 1, 8, 7}胀葱，對其進(jìn)行堆排序漠秋。首先根據(jù)該數(shù)組元素構(gòu)建一個完全二叉樹，得到
然后我們對這棵完全二叉樹進(jìn)行堆排序過程：
上圖中是完成了一次建堆操作抵屿，從最后一個非葉子節(jié)點(diǎn)開始一直到根節(jié)點(diǎn)庆锦，完成建堆操作。
到了這里我不想繼續(xù)往下面畫了，因?yàn)榇蠹铱赡芸戳松厦婢鸵呀?jīng)知道結(jié)果了，省略了最后2張圖烙心。
自己做的圖畫的不是太好声旺，下次會改進(jìn)。從上面的圖我們可以看出它抱，小頂堆的排序過程就是每次建堆都把最小的數(shù)找到最后放在根節(jié)點(diǎn)的位置，這樣我們每次只要從根節(jié)點(diǎn)拿出數(shù)據(jù)，就可以得出排序結(jié)果了誉帅。
下面我們來看下代碼實(shí)現(xiàn)：
public static void heapSort(int[] array){
int n = array.length; //堆中元素的個數(shù)
//對整個數(shù)組建堆,從最后一個非葉子節(jié)點(diǎn)(array.length-1)/2開始建堆,一直到根節(jié)點(diǎn)
for(int i=(array.length-1)/2;i>=0;i--){
createHeap(array,n,i);
}
while (n>0){
System.out.print(array[0]+" "); //輸出根節(jié)點(diǎn)
array[0] = array[n-1]; //把最后一個節(jié)點(diǎn)放到根節(jié)點(diǎn)上
n--;
createHeap(array,n,0); //從根節(jié)點(diǎn)開始重新建堆
}
}
public static void createHeap(int[] array,int n,int k){
int kLeft = 2*k + 1; //k的左孩子的下標(biāo)
int kRight = 2*k + 2; //k的右孩子的下標(biāo)
if(kLeft>=n && kRight>=n){ //如果兩個下標(biāo)都越界，表示沒有左右孩子
return;
}
int kLeftValue = Integer.MAX_VALUE; //如果是最大值右莱，代表沒有左孩子
int kRightValue = Integer.MAX_VALUE;
if(kLeft<n){
kLeftValue = array[kLeft];
}
if(kRight<n){
kRightValue = array[kRight];
}
//對三個節(jié)點(diǎn)比較大小
if(array[k]<kLeftValue && array[k]<kRightValue){ //如果左右孩子都比k小蚜锨，則不用建堆，直接返回
return;
}
if(kLeftValue < kRightValue){ //如果左孩子比右孩子小慢蜓，就用左孩子和k交換
int temp = array[k];
array[k] = array[kLeft];
array[kLeft] = temp;
createHeap(array,n,kLeft); //為了防止交換數(shù)字后破壞樹中的堆結(jié)構(gòu)亚再，必須要重新建堆
}else{
int temp = array[k];
array[k] = array[kRight];
array[kRight] = temp;
createHeap(array,n,kRight);
}
}
堆排序的應(yīng)用：當(dāng)數(shù)據(jù)為無序或鏈?zhǔn)浇Y(jié)構(gòu)的時候進(jìn)行二分查找。一般不用來排序晨抡，安卓代碼用不到氛悬，使用在大數(shù)據(jù)的查找，一般寫在后臺, 雖然不常用但是我們還是應(yīng)該了解一下的耘柱。
到了這里八大排序我們就基本講完了如捅，這也是對我學(xué)習(xí)過程的一個總結(jié)，如果有哪里寫錯了调煎，請大家指點(diǎn)镜遣。
