【数据结构】排序算法系列——堆排序（附源码+图解）

堆排序

堆排序基于一种常见的**[[二叉树]]结构**：堆

我们前面讲到选择排序，它在待排序的n个记录中选择一个最小的记录需要比较n一1次。本来这也可以理解，查找第一个数据需要比较这么多次是正常的，否则无法知道它是最小的记录。
可惜的是，这样的操作并没有把每一趟的比较结果保存下来，在后一趟的比较中，有许多比较在前一趟已经做过了，但由于前一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作，因而记录的比较次数较多。

那么我们有什么办法可以用来解决这样的重复比较的问题呢？

那么堆排序就由此而生了。简单来说，堆的性质包括如下几点：

堆（Heap）是一种特殊的树形数据结构，通常用作优先[[队列]]。堆排序算法利用了堆的性质来实现排序。堆的性质总结如下：

1. 完全二叉树：堆是一种完全二叉树（Complete Binary Tree），即除了最后一层外，每一层的节点都是满的，且最后一层的节点从左到右依次排列。
2. 堆的有序性：
   • 大顶堆（Max-Heap）：对于每一个节点 i，都满足 A[i] ≥ A[2i + 1] 且 A[i] ≥ A[2i + 2]（如果子节点存在）。即，父节点的值总是大于或等于其子节点的值。
   • 小顶堆（Min-Heap）：对于每一个节点 i，都满足 A[i] ≤ A[2i + 1] 且 A[i] ≤ A[2i + 2]（如果子节点存在）。即，父节点的值总是小于或等于其子节点的值。
3. 堆的高度：一个包含 n 个节点的堆的高度为 O(log n)。因为堆是完全二叉树，树的高度和节点数量的对数成正比。

根据堆的有序性和完全二叉树的性质，我们得知将其用在排序上是可行的，并且还能够有效减少重复比较的次数，这何乐而不为呢？

1964年，Floyd和Williams发明了堆这种数据结构，同时也发明了堆排序这种算法。

算法思想

鉴于堆的有序性，我们在进行堆排序时首先要构建一个大顶堆或者小顶堆，这里为了方便计算，我们统一为大顶堆。在大顶堆的性质下，可能会有人疑问：既然这个堆已经满足了有序性，那还需要排序什么呢？直接返回不就行了吗？其实不然。我们所知道的有序性的堆只是针对子节点与父节点之间的大小关系，例如以下堆：

我们可以看到，它确实满足大顶堆的性质：父节点永远大于子节点。但是当我们根据[[二叉树]]的遍历来进行输出时，会发现同一个父节点的子节点之间以及其中一个子节点的子节点实际上是无序的，例如60和10，它们之间是大于的关系；而60的子节点又都比10大，那么在遍历的时候，自然就不有序了。

所以堆实际上并不是完全有序的，而我们使用堆排序这个算法，也并非是根据这样的特征来进行的。我们直接看它的算法步骤：

1. 首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质（也就是将剩余n-1个元素继续构成一个堆）；
2. 之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；
3. 以此类推，在第n-1次操作后，整个数组就完成了排序。

我们可以看到，实际上堆排序的核心思想就是将第一个根节点（最大值）与数组末尾的元素来进行交换（目的是为了构建无需新开辟空间就能直接构建有序数组，末尾元素被交换后也不会影响大顶堆的重新构建），然后重新构造堆，那么此时的第二个根节点就仅次于第一个根节点的大小，这么以此类推，最终将所有节点根据大、次大、第三大的顺序排序在数组中，那么也就成功构建出了有序的数组。

C语言代码分析

void AdjustDown(HPDataType* a, int n,int parent)//向下调整算法
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        //选择左右孩子中大的那一个
        if (child+1 < n && a[child+1] > a[child])//如果右孩子存在并且右孩子大于左孩子
        {
            ++child;
        }
        if (a[child] > a[parent])//如果孩子大于父亲
        {
            Swap(&a[child] , &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else//如果孩子小于父亲
        {
            break;
        }

    }
}


void HeapSort(int* a, int n)
{
    /*for (int i = 1; i < n; i++)
    {
        AdjustUp(a, i);
    }*/
    for (int i = (n - 1 - 1) / 2; i >= 0; i++)//从最后一个非叶子节点开始调整
    {
        AdjustDown(a, n, i);
    }

    int end = n-1;
    while (end > 0)//每次将堆顶元素与最后一个元素交换，然后调整堆
    {
        Swap(&a[end], &a[0]);
        AdjustDown(a, end, 0);
        end--;
    }
}

时间复杂度

我们发现堆的算法实际上是基于[[二叉树]]排序的，并且在最坏情况和最好情况下的堆排序都是同一量级的操作，所以我们得出其时间复杂度为：O(n logn)

稳定性

鉴于堆排序会改变前后元素的相对位置，所以：不稳定