堆排序

堆排序（Heap Sort）是一种常见的排序算法，基于二叉堆数据结构进行实现，具有稳定性、时间复杂度为O(nlogn)的特点。

堆可以看成是一棵完全二叉树，分为大根堆和小根堆两种。在大根堆中，父节点的值总是大于或等于其子节点的值，而在小根堆中，父节点的值总是小于或等于其子节点的值。在进行排序时，通常使用大根堆来升序排列，使用小根堆来降序排列。

堆排序的基本思想是将待排序的序列构建成一个大根堆或小根堆，然后依次将堆顶元素（即最大值或最小值）与序列的最后一个元素交换，并将剩余元素重新构建成一个堆，重复执行以上操作直到整个序列有序为止。

以下是堆排序的C语言实现示例：

#include <stdio.h>

// 交换两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 调整大根堆
void adjust_heap(int arr[], int start, int end) {
    int dad = start;
    int son = 2 * dad + 1; // 左孩子节点
    while (son <= end) {
        if (son + 1 <= end && arr[son] < arr[son + 1]) {
            son++;
        }
        if (arr[dad] >= arr[son]) {
            return;
        } else {
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = 2 * dad + 1;
        }
    }
}

// 堆排序
void heap_sort(int arr[], int len) {
    // 构建大根堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjust_heap(arr, i, len - 1);
    }
    // 取出堆顶元素，放入已排序的数组中，重复构建堆的过程
    for (int i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        adjust_heap(arr, 0, i - 1);
    }
}

// 测试
int main() {
    int arr[] = {3, 1, 5, 7, 2, 4, 9, 6, 8};
    int len = sizeof(arr) / sizeof(arr[0]);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

该示例代码实现了堆排序的过程，首先构建大根堆，然后每次取出堆顶元素，放入已排序的数组中，重复这个过程直到所有元素都被取出，最终得到排好序的数组。