选择排序之大根堆

大根堆：树的根节点大于左右子树的结点值，这样就能保证每次从树根取的是最大值

灵魂在于HeadAdjust函数，以某节点为树根通过下落调整为大根堆，

建树思想 就是，从最后一个非终端结点开始调整以该结点为根的子树， 通过HeadAdjusth函数下落实现

排序：因为树根是最大值，每次取数根，然后与树最后一个结点交换，然后将这个点固定，树的结点数减一，调整根节点这棵树重新变为大根堆，重复依次。

#include <bits/stdc++.h> 
using namespace std;
#define inf 0x3f3f3f
void swap(int &a, int &b){int tmp=a;a=b;b=tmp;
}
//子树头节点的下落 
void HeadAdjust(int a[], int k, int len){a[0]=a[k];//暂存子树头结点//一直下落，找到最终位置 for(int i=k*2; i<=len; i*=2){if(i<len && a[i+1]>a[i])i++;//从左右儿子中找到一个最大儿子 if(a[0]>=a[i])break;//找到了最终下落位置 else{//孩子比他大，就下落 a[k]=a[i];k=i;}}a[k]=a[0];//给找到的结点写回值 
}
void BuildMaxHeap(int a[], int len){//a数组从1开始存//从最后一个非终端结点开始调整，下落； for(int i=len/2; i>=1; i--){HeadAdjust(a, i, len);}
}
void HeadSort(int a[], int len){BuildMaxHeap(a, len);//建大根堆 //每次将数跟也就是最大元素与最后一个元素交换，//再调整大根堆，每次就能确定一个未确定的最大数 for(int i=len; i>1; i--){swap(a[i], a[1]);//把最大的结点1放到树末 HeadAdjust(a, 1, i-1);//每次确定一个最大数，未确定数就少一个 } 
} 
int main()
{int a[100];int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}HeadSort(a, n);for(int i=1;i<=n;i++)cout<<a[i]<<endl;return 0;
}