数据结构-堆排序

注：下文没有堆内容的解释，首先先自己去看一下它的内容，想要学会堆排序需要先对堆有基本的概念。

堆排序是基于堆结构的排序方式，堆排序可理解为是直接选择排序的改进，直接选择排序。

例子：用堆排序（升序） 36 80 45 66 22 16 36 9

首先介绍一下第一轮排序交换发生了什么

#include 
#include 

template 
void print(const Type *arr, const int size)
{
    for (int i = 0; i < size; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}
template 
void siftDown(Type arr[], int pos, int size)
{
    int child;           //
    Type tmp = arr[pos]; //暂存根记录
    for (; pos * 2 + 1 < size; pos = child)
    {
        child = pos * 2 + 1;                                  // pos结点的左孩子
        if (child != size - 1 && arr[child + 1] > arr[child]) //选取两个孩子的大者
        {
            child++; //如果大于的话，选较大的那个，
        }
        if (arr[child] > tmp) //如果子孩子比父亲大，
        {
            arr[pos] = arr[child];
        }
        else
        {
            break;
        }
    }
    arr[pos] = tmp;
}
template 
void heapSort(Type arr[], int size)
{
    int i;
    for (i = size / 2 - 1; i >= 0; i--)
    {
        siftDown(arr, i, size);
    }
    for (i = size - 1; i > 0; i--)
    {
        std::swap(arr[0], arr[i]);
        siftDown(arr, 0, i);
    }
}
int main()
{
    int arr[] = {1, 7, 5, 2, 3, 88, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, size);
    print(arr, size);
    return 0;
}

快速排序和堆排序经常用于大量记录中找出排在前面的额若干个最大（或最小）记录。