C语言堆排序如何高效实现与优化？-C语言-盈思创科技

堆排序是一种高效的、基于比较的排序算法，它的核心思想是利用一种叫做“堆”的数据结构来进行排序，堆排序的时间复杂度为 O(n log n)，并且是原地排序算法，空间复杂度为 O(1)，这使得它非常适合对大规模数据进行排序。

（图片来源网络，侵删）

什么是堆？

在堆排序中,我们通常使用二叉堆，它是一种特殊的完全二叉树。

堆分为两种类型：

大顶堆
- 定义：任何一个父节点的值都大于或等于其所有子节点的值。
- 特性：根节点的值是整个堆中的最大值。
小顶堆
（图片来源网络，侵删）
- 定义：任何一个父节点的值都小于或等于其所有子节点的值。
- 特性：根节点的值是整个堆中的最小值。

堆的数组表示

在计算机中,我们通常使用数组来表示二叉堆，而不是使用指针来构建树节点，对于一个数组 arr，如果它的元素对应一个完全二叉树，那么对于任意节点 i（从 0 开始索引）：

它的父节点索引为：(i - 1) / 2
它的左子节点索引为：2 * i + 1
它的右子节点索引为：2 * i + 2

堆排序的原理

堆排序主要分为两个步骤：

构建初始堆

我们将待排序的数组原地构造成一个大顶堆。

从最后一个非叶子节点开始,向前逐个节点进行“堆化”（Heapify）操作。
为什么从最后一个非叶子节点开始？ 因为叶子节点没有子节点，它们天然满足堆的性质，所以无需调整。
最后一个非叶子节点的索引 是 n/2 - 1（n 是数组长度）。
堆化操作：对于一个节点，如果它比它的子节点小，就将其与最大的子节点交换，然后递归地对交换后的子节点进行同样的操作，直到满足堆的性质。

经过这一步,数组的第一个元素（arr[0]）就是整个数组中的最大值。

排序

将堆顶元素（当前最大值）与堆的最后一个元素交换。
交换后,堆的大小减一（即最后一个元素已经排好序，不再参与堆的调整）。
对新的堆顶元素进行“堆化”操作，以恢复大顶堆的性质。
重复上述过程 1-3，直到堆的大小为 1，整个数组就已经有序了。

这个过程就像是在一个锦标赛中,每次都找出当前的冠军（最大值），把他放到队伍的末尾，然后剩下的选手再重新比赛，直到所有人都排好名次。

C 语言实现

下面是完整的 C 语言堆排序实现，包含了详细的注释。

#include <stdio.h>
// 函数声明
void heapify(int arr[], int n, int i);
void heapSort(int arr[], int n);
void printArray(int arr[], int size);
// 主函数
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: \n");
    printArray(arr, n);
    heapSort(arr, n);
    printf("排序后数组: \n");
    printArray(arr, n);
    return 0;
}
/**
 * @brief 堆化函数
 * @param arr 数组
 * @param n 数组大小（或堆的大小）
 * @param i 需要堆化的节点索引
 */
void heapify(int arr[], int n, int i) {
    // 初始化最大值为当前节点 i
    int largest = i;
    int left = 2 * i + 1;     // 左子节点
    int right = 2 * i + 2;    // 右子节点
    // 如果左子节点存在且大于当前最大值
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    // 如果右子节点存在且大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    // 如果最大值不是父节点 i，则交换
    if (largest != i) {
        // 交换 arr[i] 和 arr[largest]
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        // 交换可能导致子树不满足堆的性质，所以需要递归地对受影响的子树进行堆化
        heapify(arr, n, largest);
    }
}
/**
 * @brief 堆排序主函数
 * @param arr 待排序数组
 * @param n 数组大小
 */
void heapSort(int arr[], int n) {
    // 1. 构建初始大顶堆
    // 从最后一个非叶子节点开始，从下往上，从右往左进行调整
    // 最后一个非叶子节点的索引是 n/2 - 1
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    // 2. 逐个从堆顶取出元素
    // 循环 n-1 次
    for (int i = n - 1; i > 0; i--) {
        // 将当前堆顶元素（最大值）与堆的最后一个元素交换
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        // 交换后，堆的大小减一 (i)
        // 对新的堆顶元素 (索引 0) 进行堆化，以恢复大顶堆
        heapify(arr, i, 0);
    }
}
/**
 * @brief 打印数组
 * @param arr 数组
 * @param size 数组大小
 */
void printArray(int arr[], int size) {
    for (int i = 0; i < size; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

代码执行流程解析：

main 函数：定义一个数组，调用 heapSort 进行排序，并打印排序前后的结果。
heapSort(arr, n)：
- 构建堆：for (int i = n / 2 - 1; i >= 0; i--) 循环从最后一个非叶子节点开始，调用 heapify 向上调整，确保每个子树都满足大顶堆的性质。
- 排序：for (int i = n - 1; i > 0; i--) 循环。
  - arr[0] 和 arr[i] 交换：将最大值放到数组末尾。
  - heapify(arr, i, 0)：对缩小后的堆（大小为 i）的根节点（索引 0）进行堆化，重新恢复大顶堆。
heapify(arr, n, i)：
- 这是核心的调整函数,它假设节点 i 的左右子树都已经是堆，但 arr[i] 可能比其子节点小。
- 它找到 i、left、right 三个节点中的最大值。
- 如果最大值不是 i，则交换它们，并递归地对被交换下去的节点（现在是 largest 位置）进行 heapify，以确保整个子树都满足堆的性质。

复杂度分析

时间复杂度：O(n log n)
- 构建堆：heapify 的时间复杂度是 O(log n)，因为它最多需要从根节点调整到叶子节点，构建堆的过程大约需要调用 heapify n/2 次，所以总时间复杂度是 O(n/2 * log n)，简化后是 O(n)。
- 排序过程：需要进行 n-1 次交换，每次交换后都需要调用一次 heapify，每次 heapify 的时间复杂度是 O(log n)，所以这部分的时间复杂度是 O(n log n)。
- 综合来看,堆排序的总时间复杂度由 O(n) + O(n log n) 决定，最终为 O(n log n)。
空间复杂度：O(1)
- 堆排序是原地排序算法,它只需要一个临时变量用于交换元素，没有使用额外的存储空间，递归的 heapify 函数虽然使用了栈空间，但最大深度为 log n，所以空间复杂度是 O(log n)，但在很多分析中，尤其是在原地排序的语境下，我们通常将其视为 O(1)，因为它没有使用与输入规模 n 成比例的额外空间。

优缺点

优点

高效稳定：时间复杂度为 O(n log n)，在最坏、平均和最好情况下都保持不变，性能非常稳定。
空间效率高：是原地排序，空间复杂度低，尤其适合内存受限的环境。
缓存不友好：相比于快速排序，它的数据访问模式（跳跃访问）不太利于 CPU 缓存，但在某些情况下（如数据量极大时）可能比需要递归栈的快速排序更优。

缺点

不稳定：堆排序是一种不稳定的排序算法，相等元素的相对位置在排序后可能会改变，排序序列 5(1), 5(2), 3，构建堆后可能变成 5(2), 5(1), 3，最终排序结果 3, 5(1), 5(2)，改变了两个 5 的原始顺序。
实现相对复杂：相比于插入排序或选择排序，堆排序的逻辑和实现要稍微复杂一些。
性能常数较大：虽然时间复杂度与快速排序相同，但在实际应用中，堆排序的运行速度通常比快速排序慢，因为其交换和比较操作的次数更多。

堆排序是一种非常重要的排序算法,它巧妙地利用了堆这种数据结构，虽然在实际应用中，快速排序和归并排序可能更常用，但堆排序在需要保证 O(n log n) 最坏时间复杂度和 O(1) 空间复杂度的场景下，是一个非常优秀的选择，堆排序也是实现优先队列等数据结构的基础。

C语言堆排序如何高效实现与优化？