帮我写一个堆排序的cpp程序
时间: 2023-07-07 15:43:27 浏览: 41
好的,这是一个使用C++实现堆排序的程序:
```cpp
#include <iostream>
using namespace std;
// 将以k为根的子树调整为最大堆
void adjustHeap(int* arr, int k, int len) {
int temp = arr[k];
for (int i = k * 2 + 1; i < len; i = i * 2 + 1) {
if (i + 1 < len && arr[i] < arr[i + 1]) {
i++;
}
if (arr[i] > temp) {
swap(arr[k], arr[i]);
k = i;
} else {
break;
}
}
}
void heapSort(int* arr, int len) {
// 构建最大堆
for (int i = len / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, len);
}
// 排序
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
adjustHeap(arr, 0, i);
}
}
int main() {
int arr[] = { 5, 3, 8, 4, 1, 2, 9, 7, 6 };
int len = sizeof(arr) / sizeof(int);
heapSort(arr, len);
for (int i = 0; i < len; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
程序的大致思路是先构建一个最大堆,然后对堆进行排序。构建最大堆的操作是从最后一个非叶子节点开始向上遍历,对每个节点进行调整,使其满足最大堆的性质。排序的操作是每次将堆顶元素(即最大的元素)与堆底元素交换,然后对堆顶元素进行调整,使其满足最大堆的性质。