堆排序

//对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)   //从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
}

/*将以k为根的子树调整为大根堆
从最底层的分支结点开始调整*/
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];                      //A[0]暂存子树的根结点
    for(int i=2*k; i<=len; i*=2){     //沿key较大的子结点向下筛选
                                      // i为当前所选根结点的左孩子
                                      //i*=2是为了判断调整后再下一层是否满足大根堆
        if(i<len && A[i]<A[i+1])      //判断：当前所选根结点的左、右结点哪个更大
            i++;                      //取key较大的子结点的下标
        if(A[0] >= A[i]) 
            break;                    //筛选结束：i指向更大的子结点
        else{
            A[k] = A[i];              //将A[i]调整至双亲结点上
            k=i;                      //修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0]                       //被筛选的结点的值放入最终位置
}

//交换
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

//基于大根堆进行排序
void HeapSort(int A[], int len){
    BuildMaxHeap(A, len);          //初始建堆
    for(int i=len; i>1; i--){      //n-1趟的交换和建堆过程
        swap(A[i], A[1]);          //堆顶元素和堆底元素交换
        HeadAdjust(A,1,i-1);       //把剩余的待排序元素整理成堆
    }
}