堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進癣亚。
基本思想：
堆頂元素（即第一個元素）必為最小項（小頂堆）或最大項（大頂堆）颤霎。若以一維數(shù)組存儲一個堆，則堆對應(yīng)一棵完全二叉樹党饮，且所有非葉結(jié)點的值均不大于(或不小于)其子女的值摩泪，根結(jié)點（堆頂元素）的值是最小(或最大)的。
初始時把要排序的n個數(shù)的序列看作是一棵順序存儲的二叉樹（一維數(shù)組存儲二叉樹）劫谅，調(diào)整它們的存儲序见坑，使之成為一個堆，將堆頂元素輸出捏检，得到n個元素中最大(或最小)的元素荞驴，這時堆的根節(jié)點的數(shù)最大（或最小）贯城。然后對前面(n-1)個元素重新調(diào)整使之成為堆熊楼，輸出堆頂元素，得到n個元素中次大(或次小)的元素能犯。依此類推鲫骗，直到只有兩個節(jié)點的堆，并對它們作交換踩晶，最后得到有n個節(jié)點的有序序列执泰。稱這個過程為堆排序。
因此渡蜻，實現(xiàn)堆排序需解決兩個問題：
如何將n個待排序的數(shù)建成堆术吝。
輸出堆頂元素后计济，怎樣調(diào)整剩余 n-1 個元素，使其成為一個新堆排苍。
首先討論第二個問題：
輸出堆頂元素后沦寂，對剩余 n-1 元素重新建成堆的調(diào)整過程（調(diào)整大頂堆的方法）：
1）設(shè)有 n 個元素的堆，輸出堆頂元素后淘衙，剩下 n-1 個元素传藏。將堆底元素送入堆頂（（最后一個元素與堆頂進行交換），堆被破壞彤守，其原因僅是根結(jié)點不滿足堆的性質(zhì)毯侦。
2）將根結(jié)點與左、右子樹中較大元素的進行交換遗增。
3）若與左子樹交換：如果左子樹堆被破壞叫惊，即左子樹的根結(jié)點不滿足堆的性質(zhì)，則重復(fù)方法 （2）.
4）若與右子樹交換做修，如果右子樹堆被破壞霍狰，即右子樹的根結(jié)點不滿足堆的性質(zhì)。則重復(fù)方法 （2）.
5）繼續(xù)對不滿足堆性質(zhì)的子樹進行上述交換操作饰及，直到葉子結(jié)點蔗坯，堆被建成。
稱這個自根結(jié)點到葉子結(jié)點的調(diào)整過程為篩選燎含。
再討論對 n 元素初始建堆的過程宾濒。
建堆方法：對初始序列建堆的過程，就是一個反復(fù)進行篩選的過程屏箍。
1）n 個結(jié)點的完全二叉樹仓坞，則最后一個結(jié)點是第 n/2 個結(jié)點的子樹捶枢。
2）篩選從第 n/2 個結(jié)點為根的子樹開始实幕，該子樹成為堆空厌。
3）之后向前依次對各結(jié)點為根的子樹進行篩選，使之成為堆颖御，直到根結(jié)點榄棵。
算法的實現(xiàn)：
從算法描述來看，堆排序需要兩個過程潘拱，一是建立堆疹鳄，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數(shù)組成芦岂。一是建堆的滲透函數(shù)瘪弓，二是反復(fù)調(diào)用滲透函數(shù)實現(xiàn)排序的函數(shù)。
// 輸出數(shù)組內(nèi)容
void print(int array[], int length, int i) {
printf("i=%d:",i);
for (int j = 0; j < length; j++) {
printf(" %d ", array[j]);
}
printf("\n");
}
/**
* 已知 H[s...m] 除了 H[s] 外均滿足堆的定義
* 調(diào)整 H[s] 使其成為大頂堆盔腔，即將對第 s 個結(jié)點為根的子樹篩選
*
* @param H 是待調(diào)整的堆數(shù)組
* @param s 是待調(diào)整的數(shù)組元素的位置
* @param length 是數(shù)組的長度
*/
void HeapAdjust(int H[], int s, int length) {
int temp = H[s];
int child = 2*s + 1; // 左孩子結(jié)點的位置
while (child < length) {
if (child + 1 < length && H[child] < H[child+1]) {
// 如果右孩子大于左孩子（找到比當(dāng)前待調(diào)整結(jié)點大的孩子結(jié)點）
++ child;
}
if (H[s] < H[child]) { // 如果較大的子結(jié)點大于父結(jié)點
H[s] = H[child]; // 那么把較大的子結(jié)點往上移杠茬，替換它的父結(jié)點
s = child; // 重新設(shè)置 s月褥，即待調(diào)整的下一個結(jié)點的位置
child = 2*s + 1;
} else {
// 如果當(dāng)前待調(diào)整結(jié)點大于它的左右孩子弛随，則不需要調(diào)整瓢喉，直接退出
break;
}
H[s] = temp; // 當(dāng)前待調(diào)整的結(jié)點放到比其大的孩子結(jié)點位置上
}
print(H, length, s);
}
/**
* 初始堆進行調(diào)整
* 將 H[0...length-1]建成堆
* 調(diào)整完之后第一個元素是序列的最小值
*/
void BuildingHeap(int H[], int length) {
// 最后一個有孩子的節(jié)點的位置 i = (length - 1) / 2
for (int i = (length -1) / 2; i >= 0; i --) {
HeapAdjust(H, i, length);
}
}
/**
* 堆排序算法
*/
void HeapSort(int H[], int length) {
// 初始堆
BuildingHeap(H, length);
// 從最后一個元素開始對序列進行調(diào)整
for (int i = length - 1; i > 0; i --) {
// 交換堆頂元素 H[0] 和堆中最后一個元素
int temp = H[i];
H[i] = H[0];
H[0] = temp;
// 每次交換堆頂元素和堆中最后一個元素之后，都要對堆進行調(diào)整
HeapAdjust(H, 0, i);
}
}
int main(int argc, const char * argv[]) {
int arrayHeapSort[8] = { 49,38,65,97,76,13,27,49 };
HeapSort(arrayHeapSort, 8);
print(arrayHeapSort, 8, 0);
printf("\n");
return 0;
}
總結(jié)
堆排序最壞情況下舀透，時間復(fù)雜度也為：O(nlogn )栓票。
