/*
* 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 阅读(107)
评论(0) 编辑 收藏 引用 所属分类:
算法学习