xfstart07
Get busy living or get busy dying

/*
 * Problem: Sort
 * Author: Xu Fei
 * Time: 2010.8.2 21:06
 * Method: HeapSort
 
*/
#include
<iostream>
#include
<cstdio>
using namespace std;

int N;
int A[200001];

void init()
{
    
int i;
    scanf(
"%d",&N);
    
for(i=1;i<=N;++i)
        scanf(
"%d",A+i);
}
void hsort(int i)
{
    
int tmp,j;
    tmp
=A[i];
    j
=i<<1;
    
while(j <= N)
    {
        
if(j < N && A[j] > A[j+1])
            j
++;
        
if(tmp > A[j])
        {
            A[j
>>1]=A[j];
            j
<<=1;
        }
        
else
            
break;
    }
    A[j
>>1]=tmp;
}
void solve()
{
    
int i;
    
for(i=N>>1;i>=1;--i)
        hsort(i);
    
while(N > 1)
    {
        printf(
"%d ",A[1]);
        A[
1]=A[N--];
        hsort(
1);
    }
    printf(
"%d\n",A[1]);
}
int main()
{
    freopen(
"sort.in","r",stdin);
    freopen(
"sort.out","w",stdout);
    init();
    solve();
    
return 0;
}




posted on 2010-08-02 21:12 xfstart07 阅读(44) 评论(0)  编辑 收藏 引用 所属分类: 算法学习

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理