堆排序

一个简单的堆排序实现,以便自己以后查阅。
#include<iostream> 
#include<fstream>
#include<algorithm>
using namespace std;

#define N 10000
int heapsize;
ifstream fin("input.txt");

void Heapsort(int *A);
void BuildMaxHeap(int *A);//建大顶推
void MaxHeapify(int *A, int i);
int main()
{
    int A[N];
    fin>>A[0];//存储元素个数
    for(int i=1;i<=A[0];i++)
        fin>>A[i];

    Heapsort(A);
    
    for(int i=1;i<=A[0];i++)
        cout<<A[i]<<" ";
    cout<<endl;
    
    return 0;
}
void Heapsort(int *A)
{
    heapsize=A[0];
    BuildMaxHeap(A);
    for(int i=heapsize ; i>=2; i--)//向下调整
    {
        swap(A[i],A[1]);
        heapsize--;
        MaxHeapify(A,1);
    }
}
void BuildMaxHeap(int *A)//建大顶推
{
    int i=A[0]/2;
    for(; i>=1; i--)//向上调整
        MaxHeapify(A,i);
}
void MaxHeapify(int *A, int i)
{
    int l=i*2;
    int r=l+1;
    int largest;
    if(l<=heapsize && A[l]>A[i])
        largest=l;
    else
        largest=i;
    if(r<=heapsize && A[r]>A[largest])
        largest=r;
    if(largest != i)
    {
        swap(A[largest], A[i]);
        MaxHeapify(A,largest);
    }
}

posted on 2012-03-05 08:48 DjvuLee 阅读(222) 评论(0)  编辑 收藏 引用 所属分类: 排序


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


导航

<2012年3月>
26272829123
45678910
11121314151617
18192021222324
25262728293031
1234567

统计

常用链接

留言簿

随笔分类(13)

随笔档案(19)

文章分类(2)

文章档案(1)

搜索

最新评论

评论排行榜