c++中如何堆排序_c++堆排序实现方法-C++-PHP中文网

c++中如何堆排序_c++堆排序实现方法

尼克

发布： 2025-10-05 23:05:02

原创

316人浏览过

堆排序通过构建最大堆实现，首先从最后一个非叶子节点开始向下调整，确保父节点大于子节点，然后将堆顶最大值与末尾交换并缩小堆范围，重复此过程直至有序；时间复杂度O(n log n)，空间复杂度O(1)。

c++中如何堆排序_c++堆排序实现方法

堆排序是一种基于比较的排序算法，利用二叉堆的数据结构来实现。在C++中实现堆排序，核心是构建最大堆（或最小堆），然后反复取出堆顶元素并调整堆，从而完成排序。以下是详细的实现方法。

理解堆与堆排序原理

堆是一棵完全二叉树，分为最大堆和最小堆。最大堆中父节点的值不小于子节点，堆顶元素为最大值。堆排序利用这一特性，将数组视为堆结构：

对于数组索引从0开始的情况，节点i的左孩子为2*i+1，右孩子为2*i+2，父节点为(i-1)/2
排序过程：先将数组构建成最大堆，然后将堆顶（最大值）与末尾元素交换，缩小堆的范围，再对新堆顶进行下沉操作（heapify）
重复此过程直到堆大小为1，数组即有序

实现堆调整函数（heapify）

heapify用于维护堆的性质。假设根节点、左子树、右子树中只有根可能破坏堆序，该函数将其“下沉”到正确位置：

void heapify(int arr[], int n, int i) {
    int largest = i;           // 假设当前节点为最大
    int left = 2 * i + 1;      // 左孩子
    int right = 2 * i + 2;     // 右孩子
<pre class='brush:php;toolbar:false;'>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);  // 递归调整被交换的子树
}

登录后复制

}

Replit Ghostwrite

一种基于 ML 的工具，可提供代码完成、生成、转换和编辑器内搜索功能。

查看详情

立即学习“C++免费学习笔记（深入）”；

构建堆并执行排序

堆排序主函数先从最后一个非叶子节点开始向上构建最大堆，然后逐个将堆顶与末尾交换：

void heapSort(int arr[], int n) {
    // 构建最大堆，从最后一个非叶子节点开始
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
<pre class='brush:php;toolbar:false;'>// 逐个提取堆顶元素
for (int i = n - 1; i > 0; i--) {
    std::swap(arr[0], arr[i]);   // 将最大值移到末尾
    heapify(arr, i, 0);          // 对剩余元素重新堆化
}

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

使用示例：

#include <iostream>
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
<pre class='brush:php;toolbar:false;'>heapSort(arr, n);

std::cout << "Sorted array: ";
for (int i = 0; i < n; ++i)
    std::cout << arr[i] << " ";
return 0;

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

基本上就这些。堆排序时间复杂度为O(n log n)，空间复杂度O(1)，适合大规模数据排序，且不受输入数据分布影响。

以上就是c++++中如何堆排序_c++堆排序实现方法的详细内容，更多请关注php中文网其它相关文章！