本來還想寫點思路的，詞窮，不知道怎么組織，算了。只有貼源代碼了。希望以后的我不要怪我哦！還可以看書嘛。書上講的已經(jīng)很清楚了哦。呵呵。
由于是學習，所以只寫了最大堆，也沒有怎么優(yōu)化和詳細的測試。哎，無奈的貼上源代碼：
#include <stdio.h>
#include <stdlib.h>
//交換兩個整數(shù)。注意一定要if判斷是否兩個相等，如果
//不相等才交換，如果相等也交換會出錯的。a^a = 0
inline void Swap(int& a, int& b)
{
if (a != b)
{
a^= b;
b^= a;
a^= b;
}
}
//維持一個最大堆
int Heapify(int* npData, int nPos, int nLen)
{
int nMax = -1; //暫存最大值
int nChild = nPos * 2; //他的左孩子位置
while(nChild <= nLen) //判斷他是否有孩子
{
nMax = npData[nPos]; //是當前最大值為他
if (nMax < npData[nChild]) //與左孩子比較
{
nMax = npData[nChild]; //如果比左孩子小，就時最大值為左孩子
}
//同理與右孩子比較，這里要注意，必須要保證有右孩子。
if (nChild + 1 <= nLen && nMax < npData[nChild + 1])
{
++nChild; //賦值最大值的時候把孩子變?yōu)橛液⒆樱奖阕詈蟮臄?shù)據(jù)交換
nMax = npData[nChild];
}
if (nMax != npData[nPos]) //判斷是否該節(jié)點比孩子都打，如果不大
{
Swap(npData[nPos], npData[nChild]); //與最大孩子交換數(shù)據(jù)
nPos = nChild; //該節(jié)點位置變?yōu)榻粨Q孩子的位置
nChild *= 2; //因為只有交換后才使不滿足堆得性質(zhì)。
}
else //都最大了，滿足堆得性質(zhì)了。退出循環(huán)
{
break;
}
}
return 1; //維持結束。
}
//建立一個堆
int BuildHeap(int* npData, int nLen)
{
//從nLen / 2最后一個有葉子的數(shù)據(jù)開始，逐一的插入堆，并維持堆得平衡。
//因為堆是一個完全二叉樹，所以nlen/2+1- nLen之間肯定都是葉子。
//葉子還判斷什么呢。只有一個數(shù)據(jù)，肯定滿足堆得性質(zhì)咯。
for (int i = nLen / 2; i >= 1; --i)
{
Heapify(npData, i, nLen);
}
return 1;
}
//堆排序
int HeapSort(int* npData, int nLen)
{
BuildHeap(npData, nLen); //建立一個堆。
while(nLen >= 1) //逐一交和第一個元素交換數(shù)據(jù)到最后
{ //完成排序
Swap(npData[nLen], npData[1]);
--nLen;
Heapify(npData, 1, nLen);//交換之后一定要維持一下堆得性質(zhì)。
} //不然小的成第一個元素,就不是堆了。
return 1;
}
//main函數(shù)，
int main()
{
int nData[11] = {0,9,8,7,6,5,4,3,2,1,0}; //測試數(shù)據(jù)，下標從1開始哦。
HeapSort(nData, 10); //堆排序
for (int i = 1; i <= 10; ++i) //輸出排序結果。
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}
呵呵，等知道怎么寫思路了補上。。