pra7.c

练习堆排序算法

#include<stdio.h>
#define MAXN 30
void siftdown(a,i,n)
int a[];
int i,n;
{
	int j,t;
	t=a[i];
	while((j=2*i+1)<n)
	{
		if(j<n-1&&a[j]<a[j+1])j++;
		if(t<a[j])
		{
			a[i]=a[j];
			i=j;
		}
		else break;
	}
	a[i]=t;
}
void heap_sort(a,n)
int a[];
int n;
{
	int i,t;
	for(i=(n-2)/2;i>=0;i--)
		siftdown(a,i,n);
	for(i=n-1;i>0;i--)
	{
		t=a[0];
		a[0]=a[i];
		a[i]=t;
		siftdown(a,0,i);
	}
}
void main()
{
	int b[MAXN];
	int n,i;
	printf("Please input the No. of the node:n=");
	scanf("%d",&n);
	printf("Please input the array:");
	for(i=0;i<n;i++)
		scanf("%d",&b[i]);
	heap_sort(b,n);
	for(i=0;i<n;i++)
		printf("%-5d",b[i]);
	printf("\n");
}