2
回答
堆排序 求高手解答
开发十年,就只剩下这套Java开发体系了   

堆排序求解,为什么结果不是1,2,3,。。。顺序的

代码如下:

/* 堆排序(大顶堆) */
#include<iostream>
#include<algorithm>
using namespace std;


void HeapAdjust(int *a,int i,int size) //调整堆 
{
    int lchild=2*i;
    int rchild=2*i+1;
    int max=i; //临时变量 
    if(i<=size/2)
    {
        if(lchild<=size && a[lchild]>a[max])
        {
            max=lchild;
        }
        if(rchild<=size && a[rchild]>a[max])
        {
            max=rchild;
        }
        if(max!=i)
        {
            swap(a[i],a[max]);
            HeapAdjust(a,max,size); //避免调整堆之后以max为父节点的子树不是堆 
        }
 
    } 
}


void Build_Max_Heap(int *a,int size) //建立堆(初始化堆) 
{
    int i;
    for(i=size/2;i>=1;i--) //非叶子节点最大序号值为size/2 
    {
    HeapAdjust(a,i,size);
    }



void HeapSort(int *a,int size) //堆排序
{
    int i;
    Build_Max_Heap(a,size);
    for(i=size;i>=1;i--)
    {
        swap(a[1],a[size]);
        HeapAdjust(a,1,i-1);
    }



int main()
{
    int a[100],size;
    cout<<"输入要排序的数目:";
    cin>>size;
    cout<<"请输入要排序的数:";
    for(int i=1;i<=size;i++)
        cin>>a[i];

    HeapSort(a,size);

    for(int i=1;i<=size;i++)
        cout<<a[i]<<" ";

    cout<<endl;

    return 0;
}

举报
hjhomw
发帖于3年前 2回/485阅
顶部