1.復雜度與穩(wěn)定性

算法時間復雜度

最壞情況：O(n^2)

最好情況：O(n)

平均情況：O(nlogn)

穩(wěn)定性：不穩(wěn)定排序

2. 什么是堆？

堆排序是一個比較特殊的排序方式，在學習之前我們必須要了解什么是堆

堆是一種非線性的數(shù)據(jù)結構，可以把堆看作一個數(shù)組，也可以被看作一個完全二叉樹，通俗來講堆其實就是利用完全二叉樹的結構來維護的一維數(shù)組

按照堆的特點可以把堆分為大頂堆和小頂堆

a)大頂堆：每個結點的值都大于或等于其左右孩子結點的值

b)小頂堆：每個結點的值都小于或等于其左右孩子結點的值

這種特性與我們在前面學習查找方法時學過的二叉排序樹很相似，這種特殊的數(shù)據(jù)結構可以讓我們快速訪問到我們需要的值，如優(yōu)先隊列就使用堆進行處理。

PS:我們這里提到的堆這個概念與編譯器概念堆棧需要區(qū)分。

3.過程介紹

基本思想：把待排序的元素按照大小在二叉樹位置上排列（使用數(shù)組模擬，沒必要一定使用二叉樹），排序好的元素要滿足：父節(jié)點的元素要大于等于其子節(jié)點；這個過程叫做堆化過程，如果根節(jié)點存放的是最大的數(shù)，則叫做大根堆；如果是最小的數(shù)，自然就叫做小根堆了。根據(jù)這個特性（大根堆根最大，小根堆根最?。?，就可以把根節(jié)點拿出來，然后再堆化下，再把根節(jié)點拿出來，一直循環(huán)到最后一個節(jié)點，就排序好了。

基本步驟：

其實整個排序主要核心就是堆化過程，堆化過程一般是用父節(jié)點和他的孩子節(jié)點進行比較，取最大的孩子節(jié)點和其進行交換；但是要注意這應該是個逆序的，先排序好子樹的順序，然后再一步步往上，到排序根節(jié)點上。然后又相反（因為根節(jié)點也可能是很小的）的，從根節(jié)點往子樹上排序。最后才能把所有元素排序好

4. 相關的代碼

請慢慢理解堆排序這一特殊的排序算法，在排序循環(huán)中逐步運算出數(shù)據(jù)。

#include <stdio.h>
 
/* Function: 交換交換根節(jié)點和數(shù)組末尾元素的值*/
void Swap(int *heap, int len) {
    int temp;
 
    temp = heap[0];
    heap[0] = heap[len-1];
    heap[len-1] = temp;
}
 
/* Function: 構建大頂堆 */
void BuildMaxHeap(int *heap, int len) {
    int i,temp;
    for (i = len/2-1; i >= 0; i--) {
        if ((2*i+1) < len && heap[i] < heap[2*i+1]) {  /* 根節(jié)點大于左子樹 */
            temp = heap[i];
            heap[i] = heap[2*i+1];
            heap[2*i+1] = temp;
            /* 檢查交換后的左子樹是否滿足大頂堆性質 如果不滿足 則重新調(diào)整子樹結構 */
            if ((2*(2*i+1)+1 < len && heap[2*i+1] < heap[2*(2*i+1)+1]) || (2*(2*i+1)+2 < len && heap[2*i+1] < heap[2*(2*i+1)+2])) {
                BuildMaxHeap(heap, len);
            }
        }
        if ((2*i+2) < len && heap[i] < heap[2*i+2]) {  /* 根節(jié)點大于右子樹 */
            temp = heap[i];
            heap[i] = heap[2*i+2];
            heap[2*i+2] = temp;
            /* 檢查交換后的右子樹是否滿足大頂堆性質 如果不滿足 則重新調(diào)整子樹結構 */
            if ((2*(2*i+2)+1 < len && heap[2*i+2] < heap[2*(2*i+2)+1]) || (2*(2*i+2)+2 < len && heap[2*i+2] < heap[2*(2*i+2)+2])) {
                BuildMaxHeap(heap, len);
            }
        }
    }
}
 
int main() {
    int a[8]= {70,50,30,20,10,70,40,60};
    int n=8;
    int i;
 
    for (i = n; i > 0; i--) {
        BuildMaxHeap(a, i);
        Swap(a, i);
    }
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
 
    return 0;
}