堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法。它通过构建一个最大堆（或最小堆）来实现排序，具有时间复杂度为O(n log n)的特点，适用于大规模数据的排序。本文将详细介绍堆排序的原理，并通过C语言代码示例进行分析。
二叉堆是一种特殊的完全二叉树，它满足以下性质： - 最大堆：每个节点的值都大于或等于其子节点的值。 - 最小堆：每个节点的值都小于或等于其子节点的值。
堆排序通常使用最大堆来实现升序排序。
堆排序的主要步骤如下： 1. 构建最大堆：将待排序的数组构建成一个最大堆。 2. 交换堆顶元素：将堆顶元素（最大值）与数组的最后一个元素交换，然后将剩余的元素重新调整为最大堆。 3. 重复步骤2：重复上述过程，直到所有元素都排序完成。
计算
安全
数据库
网络和加速
企业服务
#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);
}
}
// 打印数组
void printArray(int arr[], int n) {
for (int i = 0; i < n; 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;
}
原始数组:
12 11 13 5 6 7
排序后的数组:
5 6 7 11 12 13
堆排序的时间复杂度为O(n log n)，且它是一种原地排序算法，不需要额外的存储空间。
堆排序是一种高效的排序算法，尤其适用于大规模数据的排序。通过构建最大堆并不断调整堆结构，堆排序能够在O(n log n)的时间复杂度内完成排序任务。本文通过C语言代码示例详细介绍了堆排序的实现过程，并分析了其时间复杂度。希望本文能帮助读者更好地理解堆排序的原理和应用。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
