当前位置：首页 > ops >正文

算法笔记之堆排序

ops 2025/7/23 13:29:42

本系列可作为算法学习系列的笔记，小编会将代码记录下来，大家复制下来就可以练习了，方便大家学习。小编作为新晋码农一枚，会定期整理一些写的比较好的代码，作为自己的学习笔记，会试着做一下批注和补充，如转载或者参考他人文献会标明出处，非商用，如有侵权会删改！欢迎大家斧正和讨论！

系列文章目录

计算矩阵的鞍点个数

算法-比较排序

为什么比较排序算法的时间复杂度下界是 Ω(n log n)？

算法笔记之堆排序

一. 堆排序（Heap Sort）

堆排序是一种高效的排序算法，它利用了二叉堆这种数据结构来实现。堆排序的时间复杂度为O(nlogn)，且是原地排序算法（不需要额外的存储空间）。

1.堆的基本概念

堆是一种特殊的完全二叉树，满足以下性质：

最大堆：每个节点的值都大于或等于其子节点的值
最小堆：每个节点的值都小于或等于其子节点的值

在堆排序中，我们通常使用最大堆。

2.堆排序的基本步骤

建堆（Heapify）：将无序数组构建成一个堆
排序：
- 将堆顶元素（最大值）与最后一个元素交换
- 缩小堆的范围（排除最后一个元素）
- 对新的堆顶元素进行堆调整（Heap Adjust）
- 重复上述过程直到堆的大小为1

3.C语言实现代码

#include <stdio.h>// 交换两个元素的值
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 堆调整函数（下沉操作）
// arr: 待调整的数组
// n: 数组长度
// i: 当前需要调整的节点下标
void heapAdjust(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]);heapAdjust(arr, n, largest);  // 递归调整受影响的子树}
}// 建堆函数
void buildHeap(int arr[], int n) {// 从最后一个非叶子节点开始，向上调整for (int i = n / 2 - 1; i >= 0; i--) {heapAdjust(arr, n, i);}
}// 堆排序函数
void heapSort(int arr[], int n) {// 1. 构建最大堆buildHeap(arr, n);// 2. 逐个提取元素for (int i = n - 1; i > 0; i--) {// 将当前最大值（堆顶）移动到数组末尾swap(&arr[0], &arr[i]);// 对剩余元素重新调整堆heapAdjust(arr, i, 0);}
}// 测试代码
int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");heapSort(arr, n);printf("排序后数组: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}