C语言编写堆排序_堆排序代码c语言

堆排序是一种常见的排序算法，它可以通过使用堆这种数据结构来实现较快的排序。

堆是一种完全二叉树，它有两个特性：

1. 父节点的值大于等于（或小于等于）它的子节点的值，这种特性被称为堆属性；
2. 在堆中，除了根节点之外，所有节点的父节点和子节点之间不存在任何特别的关系。

堆排序的基本思想是：将待排序的数组构建成一个大顶堆（或小顶堆），然后将堆顶元素取出来放到数组的末尾，然后再对剩余的元素进行堆重构，重复进行此操作直到排序完成。

具体步骤如下：

1. 构建大顶堆：将待排序的数组视为一棵完全二叉树，并从最后一个非叶子节点开始，逐个进行堆调整，以满足堆属性；
2. 将堆顶元素取出，将其与数组末尾元素交换位置，并将堆的长度减1；
3. 对除堆顶元素外的元素进行堆重构，重复步骤2和步骤3，直到堆的长度为1。

以下是堆排序的C语言完整代码：

#include <stdio.h>
 
/* 堆排序函数 */
void heap_sort(int arr[], int n) {
    int i, temp;
    /* 构建最大堆 */
    for (i = n/2-1; i >= 0; i--) {
        max_heapify(arr, i, n);
    }
    /* 依次将每个最大元素放到数组末尾 */
    for (i = n-1; i >= 1; i--) {
        /* 将堆顶元素与当前堆的末尾元素交换位置 */
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        /* 对剩余元素重新构建最大堆 */
        max_heapify(arr, 0, i);
    }
}
 
/* 对以i为根节点的子树进行最大堆化 */
void max_heapify(int arr[], int i, int n) {
    int j, temp;
    temp = arr[i];
    j = 2 * i + 1;
    while (j < n) {
        /* 找到左右子节点中较大的那个 */
        if (j+1 < n && arr[j+1] > arr[j]) {
            j++;
        }
        /* 如果父节点比左右子节点中最大的还要大，则不需要继续调整 */
        if (temp >= arr[j]) {
            break;
        }
        /* 将父节点和左右子节点中最大的那个交换位置 */
        arr[i] = arr[j];
        i = j;
        j = 2 * i + 1;
    }
    /* 将原来的根节点放到正确的位置 */
    arr[i] = temp;
}
 
/* 主函数用于测试 */
int main() {
    int arr[] = {5, 2, 8, 3, 1, 6, 9, 7, 4};
    int n = sizeof(arr) / sizeof(int);
    printf("Before sorting: ");
    print_arr(arr, n);
    heap_sort(arr, n);
    printf("After sorting: ");
    print_arr(arr, n);
    return 0;
}
 
/* 打印数组元素的函数 */
void print_arr(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

在这个代码中，主要的排序算法函数是堆排序函数heap_sort。该函数首先通过构建最大堆来将数组排序。然后，依次将每个最大元素放到数组末尾并对剩余元素重新构建最大堆。在构建最大堆的过程中，使用了最大堆化函数max_heapify来对每个子树进行最大堆化。最后，通过主函数调用堆排序函数heap_sort来测试排序算法的效果。

堆排序的时间复杂度为O(nlogn)，其中n为待排序数组的长度。由于堆排序每次取出堆顶元素后都要进行堆重构，因此它不适用于小数据量的排序。但是，堆排序的空间复杂度为O(1)，因此它在空间有限的情况下非常适用。