堆排序排序的原理详解与 C 语言实现

堆排序（Heap Sort）是一种基于堆这种数据结构的比较排序算法。堆是一种特殊的完全二叉树结构，分为最大堆和最小堆。最大堆中每个节点的值都大于或等于其子节点的值，最小堆中每个节点的值都小于或等于其子节点的值。

堆排序的主要步骤如下：

构建最大堆：将无序数组构建成最大堆。
堆排序：将堆顶元素（最大值）与末尾元素交换，然后将剩余元素重新调整为最大堆，重复此过程直到排序完成。

堆排序的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;
}

代码解释

交换函数 swap：用于交换数组中两个元素的值。
调整堆函数 heapify：用于调整以某个节点为根的子树，使其满足堆的性质。该函数首先假设子树已经是堆，只需要将根节点向下调整。
主堆排序函数 heapSort：首先构建最大堆，然后逐个将堆顶元素（最大值）与末尾元素交换，并调整剩余元素为堆。
打印数组函数 printArray：用于输出数组的内容。
测试函数 main：包含一个示例数组，演示堆排序前后的结果。

总结

堆排序是一种高效的排序算法，其时间复杂度为O(n log n)。由于堆排序使用了堆这种数据结构，适用于需要频繁获取最值的场景。通过本文的讲解和代码示例，希望大家能对堆排序有更深入的理解。