C语言堆排序详解（从零开始掌握堆排序算法）

堆排序的基本思想

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

1. 建堆：将无序数组构造成一个最大堆。
2. 排序：重复将堆顶（最大值）与堆尾元素交换，并缩小堆的范围，重新调整堆结构，直到整个数组有序。

C语言实现堆排序

下面我们用 C语言实现堆排序，代码包含三个核心函数：

• heapify：维护堆的性质
• buildMaxHeap：构建最大堆
• heapSort：执行堆排序

// 堆排序完整C语言实现#include <stdio.h>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) {        int temp = arr[i];        arr[i] = arr[largest];        arr[largest] = temp;        heapify(arr, n, largest); // 递归堆化受影响的子树    }}void buildMaxHeap(int arr[], int n) {    // 从最后一个非叶子节点开始向上堆化    for (int i = n / 2 - 1; i >= 0; i--)        heapify(arr, n, i);}void heapSort(int arr[], int n) {    buildMaxHeap(arr, n); // 第一步：构建最大堆    // 第二步：逐个提取堆顶元素    for (int i = n - 1; i > 0; i--) {        // 将堆顶（最大值）移到末尾        int temp = arr[0];        arr[0] = arr[i];        arr[i] = temp;        // 对剩余元素重新堆化        heapify(arr, i, 0);    }}int main() {    int arr[] = {12, 11, 13, 5, 6, 7};    int n = sizeof(arr) / sizeof(arr[0]);    printf("原始数组: ");    for (int i = 0; i < n; i++)        printf("%d ", arr[i]);    heapSort(arr, n);    printf("\n排序后数组: ");    for (int i = 0; i < n; i++)        printf("%d ", arr[i]);    return 0;}  

代码解析

1. heapify 函数：确保以索引 i 为根的子树满足最大堆性质。

2. buildMaxHeap 函数：从最后一个非叶子节点（即 n/2 - 1）开始，自底向上调用 heapify，构建整个最大堆。

3. heapSort 函数：先建堆，然后不断将堆顶元素与末尾交换，并缩小堆范围，重新堆化，最终得到升序数组。

时间与空间复杂度

• 时间复杂度：O(n log n) —— 建堆 O(n)，每次调整 O(log n)，共 n 次。
• 空间复杂度：O(1) —— 原地排序，仅使用常量额外空间。

总结

通过本教程，你已经掌握了 C语言堆排序 的核心原理与实现方法。堆排序是一种稳定、高效的排序算法，适用于对性能要求较高的场景。无论你是学习 数据结构堆排序，还是准备面试，掌握堆排序都是必不可少的技能！

动手试试吧！修改数组内容，观察排序结果，加深理解。祝你编程愉快！