七大排序之堆排序

<HeapSort>
简单选择排序的改进：减少第i趟排序比较的次数。
对排序的关键：建堆和调整堆。
建堆的过程：
第1趟将索引0至n-1处的全部数据建大顶堆，就可以选出这组数据的最大值。将该堆的根节点跟这组数据的最后1个节点交换，就使得这组数据中最大排在了最后；
第2趟将索引0至n-2处的全部数据建大顶堆，就可以选出这组数据的最大值。将该堆的根节点与这组数据的倒数第2个节点交换，就使的这组数据中最大值排在了倒数第2位；
......
索引0至n-k处的全部数据建大顶堆，就可以选出这组数据的最大值。将该堆的根节点与这组数据的倒数第k个节点交换，就使的这组数据中最大值排在了倒数第k位。
其实整个堆排序过程中, 我们只需重复做两件事：
建堆(初始化+调整堆, 时间复杂度为O(n))；
拿堆的根节点和最后一个节点交换(siftdown, 时间复杂度为O(nlog n) )
因而堆排序整体的时间复杂度为O(nlog n)。
伪代码：

//对下标为i的节点来说
parent(i) return i/2;
left(i) return 2*i;
right(i) return 2*i+1;

void adjust(int *a, int size,int index)
{
    int left = 2*index;
    int right = 2*index+1;
    int parent = index/2;
    int maxIndex = index;
    if(left<size && a[left]>a[maxIndex]) maxIndex=left;
    if(right<size && a[right]>a[maxIndex]) maxIndex=right;//maxIndex是3个数中最大数的下标
    if(index != maxIndex)
    {
        swap(a[index],a[maxIndex]);
        adjust(a,size,maxIndex); //递归调整其它不满足堆性质的部分
    }

}

void HeapSort(int *a,int size)
{
    for(int i=size/2-1;i>=0;i--) // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
    {
        adjust(a,size,i);
    }
    for(int i = size-1;i>=1;i--)
    {
        swap(a[0],a[i]);//将当前最大的放置到数组末尾；
        adjust(a,i,0);
    }
}