用C语言编写一段堆排序算法

### 回答1：

#include <stdio.h>
int main()
{
int n, i, j, temp;
printf("请输入数组大小: ");
scanf("%d", &n);
int arr[n];
printf("请输入数组元素: ");
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
// 堆排序算法
for (i = n / 2 - 1; i >= 0; i--)
{
// 建立大顶堆：
// 从最后一个非叶子结点arr[i]从左至右，从下至上调整结构
heapify(arr, n, i);
}
// 调整堆结构+交换堆顶元素与末尾元素
for (j = n - 1; j > 0; j--)
{
// 将堆顶元素与末尾元素进行交换
temp = arr[0];
arr[0] = arr[j];
arr[j] = temp;
// 重新对堆进行调整
heapify(arr, j, 0);
}
printf("排序后的数组: ");
printArray(arr, n);

return 0;
}

void heapify(int arr[], int n, int i)
{
int largest = i; // 初始化最大值
int l = 2 * i + 1; // 左子结点
int r = 2 * i + 2; // 右子结点

// 如果左子结点大于父节点
if (l < n && arr[l] > arr[largest])
largest = l;

// 如果右子结点比最大值还大
if (r < n && arr[r] > arr[largest])
largest = r;

// 如果最大值不是父节点，则将父节点与最大值交换
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

// 递归调用，继续从子节点开始heapify
heapify(arr, n, largest);
}
}

// 输出排序后的数组
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
} 答：堆排序是一种采用二叉堆的排序算法，它的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

### 回答2：
堆排序是一种常用的排序算法，其基本思想是将待排序的序列构造成一个大顶堆（或小顶堆），然后依次取出堆顶元素并调整堆，最终得到有序序列。

下面是用C语言编写的堆排序算法：

#include <stdio.h>

// 调整堆
void adjustHeap(int arr[], int i, int n) {
    int temp = arr[i];
    int j = 2 * i + 1; // 左子节点下标
    while (j < n) {
        // 如果右子节点比左子节点大，则取右子节点与父节点比较
        if (j + 1 < n && arr[j] < arr[j + 1]) {
            j++;
        }
        // 如果子节点比父节点大，则交换
        if (arr[j] > temp) {
            arr[i] = arr[j];
            i = j;
            j = 2 * i + 1;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

// 堆排序
void heapSort(int arr[], int len) {
    // 构建大顶堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
    // 调整堆结构，交换顶元素与末尾元素
    for (int i = len - 1; i > 0; i--) {
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        adjustHeap(arr, 0, i);
    }
}

int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int len = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, len);

    printf("排序后的数组：");
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

以上是用C语言编写的堆排序算法。在该算法中，adjustHeap函数用于调整堆，heapSort函数用于执行堆排序，main函数中对一个数组进行堆排序并输出排序后的结果。通过调用heapSort函数，我们可以得到一个按照升序排列的数组。

### 回答3：
堆排序算法是一种对数组元素进行排序的算法。它利用了二叉堆的性质来进行排序。下面是使用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); // 重新调整堆
    }
}

// 测试
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    printf("排序后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

此代码使用了两个主要函数：`heapify`和`heapSort`。`heapify`函数用于调整堆，保持最大堆的性质，而`heapSort`函数用于构建最大堆，并逐步将最大值移到数组的末尾，最终实现堆排序。

对于给定的数组 `[12, 11, 13, 5, 6, 7]`，经过堆排序后，输出结果为 `[5, 6, 7, 11, 12, 13]`。