当前位置：首页 > C++ > 正文

C++堆排序算法详解（从零开始掌握堆排序的完整实现）

主机测评网
C++
2025-12-14
543

在计算机科学中，堆排序是一种高效的比较类排序算法，它利用了堆这种数据结构的特性。本教程将手把手教你如何用C++语言实现堆排序算法，即使你是编程小白，也能轻松理解并掌握！

什么是堆？

堆是一种特殊的完全二叉树，分为两种：

最大堆（Max Heap）：父节点的值总是大于或等于其子节点的值。
最小堆（Min Heap）：父节点的值总是小于或等于其子节点的值。

堆排序通常使用最大堆来实现升序排序。

C++堆排序算法详解（从零开始掌握堆排序的完整实现） C++堆排序算法堆排序实现 C++排序教程数据结构堆排序第1张

堆排序的基本思想

堆排序主要分为两个步骤：

建堆（Heapify）：将无序数组构造成一个最大堆。
排序：重复地将堆顶元素（最大值）与末尾元素交换，并缩小堆的范围，然后重新调整堆结构。

C++堆排序算法实现

下面我们用C++一步步实现堆排序。整个过程包括两个核心函数：

heapify()：用于维护堆的性质
heapSort()：主排序函数

#include <iostream>#include <vector>// 维护最大堆的性质void heapify(std::vector<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) {        std::swap(arr[i], arr[largest]);        heapify(arr, n, largest); // 递归堆化受影响的子树    }}// 堆排序主函数void heapSort(std::vector<int>& arr) {    int n = arr.size();    // 第一步：构建最大堆（从最后一个非叶子节点开始）    for (int i = n / 2 - 1; i >= 0; i--)        heapify(arr, n, i);    // 第二步：逐个提取元素    for (int i = n - 1; i > 0; i--) {        // 将当前最大值（堆顶）移到末尾        std::swap(arr[0], arr[i]);        // 对剩余元素重新堆化        heapify(arr, i, 0);    }}// 打印数组void printArray(const std::vector<int>& arr) {    for (int num : arr)        std::cout << num << " ";    std::cout << std::endl;}// 主函数测试int main() {    std::vector<int> arr = {12, 11, 13, 5, 6, 7};    std::cout << "原始数组: ";    printArray(arr);    heapSort(arr);    std::cout << "排序后数组: ";    printArray(arr);    return 0;}