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