排序算法――堆排序
来源：程序员人生 发布时间：2015-07-02 08:28:20 阅读次数：2481次
关于堆排序的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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
