堆排序

堆排序将数组看成一个二叉堆，对于序号为i的节点，第2*i+1和第2*i+2为它的子节点

最大堆，堆顶节点的元素比所有其他节点的元素都大的堆称为最大堆

void heapSort(int* array,int size)
{
    if(size<=1)
        return;
    int maxidx=size-1;
    int i=maxidx%2;
    if(i==0)
        i=(maxidx-2)/2;
    else
        i=(maxidx-1)/2;
    for(;i>=0;i--)
    {
        if((2*i+1)<=maxidx&&array[i]<array[2*i+1])
        {
            swap(array+i,array+(2*i+1));
        }
        if((2*i+2)<=maxidx&&array[i]<array[2*i+2])
        {
            swap(array+i,array+(2*i+2));
        }
    }
    swap(array,array+maxidx);
    heapSort(array,size-1);
}

排序原理

将数组看成一个二叉堆

1.构造最大堆.

2.堆顶元素排除

3 循环1，2直到剩余元素无法构造堆，排序完成

构造最大堆的方法

从最后一个非叶子节点向前遍历开始，如果子节点比当前节点大，将当前节点与子节点交换。遍历完成后最大的元素会被移动到堆的根节点，成为最大堆。