用C语言实现堆排序算法

1.设计思路

排序的思想将一个数组按递增的顺序进行排序，将数组的第一个位置空下（下标为0），因为会导致子节点和本身同一个结点（i和2i一致），每次堆排序在下标1的位置放上了最大值，然后和最后一个元素交换位置，使之最大值依次放在最后的位置上，最后得到一个递增序列。

2. 源代码

#include<stdio.h> 
#include<stdlib.h>
void HeapSort(int a[], int n)
{	
	int end=8,x,y,z;	     //	进行堆排序，每次找出最大值放在第一个元素位置 
	while(end-1)
	{
	while(1)
	{	
	int	pa=end/2,tag=0;
	while(pa>0)
	{
		if(a[pa]<a[2*pa])
		{
			x=a[pa];
			a[pa]=a[2*pa];
			a[2*pa]=x;
			tag=1;
		}
		if(2*pa+1<=end&&a[pa]<a[2*pa+1])
		{
		
			y=a[pa];
			a[pa]=a[2*pa+1];
			a[2*pa+1]=y;
			tag=1;
		}
		pa--;
	}
		if(!tag)  break;
	}        //	将找出的最大值与最后一个元素调换位置 
	  z=a[1];
	  a[1]=a[end];
	  a[end]=z; 
	  end--;
  }	
}
int main(void)
{
	int i;
	int a[9]={-1,3,2,5,8,4,9,6,7};
	HeapSort(a,9);
	for( i=1;i<9;i++)   //	输出整体调整后的数组 
	{
		printf("%3d",a[i]);
	}
    printf("\n");
	return 0;
}