C++ 堆排序详解 |21xrx.com

2023-07-07 08:29:03 深夜i -- --

C++ 堆排序详解

堆排序是一种基于二叉堆的排序算法，是在堆的数据结构上改进的选择排序。

C++ 堆排序的概念：

堆是一个完全二叉树，满足任意节点都大于等于或小于等于其子节点（根据排序的需要定义），这个特性被称为“堆的性质”。最大堆即为任意节点都大于等于其子节点，最小堆即为任意节点都小于等于其子节点。

堆排序的核心是建立一个堆，将要排序的数组所有元素构建成一个堆，并且从最后一个元素开始取值放到最前面，从而实现排序的目的。

C++ 堆排序的实现：

1. 最大堆的策略

（1）将初始待排序序列构建成一个大根堆。

（2）此时第一个元素是序列中最大的元素，将其与末尾元素进行交换，使得末尾元素为最大值。

（3）然后将剩余元素重新构建成一个大根堆，重复上述步骤，直到整个序列排序完成。

例如序列 29 10 14 37 13 22 80 62 75，构建成大根堆如下：

Heapify(arr, n, i)

{

largest = i；// 假设最大元素是节点i

左孩子编号left = 2 * i + 1; // 左孩子编号为2 * i + 1

右孩子编号right = 2 * i + 2; // 右孩子编号为2 * i + 2

if (left < n && arr[left] > arr[largest])

largest = left; // 记录左孩子编号

if (right < n && arr[right] > arr[largest])

largest = right; // 记录右孩子编号

if (largest != i) // 如果最大元素不是节点i

{

swap(arr[i], arr[largest]); // 交换最大元素和节点i

Heapify(arr, n, largest); // 以largest作为子树顶, 递归调用Heapify函数

}

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);

}

2. 最小堆的策略

最小堆的实现与最大堆的实现相似，即将初始待排序序列构建成一个小根堆，重复选取堆顶元素并重新构建的操作，直到整个序列排序完成。

C++ 堆排序的特点：

堆排序是稳定的排序算法，时间复杂度为 O(nlogn) ，空间复杂度为 O(1) 。由于堆排序只有在排序阶段才需要建堆，而且每次都拿出堆顶元素，所以不需要大量的辅助空间。适用于大数据排序和对稳定性要求不高的场景。

上一篇: idea打包java可执行jar包

下一篇: C++生成随机数

()

相似文章