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

C语言实现堆排序（附带源码）

news 2026/5/12 5:45:11

一、项目背景详细介绍

排序算法是数据结构与算法的基础内容，在众多排序算法中，堆排序（Heap Sort）以其稳定的时间复杂度、良好的工程可用性与结构化的逻辑，成为工业界和学术界广泛使用的排序技术。

堆排序基于完全二叉树结构与堆（heap）数据结构，通过构建最大堆（或最小堆）来完成排序。相比冒泡排序、选择排序等 O(n²) 算法，堆排序在最优、平均、最坏情况下均保持 O(n log n) 的优秀表现，使其特别适用于大数据量的场景。

本项目旨在：

用 C 语言实现堆排序完整流程
手写最大堆构建函数
实现堆调整（heapify）过程
实现堆排序
详细分析核心原理结构
给出万字级教学讲解

并严格符合你的博客专用模板。

本项目非常适合作为大学数据结构课程的实验报告、个人博客技术文章、公司内部培训文档等。

二、项目需求详细介绍

堆排序项目要求如下：

（1）排序功能要求

输入一个数组
建立最大堆
通过“堆顶元素与末尾交换 + 调整堆”逐步排序
输出排序后的结果

堆排序返回结果应为升序序列。

（2）核心技术要求

手动实现 buildMaxHeap
手动实现 heapify（堆调整）
手动实现 heapSort
不允许调用库函数排序

（3）边界情况处理

数组为空
数组仅一个元素
数组中包含重复元素
大量数据时保持稳定性能

（4）复杂度要求

输出时间复杂度与空间复杂度分析。

三、相关技术详细介绍

堆排序由以下关键技术构成：

（1）完全二叉树结构

堆是基于数组实现的完全二叉树，满足：

index=0：根节点
左子节点 = 2*i + 1
右子节点 = 2*i + 2

由于结构连续，堆不需要指针，数组即可表示。

（2）最大堆性质

最大堆需满足：

任意节点值 ≥ 子节点值
堆顶元素（索引 0）是最大值

（3）堆调整（heapify）

保证单个节点能正确下沉到堆中合适位置，维护最大堆性质。

（4）建堆（buildMaxHeap）

从最后一个非叶子结点开始往前调整，使整个数组成为最大堆。

（5）堆排序

重复执行：

交换堆顶（最大值）与堆末尾
缩小堆范围
重新 heapify

最终实现升序排序。

四、实现思路详细介绍

堆排序逻辑如下：

（1）构建最大堆

从最后一个非叶子节点开始，依次向前调用 heapify：

for (i = n/2 - 1; i >= 0; i--) heapify(arr, n, i)

（2）排序过程

交换堆顶与最后元素，使最大值移到末尾：

swap(arr[0], arr[i]) heapify(arr, i, 0)

通过不断缩小堆的有效长度 i，实现整个数组排序。

（3）最终得到升序数组

这是因为每次都把最大值放到了数组末尾。

五、完整实现代码

/************************************** * 文件：heap.h **************************************/ #ifndef HEAP_H #define HEAP_H #include <stdio.h> #include <stdlib.h> void heapify(int arr[], int n, int i); void buildMaxHeap(int arr[], int n); void heapSort(int arr[], int n); void printArray(int arr[], int n); #endif /************************************** * 文件：heap.c **************************************/ #include "heap.h" // 堆调整函数（最大堆） // arr[]：数组 // n：堆的有效长度 // 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 temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; // 递归调整子树 heapify(arr, n, largest); } } // 建立最大堆 void buildMaxHeap(int arr[], int n) { // 最后一个非叶子节点 = n/2 - 1 for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); } // 堆排序流程 void heapSort(int arr[], int n) { // 第一步：建堆 buildMaxHeap(arr, n); // 第二步：不断把堆顶最大值放到数组末尾 for (int i = n - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 调整缩小后的堆 heapify(arr, i, 0); } } // 打印数组 void printArray(int arr[], int n) { for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); } /************************************** * 文件：main.c **************************************/ #include "heap.h" int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: "); printArray(arr, n); heapSort(arr, n); printf("堆排序后: "); printArray(arr, n); return 0; }