如何用c语言输出堆排序的过程

堆排序是一种基于比较的排序算法，它通过构建并维护一个大顶堆来进行操作。以下是使用C语言描述堆排序的基本过程：

1. **建堆**：
- 首先将待排序数组看作是一个完全二叉树，从最后一个非叶子节点开始（即最后一个元素的父节点），对每个非叶子节点执行下沉（heapify）操作，确保该节点及其子树满足堆的性质（父节点值大于等于子节点值）。

2. **调整堆**：
- 对整个数组进行调整，使其变成一个最大堆，此时根节点是最大的元素。这个步骤完成后，数组的第一个元素就是最大值。

3. **交换并缩小堆**：
- 将堆顶的最大元素与末尾元素交换位置，然后删除最后一个元素。这时，数组的最后一个元素已经是排序好的，然后重新调整剩余元素构成的新堆。

4. **重复调整**：
- 重复上述步骤，每次调整后，堆的大小减一，直到调整到只剩一个元素为止。此时数组就已完全有序。

以下是堆排序的一个简化的伪代码示例：

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);     // 调整剩余堆
    }
}