堆排序

#include <stdio.h>
#define LeftChild(i) (2 * (i) + 1)

typedef int ElementType;
void PercDown(ElementType A[],int i,int N);
void HeapSort(ElementType A[],int N);
void Swap(ElementType *a,ElementType *b);
int main(void)                                  //利用大顶堆的性质，每次删除最大值，放到数组最下面
{
int i;
int a[10] = {55,88,35,1,2,3,45,89,62,26};

HeapSort(a,10);

for( i = 0; i < 10; i++)
printf("%-4d",a[i]);

printf("\nHello World!\n");
return 0;
}
void PercDown(ElementType A[],int i,int N)              //调整函数
{
int Child;
ElementType Tmp;

for(Tmp = A[i]; LeftChild(i) < N; i = Child)
{
Child = LeftChild(i);
if(Child != N - 1 && A[Child + 1] > A[Child])       //找到左右儿子中最大的
Child++;
if(Tmp < A[Child])                             //如果父亲比儿子小，父亲等于儿子
A[i] = A[Child];                           //一直往下递归，直到找到合适的放置父亲的位置
else
break;                                          //如果父亲比儿子大，退出
}

A[i] = Tmp;                                             //该节点等于父亲
}

void HeapSort(ElementType A[], int N)
{
int i;

for( i = N / 2; i >= 0; i--)                //建立堆，实质上是从最后一个非子叶节点开始，
PercDown(A,i,N);                        //向下调整，使父亲节点值最大
for(i = N - 1; i > 0; i--)
{
Swap( &A[0] , &A[i]);                   //删除max，利用交换将最大值有序放入数组，
//从数组最后一个位置放起
PercDown(A,0,i);                        //调整堆
}
}
void Swap(ElementType *a,ElementType *b)
{
ElementType x = *a;
*a = *b;
*b = x;
}