堆排序（Heap Sort）是一种原地、不稳定的排序算法，它利用堆这种数据结构来进行排序。堆是一种特殊的树形数据结构，满足堆的性质：对于每个节点 i，父节点的值始终大于或等于子节点的值（最大堆），或者父节点的值始终小于或等于子节点的值（最小堆）。
堆排序的基本原理如下：
1. **构建堆**：将待排序的元素构建成一个堆（通常是最大堆），即满足堆的性质。
2. **堆调整**：将堆顶元素（最大元素或最小元素）与堆的最后一个元素交换，然后对剩余的元素重新调整为堆，使其满足堆的性质。
3. **重复步骤2**：重复上述过程，每次将堆顶元素与当前堆的最后一个元素交换，并调整堆，直到所有元素都被取出，最终得到有序序列。
堆排序的特点：
- 时间复杂度为 O(nlogn)，其中 n 是元素个数。
- 堆排序是原地排序，不需要额外的空间。
- 堆排序是不稳定的排序算法，因为在堆调整过程中可能会改变相同元素的相对位置。
- 适用于需要原地排序且对稳定性没有要求的情况。
堆排序在实践中通常用于对大规模数据进行排序，因为它不需要额外的空间，且具有较好的时间复杂度。然而，由于其不稳定性，当需要保持相同元素的相对位置不变时，可能需要考虑其他排序算法。以下是用 C++ 实现堆排序的示例代码：
```cpp
#include <iostream>
#include <vector>
// 调整堆，使其满足堆的性质 void heapify(std::vector<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) { std::swap(arr[i], arr[largest]); // 递归调整子树 heapify(arr, n, largest); } } // 堆排序 void heapSort(std::vector<int>& arr) { int n = arr.size(); // 构建最大堆 for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 依次取出堆顶元素，将其放到数组末尾并调整堆 for (int i = n - 1; i > 0; i--) { std::swap(arr[0], arr[i]); // 将堆顶元素与当前堆的最后一个元素交换 heapify(arr, i, 0); // 调整堆 } } void printArray(const std::vector<int>& arr) { for (int num : arr) { std::cout << num << " "; } std::cout << std::endl; } int main() { std::vector<int> arr = {12, 11, 13, 5, 6, 7}; int n = arr.size(); std::cout << "Original array: "; printArray(arr); heapSort(arr); std::cout << "Sorted array: "; printArray(arr); return 0; } ```
在这段代码中，`heapify` 函数用于调整堆，使其满足堆的性质。`heapSort` 函数实现了堆排序算法，包括构建最大堆和进行堆排序。`printArray` 函数用于打印数组的元素。在 `main` 函数中定义了一个整型数组并对其进行堆排序。
