#include <stdio.h>
// 交换两个元素的值
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 堆化函数，维护堆的性质
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);
}
}
// 打印数组函数
void printArray(int arr[], int size) {
for (int i = 0; i < size; i )
printf("%d ", arr[i]);
printf("n");
}
// 主函数
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("未排序的数组: n");
printArray(arr, n);
heapSort(arr, n);
printf("排序后的数组: n");
printArray(arr, n);
return 0;
}
代码解释
交换函数swap：
用于交换两个元素的值。
堆化函数heapify：
维护堆的性质，将当前节点及其子树调整为最大堆。
比较当前节点、左子节点和右子节点的值，找到最大值并交换。
递归调整子树，确保整个树满足堆的性质。
堆排序函数heapSort：
首先将数组构建为最大堆。
逐个将最大值（根节点）移动到数组末尾，并调整剩余部分为最大堆。
打印数组函数printArray：
遍历数组并打印每个元素，便于查看排序结果。
主函数main：
初始化一个整数数组并计算其大小。
调用heapSort函数对数组进行排序。
打印排序前后的数组。
堆排序的优化
尽管堆排序的基本实现已经相对高效，但仍有一些优化方法可以进一步提升其性能：
优化堆化过程：
在堆化过程中，使用非递归方法代替递归方法可以减少函数调用的开销。
优化代码示例：
代码语言：javascript复制
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i 1;
int right = 2 * i 2;
while (left < n) {
if (arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
i = largest;
left = 2 * i 1;
right = 2 * i 2;
} else {
break;
}
}
}
