堆排序

利用到完全二叉树的有关知识，时间复杂度O(nlogn)

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int MAX_A = 100009;//使1到n元素为最大堆void Adjust(int a[],int i,int n){    int l=2*i, r=2*i+1;    int maxi=i;    //父亲是否比孩子大    if(l<=n&&a[l]>a[maxi])        maxi=l;    if(r<=n&&a[r]>a[maxi])        maxi=r;    if(maxi!=i)    {        //交换        swap(a[i],a[maxi]);        //保证调整以后以maxi为父节点的子树也为最大堆        Adjust(a,maxi,n);    }}void Build(int a[],int n){    //建大顶堆，从有叶子节点那一层的最大处开始    for(int i=n/2; i>=1; i--)        Adjust(a,i,n);}void Heap_sort(int a[],int n){    Build(a,n);    for(int i=n; i>1; i--)    {        swap(a[1],a[i]);        //只需调整root节点即可        Adjust(a,1,i-1);    }}int main(){    int a[MAX_A],n;    while(~scanf("%d",&n))    {        for(int i=1; i<=n; i++)            scanf("%d",&a[i]);        Heap_sort(a,n);        for(int i=1; i<=n; i++)            printf("%d ",a[i]);        printf("\n");    }}