[数据结构与算法]排序 - 堆排序（可执行C++测试用例）

#include <iostream>
using namespace std;
//将元素k为根的子树进行调整，小元素下坠
void HeadAdjust(int A[],int k,int len){
    A[0]=A[k];
    for(int i=2*k;i<=len;i*=2){
        if(i<len&&A[i]<A[i+1]) i++;
        if(A[0]>=A[i]) break;
        else{
            A[k]=A[i];
            k=i;
        }
    }
    A[k]=A[0];
}
//建立大根堆
void BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;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]);
        HeadAdjust(A,1,i-1);
    }
}
int main(){
    //构造一颗完全二叉树
    int A[]={0,87,45,78,32,17,65,53,9};    
    HeadSort(A,8);
    for(int i=1;i<=8;i++){
        cout<<A[i]<<" ";
    }
    return 0;
}