首页 > 编程笔记 > 算法

C语言堆排序（附带源码和解析）

堆排序是一种高效的比较排序算法，它利用堆这种数据结构来进行排序。堆排序的平均时间复杂度为 O(n log n)，其中 n 是待排序元素的数量。这种排序算法不仅效率高，而且具有原地排序的特点，即不需要额外的存储空间。

堆排序的基本思想

在开始讲解堆排序之前，我们需要先理解什么是堆。堆是一种特殊的完全二叉树，它满足以下性质：


在堆排序中，我们通常使用大顶堆,大顶堆的根节点是整个堆中的最大值。


堆排序的核心思想是利用堆的特性来进行排序，具体步骤如下：

  1. 将待排序的数组构建成一个大顶堆；
  2. 将堆顶元素（最大值）与数组末尾元素交换；
  3. 将剩余的 n-1 个元素重新构建成大顶堆；
  4. 重复步骤 2 和 3，直到整个数组有序。

堆排序的详细过程

1) 构建大顶堆

构建大顶堆是堆排序的关键步骤。我们从最后一个非叶子节点开始，自下而上地进行堆化操作。堆化操作确保每个父节点的值都大于或等于其子节点的值。


假设我们有一个数组 [4, 10, 3, 5, 1]，我们需要将其构建成一个大顶堆：

初始数组：    4  10  3  5  1
索引：        0   1  2  3  4

步骤 1：从最后一个非叶子节点（索引 1）开始堆化
        10  4  3  5  1
         |  |
         |  |
        10  5  3  4  1

步骤 2：继续堆化根节点（索引 0）
        10  5  3  4  1
         |
         |
        10  5  3  4  1 （已经是大顶堆）

2) 堆排序过程

构建好大顶堆后，我们开始进行排序：

初始大顶堆：  10  5  3  4  1

步骤 1：交换堆顶元素和末尾元素，并重新堆化
         1  5  3  4 | 10
         |
         |
         5  1  3  4 | 10
        
步骤 2：继续交换和堆化
         4  1  3 | 5  10
         |
         |
         4  1  3 | 5  10

步骤 3：重复过程
         3  1 | 4  5  10
         |
         |
         3  1 | 4  5  10

步骤 4：最后一次交换
         1 | 3  4  5  10

排序完成：    1  3  4  5  10

C语言实现堆排序

下面是堆排序的 C 语言实现：

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int arr[], int n, int 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;

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

void heapSort(int arr[], int n) {
    // 构建大顶堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 一个个从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

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;
}

运行结果：

原始数组:
12 11 13 5 6 7
排序后数组:
5 6 7 11 12 13

堆排序的性能和优缺点

堆排序的时间复杂度在各种情况下都是 O(n log n)，这使得它成为一种稳定且高效的排序算法。堆排序的空间复杂度为 O(1)，因为它是原地排序算法，不需要额外的存储空间。


堆排序的优点包括：


堆排序的缺点包括：


堆排序是一种高效的排序算法，它巧妙地利用了堆这种数据结构的特性，通过构建大顶堆并不断交换堆顶元素与末尾元素，我们可以得到一个有序的序列。

堆排序的实现虽然看起来较为复杂，但其核心思想是简洁而优雅的。在实际应用中，堆排序常用于大数据量的排序，以及实现优先队列等数据结构。


你可能还想关注其它 9 种排序算法：

  1. C语言冒泡排序（附带源码和解析）
  2. C语言快速排序（附带源码和解析）
  3. C语言选择排序（附带源码和解析）
  4. C语言插入排序（附带源码和解析）
  5. C语言希尔排序（附带源码和解析）
  6. C语言归并排序（附带源码和解析）
  7. C语言计数排序（附带源码和解析）
  8. C语言桶排序（附带源码和解析）
  9. C语言基数排序（附带源码和解析）

声明：《算法系列教程》为本站“54笨鸟”官方原创，由国家机构和地方版权局所签发的权威证书所保护。

相关文章

精选内容