void SelectSort(int A[],int n) {
    int i,min,j;
    for(i=0; i<n-1; i++) { //一共进行n-1趟排序
        min=i;//记录最小元素的位置
        for(j=i+1; j<n; j++) //在A[i...n-1]中选择最小元素的位置
            if(A[j]<A[min])min=j;//更新最小元素的位置
        if(min!=j) swap(A[i],A[min]);//与第i个位置交换
    }
}

void AdjustUp(int A[],int k)
 {//参数k为向上调整的结点，也是堆的元素个数 
     A[0]=A[k];
     int i=k/2;//若结点值大于双亲结点，就将双亲结点向下调，并继续向上比较 
     while(i>0&&A[i]<A[0])
     {
         A[k]=A[i];//双亲结点下调 
         k=i;
         i=k/2;//继续向上比较 
     }
     A[k]=A[0];//复制到最终位置 
 }
void AdjustDown(int A[],int k,int len)
{
    A[0]=A[k];//A[0]暂存 
    for(int i=2*k;i<=len;i++)//沿着关键字较大的子节点向下筛选 
    {
        if(i<len&&A[i]<A[i+1])
        i++;//取关键字值较大的子节点下标 
        if(A[0]>=A[i])break;//筛选结束 
        else{
            A[k]=A[i];//将A[i]调整到双亲结点上 
            k=i;//修改k，方便继续向下筛选 
        }
    }
    A[k]=A[0];//被筛选的结点的值放入最终位置 
}
void BuildMaxHeap(int A[],int len) {//建立大根堆 
    for(int i=len/2; i>0; i--) {//从i=[n/2]~1,反复调整堆 
        AdjustDown(A,i,len);
    }
}

void HeapSort(int A[],int len)
{
    BuildMaxHeap(A,len);//初始建堆 
    for(int i=len;i>1;i--)//n-1趟交换和建堆的过程 
    {
        swap(A[i],A[1]);//输出堆顶元素（和堆底元素交换） 
        AdjustDown(A,1,i-1);//整理，把剩余的i-1个元素整理成堆 
    }
 }