编辑代码

#include <stdio.h>

// 堆排序算法
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);
    }
}

// 对以 index 为根节点的子树进行堆调整
void heapify(int arr[], int n, int index) {
    int maxVal = index;      // 子树中的最大值位置
    int left = index * 2 + 1;    // 左儿子节点索引
    int right = index * 2 + 2;    // 右儿子节点索引

    // 找到子树中的最大值
    if (left < n && arr[left] > arr[maxVal])
        maxVal = left;
    if (right < n && arr[right] > arr[maxVal])
        maxVal = right;

    // 如果最大值不是根节点，交换根节点和最大值位置的节点，并继续调整子树
    if (maxVal != index) {
        int temp = arr[maxVal];
        arr[maxVal] = arr[index];
        arr[index] = temp;

        heapify(arr, n, maxVal);
    }
}

// 测试
int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("排序前: \n");
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);


    heapSort(arr, n);

    printf(" \n排序后: \n");
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);

    return 0;
}