给定数组 ［4，7，2，9，5］，用堆排序将其从小到大排序，并说明时间复杂度的推导过程。用c语言输出

给定数组 [4, 7, 2, 9, 5]，我们可以使用堆排序算法进行从小到大的排序。堆排序是一种利用二叉堆数据结构的排序算法，它的时间复杂度通常分为两个部分：

1. 构建最大堆（Heapify）：从最后一个非叶子节点开始，向上调整堆，保证每个节点都大于其子节点。这个过程需要O(n)时间，因为有n/2个节点需要调整。

2. 主循环（Sort）：反复取出堆顶元素（当前最大值），放到数组的末尾，然后将剩余元素重新调整成堆。这个过程会重复n次，每次调整堆需要调整log_2(n)次。因此，主循环总共需要O(n log_2(n))次。

总的时间复杂度 = 构建最大堆的时间 + n次主循环的时间 = O(n) + n * O(log_2(n)) = O(n log_2(n))

以下是使用 C 语言实现堆排序的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义堆的最大容量
#define MAX_SIZE 5

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]);

        // 对剩下的n-1个元素重新heapify
        heapify(arr, i, 0);
    }
}

// 交换数组中的两个元素
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

// 测试函数
int main() {
    int arr[] = {4, 7, 2, 9, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before sorting: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    heapSort(arr, n);

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

    return 0;
}

当你运行这段代码时，它会按照升序打印出排序后的数组：2 4 5 7 9。