堆排序c++不要用库函数
时间: 2023-12-25 15:29:15 浏览: 31
堆排序是一种常见的排序算法,它利用堆的性质进行排序。下面是一个不使用库函数的C++堆排序的示例代码:
```cpp
#include <iostream>
using namespace std;
// 调整堆
void heapify(int arr[], int n, int i) {
int largest = i; // 初始化最大元素为根节点
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点大于根节点
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点大于根节点
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大元素不是根节点
if (largest != i) {
swap(arr[i], arr[largest]);
// 递归调整子树
heapify(arr, n, largest);
}
}
// 堆排序
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);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "排序后的数组:";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```
这段代码实现了堆排序算法,首先构建最大堆,然后逐个将最大元素移到末尾,并调整剩余元素的堆。最后输出排序后的数组。