排序算法(六)--堆排序

引言

堆排序（Heap Sort）作为一种基于堆数据结构的比较排序算法，以其时间复杂度稳定、实现相对简单而备受青睐。

堆的基本概念

堆是一种特殊的完全二叉树，分为最大堆和最小堆。在最大堆中，每个节点的值都大于或等于其子节点的值；在最小堆中，每个节点的值都小于或等于其子节点的值。堆排序通常使用最大堆来实现升序排序，通过反复将堆顶元素（最大值）与堆末元素交换，并重新调整堆结构，逐步完成排序过程。
堆排序算法步骤
构建最大堆：将待排序数组视为完全二叉树，通过“堆化”过程将其调整为最大堆。堆化是指从最后一个非叶子节点开始，向上至根节点，逐个调整节点位置，确保每个节点都满足最大堆性质。
交换堆顶与堆末元素：将堆顶元素（当前最大值）与堆末元素交换，使最大值移动到数组末尾。此时，堆的有效范围缩小，堆末元素（已排序的最大值）不再参与堆调整。
重新调整堆：对剩余元素继续执行堆化操作，保持最大堆性质。重复步骤2和步骤3，直至堆的有效范围缩小至只剩一个元素，排序完成。

C语言实现

以下是堆排序的C语言实现代码，包括构建最大堆、堆化和堆排序的主要函数：
#include <stdio.h>
// 堆化函数，调整以i为根的子树为最大堆
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) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
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–) {
int swap = arr[0];
arr[0] = arr[i];
arr[i] = swap;
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;
}

代码解析

heapify函数：负责调整以i为根的子树，确保满足最大堆性质。通过比较根节点、左子节点和右子节点的值，找到最大值并交换位置。如果最大值不是根节点，则递归调用heapify函数继续调整。
heapSort函数：首先通过从最后一个非叶子节点开始向上遍历，调用heapify函数构建最大堆。然后，逐个将堆顶元素（最大值）与堆末元素交换，并减小堆的有效范围。对剩余元素继续调用heapify函数，保持最大堆性质，直至排序完成。
printArray函数：用于打印数组内容，方便观察排序前后的变化。
main函数：定义待排序数组，调用heapSort函数进行排序，并打印排序前后的数组内容。

结论

堆排序作为一种高效的排序算法，通过构建最大堆和不断调整堆结构，实现了稳定的排序效果。