堆排序算法

算法思想:首先将与堆相应的完全二叉树根节点中的记录移出，该记录称为待调整记录，此时根节点相当于空节点，从空节点的左右孩子中选出一个关键字较大的记录，如果该记录的关键字大于待调整记录的关键字，则将该记录上移至空节点中。

此时，原来的那个关键字较大的节点相当于空节点，从空节点的左右孩子中选出一个关键字较大的记录，如果该记录的关键字仍大于待调整记录的关键字，则将该记录上移至空节点。

重复上述过程，直至空节点左右孩子的关键字均小于待调整记录的关键字，此时，将待调整记录放入空节点中，测试代码如下所示：

#include<stdio.h>
#include<stdlib.h>

void min_heapfy(int a[],int HEAPSIZE,int i)
{

    int t;
    int flag=1;
    int j=2*i; //左孩子结点
    t=a[i]; //暂存根记录
    while(j<=HEAPSIZE&&flag)
    {

        if((j+1)<=HEAPSIZE&&a[j]<a[j+1]) j++; //若存在右子树，且右子树根的关键字大，则沿右分支"筛选"

     if(t>=a[j]) flag=0; //筛选完毕

        else
        {
            a[i]=a[j];
            i=j;
            j=2*i;
        } //继续筛选

    }
    a[i]=t; //将a[i]填入恰当的位置
}
void Create_min_heap(int a[],int length)//创建堆
{

    int i;
    for(i=length/2;i>=1;i--)/*自第[length/2]个记录开始进行筛选建堆*/
        min_heapfy(a,length,i);
}

/*对a[1....n]进行堆排序，执行本算法后，a[]中记录按关键字由大到小排列*/
void HeapSort(int a[],int length)
{
    int i,e;
    Create_min_heap(a,length);
    for(i=length;i>=1;--i)
    {
        printf("%4d",a[1]); //输出堆顶
        e=a[1];                //将堆顶记录和堆中的最后一个记录进行交换
        a[1]=a[i];
        a[i]=e;
        min_heapfy(a,i-1,1); //进行调整，使a[1....n-1]记录变成堆
    }
}
int main()
{
    int a[100];
    int i;
    int length;
    printf("请输入元素个数 : ");
    scanf("%d",&length);

    for(i=1;i<=length;i++)
        scanf("%d",&a[i]);

    printf("\n");
    Create_min_heap(a,length);

    printf("创建好堆以后的数组元素如下所示: \n");
    for(i=1;i<=length;i++)
        printf("%4d",a[i]);
    printf("\n");
    printf("经过排序后的堆,数组元素如下所示 : \n");

    HeapSort(a,8);
    printf("\n");


}