[算法]堆排序

堆排序我是跟着这个视频学习然后自己实现了一下算法，视频已经讲的很清楚了，我就不多说了

建堆

堆排序顾名思义，要在堆上排序，堆是一种完全二叉树，分大根堆小根堆，我们现在只讲一种，就是小根堆建堆，小根堆用自顶而下建堆法，在建堆之前我们写好上滤、下滤操作。
我的实现是用数组，根节点从下标1开始，这样可以保证一个节点int(index/2)就能得到它的父节点
下滤就是跟子节点比较，然后交换或者退出操作。index就是需要执行操作的下标，size就是当前堆节点数

void UpToDown(int a[], unsigned int index, size_t size) // 下滤
{
    int maxindex; // maxindex用来储存a[index]的最大子节点
    do            // 既然选择执行下滤那么index一定不在最底层，所以至少执行一次下滤
    {
        maxindex = 2 * index;
        if (maxindex + 1 < size && a[maxindex + 1] > a[maxindex]) // 首先得保证读数据不会内存溢出吧
            maxindex++;
        if (a[index] < a[maxindex])
            swap(a[index], a[maxindex]);
        else
            break;
        index = maxindex;
    } while (index < size / 2);
}

与下滤对应的是上滤，就是跟父节点比较。

void DownToUp(int a[], unsigned int index) // 上滤
{
    int faindex = index / 2;
    do
    {
        if (a[index] > a[faindex])
            swap(a[index], a[faindex]);
        else
            break;
        index /= 2;
        faindex = index / 2;
    } while (faindex > 0);
}

代码都很简单，就不详细说了。
实现了上滤、下滤，剩下的就是建堆了，至于建大根堆还是小根堆看你自己意愿。

void BuildHeap(int a[], size_t size) // 自顶而下建堆法
{
    if (size < 3)
        return;
    for (int i = 2; i < size; i++)
    {
        DownToUp(a, i);
    }
}

都写一下吧

void BuildHeap(int a[], size_t size) // 自下而上建堆法
{
    for (int i = size / 2; i > 0; i--)
    {
        UpToDown(a, i, size);
    }
}

这就是堆排序前的所有操作，剩下的就是排序了，代码也很简单：

堆排序

void HeapSort(int a[], size_t size)
{
    for (int i = size - 1; i > 0; i--)
    {
        swap(a[i], a[1]);
        UpToDown(a, 1, i);
    }
    swap(a[1], a[2]);
}

注意堆排序的前提是对堆排序，需要先BuildHeap的，直接排序你只能看到一堆乱七八糟的结果，然后怀疑自己写的哪有问题（别问我怎么知道的）。
现在在你的main函数中写下你需要排序的数据，再试试你的代码就好了。

    int a[9] = {0, 3, 5, 4, 1, 2, 0, 85, 7};
    BuildHeap(a, 9);
    for (int i = 1; i < 9; i++)
        cout << a[i] << ' ';
    cout << endl;
    HeapSort(a, 9);
    for (int i = 1; i < 9; i++)
        cout << a[i] << ' ';