堆排序从入门到精通（C语言堆排序算法详解）

堆排序的基本思想

堆排序分为两个主要阶段：

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

C语言实现堆排序

下面我们用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 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--) {        // 将当前最大值（堆顶）移到末尾        int temp = arr[0];        arr[0] = arr[i];        arr[i] = temp;        // 对剩余元素重新调整堆        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;}

时间复杂度分析

堆排序的时间复杂度为 O(n log n)，无论最好、最坏还是平均情况都是如此。空间复杂度为 O(1)，属于原地排序算法。

为什么学习堆排序？

掌握数据结构堆排序不仅有助于理解高级算法（如优先队列），还能提升你在面试和实际开发中的问题解决能力。与其他 O(n log n) 排序算法（如快速排序）相比，堆排序具有更稳定的时间性能。

总结

通过本教程，你已经学会了如何用C语言实现堆排序。堆排序虽然不如快速排序在实践中常用，但其稳定的时间复杂度和对内存的高效利用使其在特定场景下非常有价值。建议你动手运行上述代码，加深理解。

关键词回顾：C语言堆排序、堆排序算法详解、数据结构堆排序、C语言实现堆排序。