点击蓝字，关注我们

往期回顾

C语言的魔法书：揭秘stdio.h

如何用判断和转换字符类型

本节重点

C语言堆排序-数组的应用

堆排序是什么？

堆排序是一种基于堆这种数据结构的排序算法。堆是一种特殊的二叉树，它的每个节点都满足以下性质：

大顶堆：每个节点的值都大于或等于其子节点的值
小顶堆：每个节点的值都小于或等于其子节点的值

这样的性质保证了堆的根节点（堆顶）是整个堆中的最大值或最小值。因此，堆排序就是利用这个特点，不断地把堆顶元素和堆尾元素交换，然后调整堆的结构，直到堆中只剩下一个元素为止。

堆排序的原理

堆排序的原理可以分为两个步骤：

建堆：把一个无序的数组转化为一个堆
排序：把堆中的元素按照大小顺序输出

建堆：

建堆的过程是从数组的最后一个非叶子节点开始，依次向上调整每个节点，使其满足堆的性质。这个过程可以用一个循环来实现，如下：

// 假设数组a的长度为n，下标从0开始
void build_heap(int a[], int n) 
{
    // 从最后一个非叶子节点开始，向上调整
    for (int i = n / 2 - 1; i >= 0; i--) 
    {
        // 调用shift_down函数，使以i为根的子树满足堆的性质
        shift_down(a, i, n);
    }
}

排序：

排序的过程是不断地把堆顶元素和堆尾元素交换，然后缩小堆的大小，再调整堆的结构，直到堆中只剩下一个元素为止。这个过程也可以用一个循环来实现，如下：

// 假设数组a的长度为n，下标从0开始
void heap_sort(int a[], int n) 
{
    // 先建堆
    build_heap(a, n);
    // 循环n-1次，每次把堆顶元素和堆尾元素交换，然后缩小堆的大小，再调整堆的结构
    for (int i = n - 1; i > 0; i--) 
    {
        // 交换堆顶元素和堆尾元素
        swap(a, 0, i);
        // 缩小堆的大小
        n--;
        // 调用shift_down函数，使以0为根的子树满足堆的性质
        shift_down(a, 0, n);
    }
}

shift_down函数

shift_down函数的作用是调整以某个节点为根的子树，使其满足堆的性质。具体的做法是比较该节点和其左右子节点的值，如果该节点的值不满足堆的性质，就和其较大（或较小）的子节点交换，然后递归地调整交换后的子节点为根的子树，直到该节点的值满足堆的性质或者没有子节点为止。这个过程可以用一个递归函数来实现，如下：

// 假设数组a的长度为n，下标从0开始，i是要调整的节点的下标
void shift_down(int a[], int i, int n) 
{
    // 计算左右子节点的下标
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    // 如果左子节点存在，且左子节点的值大于父节点的值（大顶堆的情况）
    if (left < n && a[left] > a[i]) 
    {
        // 交换左子节点和父节点的值
        swap(a, left, i);
        // 递归地调整左子节点为根的子树
        shift_down(a, left, n);
    }
    // 如果右子节点存在，且右子节点的值大于父节点的值（大顶堆的情况）
    if (right < n && a[right] > a[i]) 
    {
        // 交换右子节点和父节点的值
        swap(a, right, i);
        // 递归地调整右子节点为根的子树
        shift_down(a, right, n);
    }
}

swap函数

swap函数的作用是交换数组中两个元素的值。这个函数可以用指针来实现，如下：

// 假设数组a的长度为n，下标从0开始，i和j是要交换的元素的下标
void swap(int a[], int i, int j)
{
    // 定义两个指针，分别指向要交换的元素
    int *p = &a[i];
    int *q = &a[j];
    // 定义一个临时变量，用于存储其中一个元素的值
    int temp;
    // 把p指向的元素的值赋给temp
    temp = *p;
    // 把q指向的元素的值赋给p指向的元素
    *p = *q;
    // 把temp的值赋给q指向的元素
    *q = temp;
}

堆排序的特点

堆排序的特点有以下几点：

堆排序是一种原地排序算法，即不需要额外的空间来存储数据，只需要在原数组上进行操作即可。
堆排序是一种不稳定排序算法，即可能会改变相同元素的相对顺序。例如，如果数组中有两个相同的元素，它们可能会在排序过程中被交换，导致它们的顺序发生变化。
堆排序的时间复杂度为O(nlogn)，即无论数组是有序还是无序，堆排序都需要O(nlogn)的时间来完成排序。这是因为建堆的过程需要O(n)的时间，而每次交换和调整堆的过程需要O(logn)的时间，共需要进行n?1次交换和调整，所以总的时间复杂度为O(nlogn)。
堆排序的空间复杂度为O(1)，即只需要常数个额外的空间来存储临时变量，不需要额外的数组或其他数据结构来辅助排序。

下节以实例来说明如何使用堆排序！

觉得有用的话可以转发给你身边需要的朋友！非常感谢！！！

点赞加关注，学习不迷路

微信公众号｜工控小新

EPLAN电气绘图、TIA博图基础、CAD、C语言教学、单片机基础、三菱PLC ... 每日持续更新中

#记录我的2024#

你可能不知道的C语言排序神器:堆排序

建堆：

排序：

shift_down函数

swap函数

相关文章