C++ 堆排序

C++ 堆排序

堆排序是一种基于二叉堆数据结构的排序算法，其原理如下：

1. 构建最大堆：将待排序的数组看作一个完全二叉树，并通过调整节点的位置构建一个最大堆。最大堆满足每个父节点的值都大于或等于其子节点的值。构建最大堆的过程可以从最后一个非叶子节点开始，逐步向前，对每个节点进行下沉操作，使得子树满足最大堆的性质。

2. 排序过程：构建完成最大堆后，将堆顶元素（即最大值）与数组的最后一个元素交换。然后，将堆的大小减1，再对堆顶元素执行下沉操作，以重新满足最大堆的性质。重复这个过程，直到堆的大小减少到1。最终，得到的数组就是有序的。

堆排序的关键操作是下沉（sink）和上浮（swim）：

• 下沉操作：将某个节点与其子节点中较大的节点交换位置，并递归地对交换后的子节点执行下沉操作，直到满足最大堆的性质。
• 上浮操作：将某个节点与其父节点比较，如果节点的值大于父节点的值，则交换位置，并递归地对交换后的父节点执行上浮操作，直到满足最大堆的性质。

堆排序的时间复杂度为O(n log n)，其中n是待排序数组的长度。构建最大堆的时间复杂度是O(n)，排序过程需要进行n次下沉操作，每次下沉操作的时间复杂度是O(log n)。由于堆排序是原地排序算法，不需要额外的辅助空间，因此空间复杂度是O(1)。

需要注意的是，堆排序是不稳定的排序算法，即相等元素的相对顺序可能会发生改变。

#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[i] < arr[left]) {largest = left;}// 如果右子节点存在且大于根节点或左子节点，则更新最大值索引if (right < n && arr[largest] < arr[right]) {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;
}