一：定義
作為選擇排序的改進(jìn)版，堆排序可以把每一趟元素的比較結(jié)果保存下來，以便我們在選擇最小/大元素時對已經(jīng)比較過的元素做出相應(yīng)的調(diào)整。
二：堆排序算法
作為選擇排序的改進(jìn)版，堆排序可以把每一趟元素的比較結(jié)果保存下來，以便我們在選擇最小/大元素時對已經(jīng)比較過的元素做出相應(yīng)的調(diào)整。
堆排序是一種樹形選擇排序，在排序過程中可以把元素看成是一顆完全二叉樹，每個節(jié)點都大（小）于它的兩個子節(jié)點，當(dāng)每個節(jié)點都大于等于它的兩個子節(jié)點時，就稱為大頂堆，也叫堆有序； 當(dāng)每個節(jié)點都小于等于它的兩個子節(jié)點時，就稱為小頂堆。
下面是我們要保存在數(shù)組中的堆的形式
二：堆排序算法
1.將長度為n的待排序的數(shù)組進(jìn)行堆有序化構(gòu)造成一個大頂堆 2.將根節(jié)點與尾節(jié)點交換并輸出此時的尾節(jié)點 3.將剩余的n -1個節(jié)點重新進(jìn)行堆有序化 4.重復(fù)步驟2，步驟3直至構(gòu)造成一個有序序列
三：圖解演示，構(gòu)造堆（大頂堆）
{5, 2, 6, 0, 3, 9, 1, 7, 4, 8}
在構(gòu)造有序堆時，我們開始只需要掃描一半的元素（n/2-1 ~ 0）即可，為什么?
因為(n/2-1)~0的節(jié)點才有子節(jié)點，如圖1，n=8,(n/2-1) = 3 即3 2 1 0這個四個節(jié)點才有子節(jié)點
第一次找到[n/2]處，進(jìn)行構(gòu)造：
我們比較父節(jié)點，左右孩子結(jié)點的大小，將最大的作為堆頂
第二次，我們對上次找到位置-1即可，找到結(jié)點0，對其左右孩子比較，構(gòu)造這三個結(jié)點的最大堆
第三次，我們找到結(jié)點6，要對其進(jìn)行構(gòu)造，結(jié)果如下
第四次（重點），我們不止要構(gòu)造雙親和左右孩子，我們還要比較其孩子結(jié)點為根的堆是否正確，不然我們需要進(jìn)行調(diào)整
我們發(fā)現(xiàn)將8,7,2三個結(jié)點變?yōu)榱俗畲蠖眩瞧渲?,3子樹不再是一個最大堆，我們需要對其修改
第五次：選取結(jié)點9進(jìn)行構(gòu)造
發(fā)現(xiàn)以結(jié)點5為根的子樹不是最大堆，我們需要進(jìn)行調(diào)整
完成最大堆的構(gòu)建
四：圖解演示：堆排序（堆存儲在數(shù)組中）
第一步：將最大值和最后的一個元素交換
第二步：將剩余的結(jié)點再次進(jìn)行堆構(gòu)造
第三步：參照第一步
按照上面循環(huán)，最終結(jié)果為
五：代碼實現(xiàn)
void swap(int K[], int i, int j)
{
int temp = K[i];
K[i] = K[j];
K[j] = temp;
}
//大頂堆的構(gòu)造，傳入的i是父節(jié)點
void HeapAdjust(int k[],int p,int n)
{
int i,temp;
temp = k[p];
for (i = 2 * p; i <= n;i*=2) //逐漸去找左右孩子結(jié)點
{
//找到兩個孩子結(jié)點中最大的
if (i < n&&k[i] < k[i + 1])
i++;
//父節(jié)點和孩子最大的進(jìn)行判斷，調(diào)整，變?yōu)樽畲蠖? if (temp >= k[i])
break;
//將父節(jié)點數(shù)據(jù)變?yōu)樽畲蟮模瑢⒃瓉淼臄?shù)據(jù)還是放在temp中，
k[p] = k[i]; //若是孩子結(jié)點的數(shù)據(jù)更大，我們會將數(shù)據(jù)上移，為他插入的點提供位置
p = i;
}
//當(dāng)我們在for循環(huán)中找到了p子樹中，滿足條件的點，我們就加入數(shù)據(jù)到該點p,注意：p點原來數(shù)據(jù)已經(jīng)被上移動了
//若沒有找到，就是相當(dāng)于對其值不變
//插入
k[p] = temp;
}
//大頂堆排序
void HeapSort(int k[], int n)
{
int i;
//首先將無序數(shù)列轉(zhuǎn)換為大頂堆
for (i = n / 2; i > 0;i--) //注意由于是完全二叉樹，所以我們從一半向前構(gòu)造，傳入父節(jié)點
HeapAdjust(k, i, n);
//上面大頂堆已經(jīng)構(gòu)造完成，我們現(xiàn)在需要排序，每次將最大的元素放入最后
//然后將剩余元素重新構(gòu)造大頂堆，將最大元素放在剩余最后
for (i = n; i >1;i--)
{
swap(k, 1, i);
HeapAdjust(k, 1, i - 1);
}
}
int main()
{
int i;
int a[11] = {-1, 5, 2, 6, 0, 3, 9, 1, 7, 4, 8 };
HeapSort(a, 10);
for (i = 1; i <= 10; i++)
printf("%d ", a[i]);
system("pause");
return 0;
}
六：性能分析
運行時間主要消耗在構(gòu)造堆和重建堆時的反復(fù)篩選上。 構(gòu)造堆的時間復(fù)雜度為O(n) 重建堆時時間復(fù)雜度為O(nlogn)。 所以總體就是O(nlogn)。 不適合排序序列個數(shù)較少的情況
