怎样在 C 语言中实现堆排序？

🍅关注博主🎗️ 带你畅游技术世界，不错过每一次成长机会！
📙C 语言百万年薪修炼课程 【https://dwz.mosong.cc/cyyjc】通俗易懂，深入浅出，匠心打磨，死磕细节，6年迭代，看过的人都说好。

C 语言中的堆排序实现

一、堆排序的基本概念

堆排序（Heap Sort）是利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

在堆排序中，我们通常使用最大堆来进行排序。最大堆的每个父节点的值都大于或等于其子节点的值。

二、堆排序的基本原理

堆排序的基本思想是：首先将待排序的数组构建成一个最大堆，然后将堆顶元素（最大值）与堆的最后一个元素交换位置，此时最大值就处于正确的位置（数组的末尾）。接下来，将剩余的元素重新调整为最大堆，再将堆顶元素与当前堆的最后一个未排序元素交换位置，重复这个过程，直到整个数组排序完成。

三、堆排序的步骤

1. 构建最大堆

   • 从最后一个非叶子节点开始，依次向前调整每个节点及其子树，使其满足最大堆的性质。

2. 交换堆顶和末尾元素

   • 将堆顶元素与堆的最后一个元素交换位置。

3. 调整剩余堆为最大堆

   • 对除了已排序的末尾元素外的剩余元素重新调整为最大堆。

4. 重复步骤 2 和 3，直到整个数组排序完成

四、C 语言实现堆排序

以下是一个用 C 语言实现堆排序的示例代码：

#include <stdio.h>

// 交换函数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 维护最大堆的性质
void maxHeapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest!= i) {
        swap(&arr[i], &arr[largest]);
        maxHeapify(arr, n, largest);
    }
}

// 构建最大堆
void buildMaxHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        maxHeapify(arr, n, i);
}

// 堆排序函数
void heapSort(int arr[], int n) {
    buildMaxHeap(arr, n);

    for (int i = n - 1; i >= 0; i--) {
        swap(&arr[0], &arr[i]);
        maxHeapify(arr, i, 0);
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 测试示例
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组为: ");
    printArray(arr, n);

    heapSort(arr, n);

    printf("排序后的数组为: ");
    printArray(arr, n);

    return 0;
}

在上述代码中，我们定义了以下几个函数：

• swap 函数用于交换两个整数的位置。
• maxHeapify 函数用于维护最大堆的性质。它接受一个数组、数组的长度和要调整的节点索引作为参数。通过比较节点与其子节点的值，将最大值交换到父节点的位置，并对可能受到影响的子树递归调用 maxHeapify 函数。
• buildMaxHeap 函数用于构建最大堆。从最后一个非叶子节点开始，依次调用 maxHeapify 函数，确保整个数组满足最大堆的性质。
• heapSort 函数是堆排序的核心函数。首先调用 buildMaxHeap 构建最大堆，然后通过不断交换堆顶元素和末尾元素，并对剩余元素重新调整为最大堆，实现排序。
• printArray 函数用于打印数组的元素。

在 main 函数中，我们创建了一个测试数组，调用 heapSort 函数对其进行排序，并打印排序前后数组的元素。

五、代码解释

1. swap 函数

   • 这个函数通过一个临时变量 temp 来实现两个整数的交换。

2. maxHeapify 函数

   • 首先，确定当前节点 i 的左右子节点的索引 l 和 r 。
   • 然后，找出 i、l 和 r 中值最大的节点索引，并存储在 largest 变量中。
   • 如果最大的值不在当前节点 i ，则将最大的值与当前节点交换位置，并对交换后的子树递归调用 maxHeapify 函数，以确保子树也满足最大堆的性质。

3. buildMaxHeap 函数

   • 从最后一个非叶子节点开始，通过循环调用 maxHeapify 函数来构建最大堆。最后一个非叶子节点的索引为 n / 2 - 1 。

4. heapSort 函数

   • 首先调用 buildMaxHeap 函数构建最大堆。
   • 然后通过一个循环，每次将堆顶元素与末尾未排序的元素交换位置，并对剩余的元素调用 maxHeapify 函数重新调整为最大堆。

六、时间复杂度和空间复杂度分析

1. 时间复杂度

   • 堆排序的时间复杂度为 O(nlogn) 。其中，构建最大堆的时间复杂度为 O(n) ，每次调整最大堆的时间复杂度为 O(logn) ，在排序过程中需要进行 n - 1 次调整，所以总的时间复杂度为 O(nlogn) 。

2. 空间复杂度

   • 堆排序的空间复杂度为 O(1) 。因为整个排序过程只在原数组上进行操作，没有额外的空间开销。

七、堆排序的优点和缺点

1. 优点

   • 堆排序在最坏情况下的时间复杂度仍然为 O(nlogn) ，性能较为稳定。
   • 是一种原地排序算法，不需要额外的存储空间，空间复杂度低。

2. 缺点

   • 堆排序的性能在实际应用中通常比快速排序稍逊一筹。
   • 构建堆的过程相对较为复杂，理解和实现起来有一定难度。

八、应用场景

堆排序适用于对时间复杂度要求较高，且对空间复杂度有限制的场景，例如在嵌入式系统或资源受限的环境中。

九、与其他排序算法的比较

1. 与冒泡排序相比

   • 冒泡排序的时间复杂度为 O(n^2) ，而堆排序的时间复杂度为 O(nlogn) ，在大多数情况下，堆排序的性能优于冒泡排序。

2. 与快速排序相比

   • 快速排序在平均情况下的性能非常出色，时间复杂度也为 O(nlogn) 。但在最坏情况下，快速排序的时间复杂度可能退化为 O(n^2) ，而堆排序在最坏情况下仍然保持 O(nlogn) 的时间复杂度。

3. 与归并排序相比

   • 归并排序的时间复杂度和堆排序相同，均为 O(nlogn) ，但归并排序需要额外的辅助空间，空间复杂度为 O(n) ，而堆排序是原地排序，空间复杂度为 O(1) 。

十、总结

堆排序是一种高效的排序算法，通过构建最大堆和不断交换堆顶元素与末尾元素来实现排序。虽然在实际应用中可能不如快速排序等算法常用，但在特定的场景下，如对空间要求严格的环境中，具有一定的优势。理解和掌握堆排序的原理和实现对于深入理解算法和数据结构的知识体系具有重要意义。

🎉相关推荐

• 📙C 语言百万年薪修炼课程 【https://dwz.mosong.cc/cyyjc】 通俗易懂，深入浅出，匠心打磨，死磕细节，6年迭代，看过的人都说好。
• 🍅博客首页-关注博主🎗️ 带你畅游技术世界，不错过每一次成长机会！
• 📙CSDN专栏-C语言修炼
• 📙技术社区-墨松科技