堆排：一种高效的比较排序算法

欢迎来到我的：世界

希望作者的文章对你有所帮助，有不足的地方还请指正，大家一起学习交流 !

前言

在计算机科学中，排序算法是一类非常重要的算法，它们用于将一系列元素按特定顺序排列。堆排序，作为一种基于比较的排序算法，因其优秀的平均和最坏情况时间复杂度（均为O(n log n)）而被广泛应用。本文将详细介绍堆排序的原理、实现步骤以及其优缺点。

我们需要先知道要对一组无序数据进行堆排，需要对这组无序数据进行1.建堆（向上调整算法 or 向下调整算法）和2.排序（向下调整算法）操作，即可；
先建堆:建堆就是把这组无序数据构成一个堆（大堆或小堆），如图：
对于这样一组无序数据：
可以看做一个这样的堆结构：
但是现在这个完全二叉树是对的么？
是的，它确实是一颗完全二叉树，但是它是堆结构么？
不是，因为堆一个就两种结构：
1.小堆存储结构：父节点的值总是小于或等于其子节点的值，
2.大堆存储结构：父节点的值总是大于或等于其子节点的值
显然这颗完全二叉树不满足堆结构的定义，所以此时需要进行建堆操作：也就是先把这个完全二叉树构建成满足堆结构下面进行的操作：那么又会问怎么进行调整让它变成堆结构呢？
接下来就需要知道两种调整的方法：1.向上调整算法 2.向下调整算法
对于这两种调整算法的解释可以看我另一篇博客堆的应用
下面我以向下调整算法做例（建小堆）：

现在建好堆了，就差进行排序了😊
其实可以看出堆结构有什么特点，就是堆顶的那个元素一定是整个堆结构最小（建小堆）或最大（建大堆），所以我们可以根据这一特性进行逆序排序：
首先我们需要知道，如果你建的是小堆，那你只能进行逆序的排序，那如果你建的是大堆，那你只能进行升序的排序；
因为我们是建的小堆，那就进行逆序：先把堆顶的元素与最后一个元素进行交换，此时我们已经可以确定最后一个值的位置了，（因为是逆序么，所以最小值当然在最后喽🤣），但是交换之后我们堆结构又打乱了，所以需要再进行一次建堆操作（向下调整算法），但是要注意，这次进行建堆的结点个数要少一个（因为最后一位已经排好了）如图：

然后你肯定能发现其规律了，一次一次的将堆顶的元素移到后面，直到所有数据排好序；
😁😁😁😁😁😁😁

内容

堆排序的原理

堆排序基于二叉堆数据结构，二叉堆可以是最大堆或最小堆。在最大堆中，父节点的值总是大于或等于其子节点的值；而在最小堆中，父节点的值总是小于或等于其子节点的值。堆排序算法通过维护一个最大堆来实现排序。

堆的构建（排升序）

• 构建最大堆：将无序数组构建成一个最大堆，确保每个父节点的值都大于子节点的值。
• 交换并调整堆：将堆顶元素（最大值）与数组末尾元素交换，然后将堆的大小减一，即从堆中移除最后一个元素。
• 重新调整堆：由于交换操作可能破坏了堆的性质，需要对堆顶元素进行调整，以恢复最大堆的性质。
• 重复步骤2和3：重复上述过程，直到堆的大小为1，此时数组已经按照降序排列完成。

对于其中的建堆的一些基本概念：可以看另一篇博客：建堆的基本概念

堆排的优点

• 时间复杂度稳定：堆排序的时间复杂度为O(nlog(n))，无论是最好、最坏还是平均情况，这个复杂度在所有比较排序算法中是最优的。
• 空间复杂度低：堆排序是原地排序算法，除了常数个额外空间用于存储递归栈之外，不需要额外的内存空间。
• 适用于各种数据类型：堆排序可以适用于各种数据类型，包括整数、浮点数、字符串等，只要能够为这些数据类型定义合适的比较操作。
• 易于实现：堆排序的实现相对简单，尤其是使用二叉堆的实现。
• 原地排序：堆排序不需要额外的辅助存储空间，只需要在原数组上进行元素的交换和调整
• 稳定性：虽然堆排序通常不是稳定的排序算法，即相同值的元素在排序后的相对位置可能会发生改变。

动态演示

堆排代码实现

#include <assert.h> // 引入断言库，用于检查数组是否为空

// 交换两个整数的值
void Swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 向下调整算法（升序：建大堆）
// a: 数组
// n: 数组长度
// parent: 父节点索引
void AdjustDwon(int* a, int n, int parent) {
    int child = parent * 2 + 1; // 计算左子节点的索引

    // 只要左子节点在数组范围内，就进行循环
    while (child < n) {
        // 如果右子节点存在且右子节点的值大于左子节点的值，则选择右子节点作为child
        if (child + 1 < n && a[child + 1] > a[child]) {
            child++;
        }
        // 如果子节点的值大于父节点的值，则交换它们，并继续向下调整
        if (a[child] > a[parent]) {
            Swap(&a[parent], &a[child]); // 交换父节点和子节点的值
            parent = child; // 更新父节点索引为子节点索引
            child = parent * 2 + 1; // 重新计算子节点的索引
        } else {
            // 如果不需要交换，则退出循环
            break;
        }
    }
}

// 堆排序算法
// a: 数组
// n: 数组长度
void HeapSort(int* a, int n) {
    assert(a); // 确保传入的数组a不为空

    // 建大堆
    // 从最后一个非叶子节点开始，向前遍历数组，对每个节点进行调整
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDwon(a, n, i);
    }

    // 开始排序
    int end = n - 1; // 设置数组最后一个元素的索引
    while (end > 0) {
        // 将堆顶元素（最大值）与数组末尾的元素交换
        Swap(&a[0], &a[end]);
        // 调整堆，使其满足大顶堆的性质
        AdjustDwon(a, end, 0);
        // 减少end的值，缩小排序的范围
        end--;
    }
}

总结

到了最后：感谢支持

------------对过程全力以赴，对结果淡然处之