学步园

详细见算法导论：

最坏运行时间O(nlgn)

/*
堆排序 参考算法导论 
heap

数组的关系坐标都要减1 
*/
#include<iostream>
#include<stdio.h>
using namespace std;

int len;

void swap(int A[],int a,int b)
{
	int temp=A[a];
	A[a]=A[b];
	A[b]=temp;
} 

void max_heap(int A[],int i,int n)
{
	int l,r,max;
	l=2*i;//数组起始是0 l=a[2*i+1],r=A[2*i+2];
	r=2*i+1;
	
	if(l<=n&&A[l]>A[i])//寻找三者中最大的 
		max=l;
	else 
		max=i;
	if(r<=n&&A[r]>A[max])
		max=r;
		
	if(max!=i)
	{
		swap(A,max,i);
		max_heap(A,max,n);
	}	
} 

void build_heap(int A[],int len)
{
	for(int i=len/2;i>=1;i--)//非叶子节点开始建堆 
		max_heap(A,i,len);
}


void heap_sort(int A[],int n)
{
	build_heap(A,len);
	for(int i=len;i>1;i--)//每次最后一个与第一个最大的交换 
	{
		swap(A,1,i);
		n--;
		max_heap(A,1,n);
	}
} 

int main()
{
	int A[100];

    while(scanf("%d",&len))
    {
        int i;
        for(i=1;i<=len;i++)
            cin>>A[i];
        heap_sort(A,len);
        for(i=1;i<=len;i++)
            cout<<A[i]<<" ";
        cout<<endl;
    }
	
	return 0;
}