好库网 好库网首页 | 我的好库
VC开发指南

C语言实现堆排序(Heap Sort)

发布者:vchelp
发布日期:2012/6/19 13:11:04   更新日期:2012/6/19 13:11:04
阅读次数:4027
评分:4.90
介绍:对于大量的记录的排序来说,堆排序是一种非常有效的方法。如果排序的记录数不大,则堆排序的优越性并不明显,而且还需要一个供交换时暂存记录的辅助空间。
正文:

 

对于大量的记录的排序来说,堆排序是一种非常有效的方法。如果排序的记录数不大,则堆排序的优越性并不明显,而且还需要一个供交换时暂存记录的辅助空间。

 

堆排序的时间复杂度是O(nlgN),与快速排序达到相同的时间复杂度。但是在实际应用中,我们往往采用快速排序而不是堆排序。这是因为快速排序的一个好的实现,往往比堆排序具有更好的表现。堆排序的主要用途,是在形成和处理优先级队列方面。另外,如果计算要求是类优先级队列(比如,只要返回最大或者最小元素,只有有限的插入要求等),堆同样是很适合的数据结构。

 

 

测试代码:

 

#include <stdio.h>
#define MARK 0

static a[8] = {MARK,25,4,36,1,60,10,58,};
int count = 1;
void heap(int n);
void adjust(int i,int n);

int main(void)
{
	int i;
	printf("源数据为:");
	for(i = 1;i<8;i++)
		printf("%5d",a[i]);
	heap(7);
	printf("\n排序后的数据为:");
	for(i = 1;i<8;i++)
		printf("%5d",a[i]);
	printf("\n");
	return 0;
}

void heap(n)
int n;
{
	int i,j,t;
	for(i =n/2;i>0;i--)
		adjust(i,n);
	printf("\n初始化成堆===>   ");
	for(i = 1;i < 8;i++)
		printf("%5d",a[i]);
	for(i = n-1;i>0;i--)
	{
		t = a[i+1];
		a[i+1] = a[1];
		a[1] = t;
		adjust(1,i);
		printf("\n第%2d步操作结果===>",count++);
		for(j = 1;j<8;j++)
			printf("%5d",a[j]);
	}
}

void adjust(i,n)
int i,n;
{
	int j,k,r,done=0;
	k = r = a[i];
	j = 2*i;
	while((j<=n)&&(done==0))
	{
		if(j<n)
		{
			if(a[j]<a[j+1])
				j++;
		}
		if(k>=a[j])
			done = 1;
		else
		{
			a[j/2] = a[j];
			j = 2*	j;
		}
	}
	a[j/2] = r;
}

 

 

 


评论 [发表评论]
账号 密码 还没帐号呢,现在注册一个?

免责声明:好库网所展示的信息由买卖双方自行提供,其真实性、准确性和合法性由信息发布人负责。好库网不提供任何保证,并不承担任何法律责任。