排序算法――堆排序
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-07-02 08:28:20 閱讀次數(shù)：2649次
關(guān)于堆排序的1些基本定義可參見(jiàn)我轉(zhuǎn)載的另外一篇博文。http://blog.csdn.net/u010275850/article/details/45311661
其實(shí)在學(xué)習(xí)堆的時(shí)候仔細(xì)的同學(xué)就能夠發(fā)現(xiàn)，只要順次保存刪除操作的數(shù)據(jù)，就能夠得到1個(gè)有序的序列。堆排序也是利用了這樣的思想。
算法實(shí)現(xiàn)：
/*根據(jù)最大堆實(shí)現(xiàn)的堆排序*/
#include<stdio.h>
#define LeftChild(i) (2*i+1)
void PercDown(int *data,int i,int n);
void Heapsort(int *data,int n);
void Swap(int *a,int *b);
int main()
{
int i=0;
int data[7]={97,53,26,41,59,31,58};
printf("Before Sort:
");
for(i=0;i<7;i++)
{
printf("%d ",data[i]);
}
Heapsort(data,7);
printf("
After Sort:
");
for(i=0;i<7;i++)
{
printf("%d ",data[i]);
}
return 0;
}
void PercDown(int *data,int i,int n)
{
int Child;
int tmp;
for(tmp=data[i];LeftChild(i)<n;i=Child)//i=Child其實(shí)相當(dāng)于1個(gè)遞歸調(diào)用。相當(dāng)于將大的孩子與父節(jié)點(diǎn)做了1次交換。交換以后繼續(xù)調(diào)劑
{ //LeftChild(i)<n表示調(diào)劑至葉節(jié)點(diǎn)為止
Child=LeftChild(i);
if((Child!=n⑴)&&(data[Child+1]>data[Child]))//取出大的孩子
Child++;
if(tmp<data[Child])//將大的孩子與父節(jié)點(diǎn)比較，父節(jié)點(diǎn)取大的值
data[i]=data[Child];//此時(shí)data[i]的值在tmp中還有1份拷貝，并未完全被覆蓋
else
break;
}
data[i]=tmp;//將tmp還給樹(shù)中適合位置
}
void Heapsort(int *data,int n)
{
int i;
for(i=n/2;i>=0;i--)//i=n/2表示從最后1個(gè)非葉節(jié)點(diǎn)開(kāi)始調(diào)劑，（如果是葉節(jié)點(diǎn)，PercDown會(huì)跳過(guò)甚么都不做）i--則是此節(jié)點(diǎn)往前1次調(diào)劑非葉節(jié)點(diǎn)
PercDown(data,i,n);//i表示待調(diào)劑的父節(jié)點(diǎn) n表示樹(shù)的節(jié)點(diǎn)數(shù)
for(i=n⑴;i>0;i--)
{
Swap(&data[0],&data[i]);
PercDown(data,0,i);
}
}
void Swap(int *a,int *b)
{
int tmp;
tmp=*a;
*a=*b;
*b=tmp;
}
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
