堆排序的C++具体实现
时间: 2023-10-22 19:14:50 浏览: 36
堆排序是一种树形选择排序,它的特点是将待排序序列构造成一个堆,选择最大(最小)的元素放到堆的最后,然后将剩余元素重新构造成堆,直到所有元素都排完为止。
以下是堆排序的C++实现:
```cpp
#include <iostream>
using namespace std;
// 堆排序函数
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 heapify(int arr[], int n, int i) {
int largest = i; // 初始化最大值为根节点
int l = 2 * i + 1; // 左子节点
int r = 2 * i + 2; // 右子节点
// 如果左子节点比根节点大,则更新最大值
if (l < n && arr[l] > arr[largest])
largest = l;
// 如果右子节点比最大值大,则更新最大值
if (r < n && arr[r] > arr[largest])
largest = r;
// 如果最大值不是根节点,则交换根节点和最大值
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest); // 继续构造最大堆
}
}
// 打印排序后的数组
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}
```
以上代码实现了堆排序的核心函数 `heapSort()` 和最大堆构造函数 `heapify()`。程序运行结果如下:
```
Sorted array is
5 6 7 11 12 13
```