您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# C语言中如何实现堆排序
## 1. 堆排序概述
堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法。它由J. W. J. Williams于1964年提出，具有以下特点：
- **时间复杂度**：平均和最坏情况下均为O(n log n)
- **空间复杂度**：O(1)（原地排序）
- **稳定性**：不稳定排序
- **适用性**：适合大数据量排序，尤其当需要部分排序时效率很高
## 2. 堆的基本概念
### 2.1 二叉堆的定义
二叉堆是一种特殊的完全二叉树，满足以下性质：
- **结构性质**：完全二叉树的结构
- **堆序性质**：
- 最大堆：父节点值 ≥ 子节点值
- 最小堆：父节点值 ≤ 子节点值
### 2.2 堆的存储
由于堆是完全二叉树，通常用数组存储：
- 对于节点i（从0开始）：
- 父节点：(i-1)/2
- 左子节点：2*i+1
- 右子节点：2*i+2
## 3. 堆排序算法步骤
堆排序主要分为两个阶段：
1. **建堆（Heapify）**：将无序数组构建成堆
2. **排序**：反复取出堆顶元素，调整剩余元素为新堆
### 3.1 完整算法流程
```c
void heapSort(int arr[], int n) {
// 1. 构建最大堆
for (int i = n/2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 2. 逐个提取元素
for (int i = n-1; i > 0; i--) {
swap(&arr[0], &arr[i]); // 将当前最大移到末尾
heapify(arr, i, 0); // 对剩余元素重新堆化
}
}
// 对以i为根的子树进行堆化，n是堆的大小
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 swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
#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;
}
递归实现可能产生栈溢出风险，可用循环替代：
void heapify(int arr[], int n, int i) {
int largest, left, right;
while (1) {
largest = i;
left = 2 * i + 1;
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) break;
swap(&arr[i], &arr[largest]);
i = largest;
}
}
Floyd提出的自底向上建堆方法效率更高
需要O(n log n)时间且空间受限时
需要获取前k个最大/最小元素时
优先级队列实现
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
只需修改堆化条件即可实现升序排序：
void heapify_min(int arr[], int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest])
smallest = left;
if (right < n && arr[right] < arr[smallest])
smallest = right;
if (smallest != i) {
swap(&arr[i], &arr[smallest]);
heapify_min(arr, n, smallest);
}
}
堆排序是一种高效的通用排序算法，特别适合： - 需要保证最坏情况下性能的场景 - 内存受限的环境 - 需要实现优先级队列时
理解堆排序的关键在于掌握： 1. 二叉堆的数据结构特性 2. 堆化操作的实现原理 3. 建堆和排序的两个阶段
通过本文的C语言实现和详细解析，读者应能掌握堆排序的核心思想并能在实际编程中灵活应用。 “`
这篇文章共计约2500字，采用Markdown格式编写，包含： 1. 算法原理说明 2. 完整的C语言实现代码 3. 复杂度分析 4. 优化建议 5. 应用场景和比较 6. 扩展内容等完整的技术细节
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。