堆的概念
在介紹堆排序之前，首先需要說明一下，堆是個什麼玩意兒。
堆是一棵順序存儲的完全二叉樹。
其中每個結點的關鍵字都不大于其孩子結點的關鍵字，這樣的堆稱為小根堆。
其中每個結點的關鍵字都不小于其孩子結點的關鍵字，這樣的堆稱為大根堆。
舉例來說，對于n個元素的序列{R0, R1, ... , Rn}當且僅當滿足下列關系之一時，稱之為堆：
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整;
如上圖所示，序列R{3, 8, 15, 31, 25}是一個典型的小根堆。
堆中有兩個父結點，元素3和元素8。
元素3在數組中以R[0]表示，它的左孩子結點是R[1]，右孩子結點是R[2]。
元素8在數組中以R[1]表示，它的左孩子結點是R[3]，右孩子結點是R[4]，它的父結點是R[0]。可以看出，它們滿足以下規律：
設目前元素在數組中以R[i]表示，那麼，
(1) 它的左孩子結點是：R[2*i+1];
(2) 它的右孩子結點是：R[2*i+2];
(3) 它的父結點是：R[(i-1)/2];
(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。
要點
首先，按堆的定義将數組R[0..n]調整為堆（這個過程稱為建立初始堆），交換R[0]和R[n]；
然後，将R[0..n-1]調整為堆，交換R[0]和R[n-1]；
如此反複，直到交換了R[0]和R[1]為止。
以上思想可歸納為兩個操作：
（1）根據初始數組去構造初始堆（建構一個完全二叉樹，保證所有的父結點都比它的孩子結點數值大）。
（2）每次交換第一個和最後一個元素，輸出最後一個元素（最大值），然後把剩下元素重新調整為大根堆。
當輸出完最後一個元素後，這個數組已經是按照從小到大的順序排列了。
先通過詳細的執行個體圖來看一下，如何建構初始堆。
設有一個無序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。
構造了初始堆後，我們來看一下完整的堆排序處理：
還是針對前面提到的無序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 來加以說明。
相信，通過以上兩幅圖，應該能很直覺的示範堆排序的操作處理。
核心代碼
public void HeapAdjust(int[] array, int parent, int length) {
int temp = array[parent]; // temp儲存目前父節點
int child = 2 * parent + 1; // 先獲得左孩子
while (child < length) {
// 如果有右孩子結點，并且右孩子結點的值大于左孩子結點，則選取右孩子結點
if (child + 1 < length && array[child] < array[child + 1]) {
child++;
}
// 如果父結點的值已經大于孩子結點的值，則直接結束
if (temp >= array[child])
break;
// 把孩子結點的值賦給父結點
array[parent] = array[child];
// 選取孩子結點的左孩子結點,繼續向下篩選
parent = child;
child = 2 * child + 1;
}
array[parent] = temp;
}
public void heapSort(int[] list) {
// 循環建立初始堆
for (int i = list.length / 2; i >= 0; i--) {
HeapAdjust(list, i, list.length);
// 進行n-1次循環，完成排序
for (int i = list.length - 1; i > 0; i--) {
// 最後一個元素和第一進制素進行交換
int temp = list[i];
list[i] = list[0];
list[0] = temp;
// 篩選 R[0] 結點，得到i-1個結點的堆
HeapAdjust(list, 0, i);
System.out.format("第 %d 趟: \t", list.length - i);
printPart(list, 0, list.length - 1);
算法分析
堆排序算法的總體情況
| 排序類别 | 排序方法 | 時間複雜度 | 空間複雜度 | 穩定性 | 複雜性 | ||
| 平均情況 | 最壞情況 | 最好情況 | |||||
| 選擇排序 | 堆排序 | O(nlog2n) | O(1) | 不穩定 | 較複雜 |
堆的存儲表示是順序的。因為堆所對應的二叉樹為完全二叉樹，而完全二叉樹通常采用順序存儲方式。
當想得到一個序列中第k個最小的元素之前的部分排序序列，最好采用堆排序。
因為堆排序的時間複雜度是O(n+klog2n)，若k≤n/log2n，則可得到的時間複雜度為O(n)。
算法穩定性
堆排序是一種不穩定的排序方法。
因為在堆的調整過程中，關鍵字進行比較和交換所走的是該結點到葉子結點的一條路徑，
是以對于相同的關鍵字就可能出現排在後面的關鍵字被交換到前面來的情況。
完整參考代碼
JAVA版本
代碼實作
以下範例是對上文提到的無序序列 {
1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 進行排序。
public class HeapSort {
public void HeapAdjust(int[] array, int parent, int length) {
int temp = array[parent]; // temp儲存目前父節點
int child = 2 * parent + 1; // 先獲得左孩子
while (child < length) {
// 如果有右孩子結點，并且右孩子結點的值大于左孩子結點，則選取右孩子結點
if (child + 1 < length && array[child] < array[child + 1]) {
child++;
}
// 如果父結點的值已經大于孩子結點的值，則直接結束
if (temp >= array[child])
break;
// 把孩子結點的值賦給父結點
array[parent] = array[child];
// 選取孩子結點的左孩子結點,繼續向下篩選
parent = child;
child = 2 * child + 1;
}
array[parent] = temp;
}
public void heapSort(int[] list) {
// 循環建立初始堆
for (int i = list.length / 2; i >= 0; i--) {
HeapAdjust(list, i, list.length);
}
// 進行n-1次循環，完成排序
for (int i = list.length - 1; i > 0; i--) {
// 最後一個元素和第一進制素進行交換
int temp = list[i];
list[i] = list[0];
list[0] = temp;
// 篩選 R[0] 結點，得到i-1個結點的堆
HeapAdjust(list, 0, i);
System.out.format("第 %d 趟: \t", list.length - i);
printPart(list, 0, list.length - 1);
}
}
// 列印序列
public void printPart(int[] list, int begin, int end) {
for (int i = 0; i < begin; i++) {
System.out.print("\t");
}
for (int i = begin; i <= end; i++) {
System.out.print(list[i] + "\t");
}
System.out.println();
}
public static void main(String[] args) {
// 初始化一個序列
int[] array = {
1, 3, 4, 5, 2, 6, 9, 7, 8, 0
};
// 調用快速排序方法
HeapSort heap = new HeapSort();
System.out.print("排序前:\t");
heap.printPart(array, 0, array.length - 1);
heap.heapSort(array);
System.out.print("排序後:\t");
heap.printPart(array, 0, array.length - 1);
}
} 運作結果
排序前: 1 3 4 5 2 6 9 7 8 0
第 1 趟: 8 7 6 5 2 1 4 3 0 9
第 2 趟: 7 5 6 3 2 1 4 0 8 9
第 3 趟: 6 5 4 3 2 1 0 7 8 9
第 4 趟: 5 3 4 0 2 1 6 7 8 9
第 5 趟: 4 3 1 0 2 5 6 7 8 9
第 6 趟: 3 2 1 0 4 5 6 7 8 9
第 7 趟: 2 0 1 3 4 5 6 7 8 9
第 8 趟: 1 0 2 3 4 5 6 7 8 9
第 9 趟: 0 1 2 3 4 5 6 7 8 9
排序後: 0 1 2 3 4 5 6 7 8 9
參考資料
《資料結構習題與解析》（B級第3版）
相關閱讀
歡迎閱讀
程式員的内功——算法系列
示例源碼：https://github.com/dunwu/algorithm-notes
說明
感謝 @
放學路上的國小生的指正，他提到的第一種修改方法是有效的。本文已修改。
在我的 github 中，提供了單元測試來進行排序驗證：
樣本包含：數組個數為奇數、偶數的情況；元素重複或不重複的情況。且樣本均為随機樣本，實測有效。
https://github.com/dunwu/algorithm-notes/blob/master/codes/src/test/java/io/github/dunwu/algorithm/sort/SortStrategyTest.java![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)