Just enjoy programming

堆排序c语言实现

/*堆排序 实现,算法复杂度O(nlgn)*/
#include<stdio.h>
#include<stdlib.h>

/*假设节点i的左右子树都是最大堆,操作使节点i的子树变成最大堆*/
void maxHeap(int A[],int len,int i)
{
    int l,r,large,temp;
    l=2*i;
    r=2*i+1;
    large=i;
    if(l<len)
    {
        if(A[l]>A[i])
        {
            large=l;
        }
    }
    if(r<len)
    {
        if(A[r]>A[large])
        {
            large=r;
        }   
    }

    if(large!=i)
    {
        temp=A[large];
        A[large]=A[i];
        A[i]=temp;
        maxHeap(A,len,large);
    }
}

/*建立大根堆*/
void buildMaxHeap(int A[],int len)
{
    int i;
    for(i=len/2-1;i>=0;i--)
        maxHeap(A,len,i);
}


/*堆排序*/
void maxHeapSort(int A[],int len)
{
    int i,temp;
    buildMaxHeap(A,len);
    printf("建立大跟堆\n");
    for(i=0;i<len;i++)
        printf("%d ",A[i]);
    printf("\n");

    for(i=len;i>1;i--)
    {
        temp=A[0];
        A[0]=A[i-1];
        A[i-1]=temp;
        printf("%d  ",A[i-1]);
        buildMaxHeap(A,i-1);
    }
    printf("\n");
}

/*测试堆排序*/
int main()
{
    int i;
    int A[11]={4,1,3,2,16,9,10,14,8,7,6};
    maxHeapSort(A,11);
   
    for(i=0;i<11;i++)
    {
        printf("%d  ",A[i]);
    }
    printf("\n");
}

posted on 2011-03-21 21:48 周强 阅读(4228) 评论(2)  编辑 收藏 引用 所属分类: 算法

评论

# re: 堆排序c语言实现[未登录] 2011-08-23 18:16 gleaner

你好,你用 A[17]={4,12,12,2,16,9,10,14,8,7,6,11,13,27,22,15,29};
看看是否会有问题。个人感觉是有问题的  回复  更多评论   

# re: 堆排序c语言实现 2011-08-24 00:21 周强

@gleaner
谢谢你的问题,程序确实有点问题。在maxHeap函数中左右孩子下标计算中有点问题。下标从0开始计数。
l=2*i;
r=2*i+1;

应该改为
l=2*i+1;
r=2*i+2;  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理