选择排序之大根堆

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

灵魂在于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;
}