排序算法――堆排序

关于堆排序的1些基本定义可参见我转载的另外一篇博文。http://blog.csdn.net/u010275850/article/details/45311661

 其实在学习堆的时候仔细的同学就能够发现,只要顺次保存删除操作的数据,就能够得到1个有序的序列。堆排序也是利用了这样的思想。

算法实现:

/*根据最大堆实现的堆排序*/
#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其实相当于1个递归调用。相当于将大的孩子与父节点做了1次交换。交换以后继续调剂
{ //LeftChild(i)<n表示调剂至叶节点为止
Child=LeftChild(i);
if((Child!=n⑴)&&(data[Child+1]>data[Child]))//取出大的孩子
Child++;
if(tmp<data[Child])//将大的孩子与父节点比较,父节点取大的值
data[i]=data[Child];//此时data[i]的值在tmp中还有1份拷贝,并未完全被覆盖
else
break;
}
data[i]=tmp;//将tmp还给树中适合位置
}

void Heapsort(int *data,int n)
{
int i;
for(i=n/2;i>=0;i–)//i=n/2表示从最后1个非叶节点开始调剂,(如果是叶节点,PercDown会跳过甚么都不做)i–则是此节点往前1次调剂非叶节点
PercDown(data,i,n);//i表示待调剂的父节点 n表示树的节点数
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;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 排序算法――堆排序

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡