用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;
}

3.运行结果