博客

堆排序的C语言代码实现

#include<stdio.h>

int a[100];
void Exchange(int i,int n)//将最大叶子结点与根结点交换 
{
	int temp;
	temp = a[i];
	a[i] = a[n];
	a[n] = temp;
	
}

void Created(int n)
{
	if(n == 2){//当只剩两个的时候，直接比较大小 先输出最大的 然后输出最小的 
		if(a[0] > a[1]){
			printf("%d %d\n",a[0],a[1]);
		}
		else
			printf("%d %d\n",a[1],a[0]);
		return;
	}
	int i;
	for(i = n/2-1;i >= 0; i--) //比较每一个根结点与其叶子结点的大小   并且将大于根结点的叶子结点与根结点交换 
	{//最后一个根结点是第n/2个 但是第一个数下标为0  所以最后一个根结点下标为n/2-1 
		if(a[2*i+1] > a[i] && 2*i+1 < n)//与左孩子进行比较 
			Exchange(i,2*i+1);
		if(a[2*i+2] > a[i] && 2*i+2 < n)//与右孩子进行比较 
			Exchange(i,2*i+2);
	}
	int t;
	t = a[0];//将第一个根结点与最后一个叶子结点互换 
	a[0] = a[n-1];
	a[n-1] = t;
	printf("%d ",a[n-1]);//输出最大的结点 
	Created(n-1);//将是输出的结点弹出 
}

int main()
{
	int  n;
	printf("请输入需要排序的元素的个数：");
	scanf("%d",&n);
	printf("请输入%d个元素:",n);
	for(int j =0; j <n; j++)
	{
		scanf("%d",&a[j]);
	}
	Created(n);
	return 0;
}