堆排序

堆简介

判断堆的标准：1.完全二叉树；2.满足最大堆或最小堆，两个条件缺一不可。

构建堆

要想实现堆排序首先你得构建一个堆。
如何构建呢，如图所示

算法描述

void AjustDown(int* a, size_t size, int root)
{
    assert(a);
    int parent = root;
    int child = parent * 2 + 1;
    while (child < size)
    {
        if (a[child + 1] && a[child] < a[child + 1])
        {
            ++child;
        }
        if (a[parent] < a[child])
        {
            swap(a[parent], a[child]);
            parent = child;
            child = child * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(int* a, size_t size)
{
    assert(a);
    for (int i = (size - 2) / 2; i >= 0; --i)
    {
        AjustDown(a, size, i);
    }
    for (int index = size - 1; index > 1; --index)
    {
        swap(a[index], a[0]);
        AjustDown(a, index-1, 0);
    }
}