堆排序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 周強 閱讀(4279) 評論(2)  編輯 收藏 引用 所屬分類: 算法