1. 堆排序介紹：

• 堆排序是利用“堆”這種數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的，也是一種選擇排序，時(shí)間復(fù)雜度為O(nlogn)，屬于不穩(wěn)定排序。
• 堆，其實(shí)就是具有某些特征的完全二叉樹。特點(diǎn)就是：每個(gè)節(jié)點(diǎn)的值都大于其左右孩子節(jié)點(diǎn)的值，這樣的叫大頂堆；反之叫小頂堆。

如果我們以圖中黑色數(shù)字作為索引將值依次存到數(shù)組里，那么數(shù)組就是：

50, 45, 40, 20, 26, 35, 30, 10, 15

可以發(fā)現(xiàn)，arr[i] > arr[2*i + 1]，arr[i] > arr[2*i + 2]。

在用堆排序的時(shí)候，如果要升序，那就使用大頂堆，如果要降序，那就使用小頂堆?！ぁ?/p>

2. 排序思想：

• 將待排序列構(gòu)造成一個(gè)最大堆。不需要真正地構(gòu)建二叉樹，之前說(shuō)了二叉樹的順序存儲(chǔ)，這里就派上用場(chǎng)了；

• 此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)；

• 將堆頂元素與末尾元素進(jìn)行交換，此時(shí)末尾元素就是最大值；

• 將剩余的(n - 1)個(gè)元素，重新構(gòu)造成一個(gè)堆，如此反復(fù)執(zhí)行……

3. 代碼實(shí)現(xiàn)：

首先寫個(gè)方法，將樹調(diào)整成大頂堆，具體步驟看代碼注釋：

/**
* 把以index為父節(jié)點(diǎn)的子樹調(diào)整成大頂堆
* @param arr 數(shù)組
* @param index 非葉子節(jié)點(diǎn)的索引
* @param length 對(duì)多少個(gè)元素進(jìn)行調(diào)整
*/
private static void buildHeap(int[] arr, int index, int length) {
 // 保存index對(duì)應(yīng)的值，其實(shí)就是要調(diào)整子樹的父節(jié)點(diǎn)的值
 int temp = arr[index];
 // 開始調(diào)整，i就是index節(jié)點(diǎn)的左子節(jié)點(diǎn)
 for (int i=(index * 2 + 1); i<length; i = (i * 2 + 1)) {
  // 如果左子節(jié)點(diǎn)小于右子節(jié)點(diǎn)，那就讓i指到右子節(jié)點(diǎn)
  if (i + 1 < length && arr[i] < arr[i+1]) {
   i++;
  }
  // 經(jīng)過(guò)上面操作，arr[i]就是最大的子節(jié)點(diǎn)
  if (arr[i] > temp) {
   // 如果最大子節(jié)點(diǎn)的值比父節(jié)點(diǎn)更大，就把這個(gè)子節(jié)點(diǎn)的值賦給父節(jié)點(diǎn)
   arr[index] = arr[i];
   // 然后就以剛才那個(gè)最大子節(jié)點(diǎn)為父節(jié)點(diǎn)，再循環(huán)進(jìn)行調(diào)整
   index = i;
  } else {
   break;
  }
 }
 // 循環(huán)結(jié)束，就是調(diào)整結(jié)束，要把剛才保存的父節(jié)點(diǎn)的值賦給當(dāng)前節(jié)點(diǎn)，這才完成了父節(jié)點(diǎn)與子節(jié)點(diǎn)值的交換
 arr[index] = temp;
}

然后就可以寫排序方法了，首先調(diào)用一次調(diào)整大頂堆的方法，然后將堆頂元素放到最后，此時(shí)最后那個(gè)元素就是最大的了，然后再進(jìn)行調(diào)整，就可以少調(diào)整一個(gè)數(shù)了，具體代碼如下：

public static void sort(int[] arr) {
 // 遍歷數(shù)組，找到非葉子節(jié)點(diǎn)，對(duì)以非葉子節(jié)點(diǎn)為父節(jié)點(diǎn)的子樹進(jìn)行調(diào)整
 // (arr.length / 2 - 1)就可以找到完全二叉樹的最后一個(gè)非葉子節(jié)點(diǎn)
 for(int i=(arr.length / 2 - 1); i>=0; i--) {
  buildHeap(arr, i, arr.length);
 }
 // 調(diào)整成大頂堆后，讓堆頂元素與末尾元素進(jìn)行交換，此時(shí)末尾元素就是最大值
 int temp;
 for(int j=arr.length-1; j>0; j--) {
  temp = arr[j];
  arr[j] = arr[0];
  arr[0] = temp;
  // 交換完后，將剩余的(n-1)個(gè)元素再調(diào)整成大頂堆
  buildHeap(arr, 0, j);
 }
}