算法簡介：
堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為(nlogn)，它也是不穩(wěn)定排序，首先了解一下堆
堆
堆是具有以下性質(zhì)的完全二叉樹：每個節(jié)點的值都大于或等于其左右孩子節(jié)點的值，稱為大頂堆；或者每個節(jié)點的值都小于或等于其左右孩子節(jié)點的值，稱為小頂堆。如圖：
同時，我們對堆中的節(jié)點按層進行編號，將這種邏輯結(jié)構(gòu)映射到數(shù)組中就是下面這個樣子
接下來，我們來看看堆排序的基本思想及實現(xiàn)步驟：
堆排序的基本思想及實現(xiàn)步驟
堆排序的基本思想是：將待排序序列構(gòu)造成一個大頂堆，此時，整個序列的最大值就是堆頂?shù)母?jié)點。將其與末尾元素進行交換，此時末尾元素成為最大值。然后將剩余n-1個元素重新構(gòu)造成一個大頂堆，這樣會得到n個元素的次小值，此時根節(jié)點又會成為次小值中的最大值，再重復以上步驟，最終便會得到一個有序序列了。
步驟一 構(gòu)造初始大頂堆(升序用大頂堆，降序小頂堆)
上圖：
1.假定給定無序序列結(jié)構(gòu)如下
2.此時我們從最后一個非葉子節(jié)點(6)開始，從左至右，從下至上進行調(diào)整
3.找到第二個非葉子節(jié)點4，由于(4,9,8)中9最大，4和9進行交換。
這時，交換導致了子根(4,5,6)結(jié)構(gòu)的混亂，繼續(xù)調(diào)整，(4,5,6)中6最大。交換4和6.
此時，我們就將一個無序序列構(gòu)造成了一個大頂堆。
步驟二 將堆頂元素與末尾元素進行交換，使末尾元素最大。然后繼續(xù)調(diào)整堆（此時調(diào)整的堆元素長度為n-1,與大頂堆根元素交換過的位置在下一次調(diào)整排除）然后繼續(xù)調(diào)整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復進行交換、重建、交換。
上圖：
1.將堆頂元素9和末尾元素4交換：
2.重新調(diào)整結(jié)構(gòu)，使剩下的n-1個元素繼續(xù)成為大頂堆
3.再將堆頂元素8和末尾元素5進行交換，得到第二大元素8
后續(xù)過程，進行重復以上步驟，最終使得整個序列有序
對堆排序的基本思路的簡單總結(jié)：
a.將無序序列構(gòu)建成一個堆，根據(jù)升序降序需求選擇大頂堆還是小頂堆;
b.將堆頂元素與末尾元素進行交換，將最大(最小)元素“沉”到數(shù)組末端；
c.重新調(diào)整剩余的n-1（n-2,n-3....1）個結(jié)構(gòu)，使其滿足堆定義，然后繼續(xù)交換堆頂元素和當前末尾元素，反復執(zhí)行調(diào)整+交換步驟，直到整個序列有序。
代碼實現(xiàn)：
public class Duition{
public static void sort(int[] arr){
int len = arr.length - 1;
for(int i = len/2-1;i>=0;i--){
//構(gòu)造大頂堆
headAdjust(arr,i,len);
}
//交換根元素后再進行堆調(diào)整
while(len>=0){
swap(arr,0,len--);
headAdjust(arr,0,len);
}
}
//交換指定元素
public static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//構(gòu)造大頂堆
public static void headAdjust(int[] arr,int i,int len){
int left; //左孩子
int right; //右孩子
int j;
while((left = i*2+1)<=len){
right = left +1;
j = left;
//比較左右孩子，將其中較大者的位置賦予j
if(j<len && arr[left] < arr[right]){
j++;
}
//比較根節(jié)點和較大孩子的值
if(arr[i] < arr[j])
swap(arr,i,j);
else
breadk;
i = j; //下一個根節(jié)點，為下一次循環(huán)做準備
}
}
}
其中 len/2-1是表示數(shù)組元素按曾編號之后非葉子節(jié)點的下標范圍，在len/2-1之后的元素都是葉子節(jié)點(即沒有左右孩子)，這是完全二叉樹的規(guī)律。
注：以上算法思想及圖源自圖解排序算法(三)之堆排序，代碼已測試，沒發(fā)現(xiàn)什么問題，做個記錄，以便日后查詢。
