堆排序实现

/*

 * Description:

 *           一个堆排序的实现，实现的是最大堆，主函数写了个简单的测试用例。

 * Author  :FinL

 * Language: C

 * Date    : 2010-07-20

 */

#include

void Swap(int *a,int *b)

{

int tmp;

tmp = *a;

*a = *b;

*b = tmp;

}

void Heapify(int *A,int idx,int max)

{

int left = 2*idx + 1;

int right = 2*idx + 2;

int largest;

if((leftA[idx]))

largest = left;

else

largest = idx;

if((rightA[largest]))

largest = right;

if(largest!=idx)

{

Swap(&A[idx],&A[largest]);

Heapify(A,largest,max);

}

}

void BuildHeap(int *A,int n)

{

int i = n/2-1;

while(i>=0)

{

Heapify(A,i,n);

i--;

}

}

void Sort(int *A,int n)

{

int i;

BuildHeap(A,n);

i = n-1;

while(i>=1)

{

Swap(&A[0],&A[i]);

Heapify(A,0,i);

i--;

}

}

int main()

{

int A[8] = {5,3,16,2,10,14,1,8};

int k;

Sort(A,8);

printf("Array A after sorted is : ");

for(k=0;k<8;k++)

{

printf(" %d  ", A[k]);

}

printf("\n");

return 0;

}