写一个c++的最大堆排序的程序
时间: 2024-05-15 11:17:31 浏览: 10
好的,请参考下面的 C 代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 宏定义,计算数组下标对应的父节点、左孩子节点和右孩子节点的下标
#define PARENT(i) ((i - 1) / 2)
#define LEFT_CHILD(i) (2 * i + 1)
#define RIGHT_CHILD(i) (2 * i + 2)
// 最大堆调整函数,维护最大堆的性质
void max_heapify(int arr[], int i, int heap_size) {
int largest = i;
int left = LEFT_CHILD(i);
int right = RIGHT_CHILD(i);
// 找到三个节点中的最大值
if (left < heap_size && arr[left] > arr[largest]) {
largest = left;
}
if (right < heap_size && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值已经不是 i,那么交换 i 和最大值的位置,递归调用 max_heapify
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
max_heapify(arr, largest, heap_size);
}
}
// 建立最大堆的函数
void build_max_heap(int arr[], int len) {
int i;
for (i = len/2-1; i >= 0; i--) {
max_heapify(arr, i, len);
}
}
// 堆排序函数
void heap_sort(int arr[], int len) {
build_max_heap(arr, len); // 先建立最大堆
int i;
int heap_size = len;
for (i = len - 1; i > 0; i--) {
// 将堆的最大值交换到数组的末尾
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heap_size--; // 堆大小减一
max_heapify(arr, 0, heap_size); // 调整堆
}
}
int main() {
int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
int len = sizeof(arr) / sizeof(arr[0]);
heap_sort(arr, len);
int i;
for (i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
上述代码中,max\_heapify 函数用来调整最大堆,build\_max\_heap 函数用来建立最大堆,heap\_sort 函数用来排序。建立最大堆的时间复杂度为 O(n),堆排序的时间复杂度为 O(nlogn)。
如果您还有任何疑问或者需要进一步的帮助,请随时与我联系。