堆排序（Heap Sort）是一种基于比较的排序算法，它利用了堆这种数据结构来实现高效排序。堆是一种完全二叉树，分为最大堆和最小堆。最大堆中每个节点的值都大于或等于其子节点的值，最小堆则相反。
以下是堆排序的详细步骤：
1. 建堆：将待排序的序列构建成一个最大堆（或最小堆）。对于一个数组 arr，从最后一个非叶子节点开始，从下往上调整堆，使得每个节点都满足堆的性质。
2. 交换元素：将堆顶元素（即最大值）与堆的最后一个元素交换位置，这样最大值就放到了数组的末尾。
3. 调整堆：交换后，堆的性质被破坏，需要对除了最后一个元素之外的其他元素重新调整堆，使其再次满足堆的性质。
4. 重复步骤2和3：不断重复上述过程，直到堆中只剩下一个元素，此时数组已经有序。
下面是用C++实现堆排序的代码示例：
#include
#include
using namespace std;
// 调整堆的函数，将当前节点调整为最大堆
void heapify(vector
int largest = i; // 初始化最大节点为当前节点
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点比当前节点大
if (left < n arrleft> arr[largest]) {
largest = left;
}
// 如果右子节点比当前最大节点大
if (right < n arrright> arr[largest]) {
largest = right;
}
// 如果最大节点不是当前节点，交换并递归调整
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
// 堆排序函数
void heapSort(vector
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) {
// 将当前堆顶元素移到数组末尾
swap(arr[0], arr[i]);
// 对剩余元素重新调整堆
heapify(arr, i, 0);
}
}
// 打印数组函数
void printArray(const vector
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}
你可以使用以下方式调用：
int main() {
vector
cout << "Original array: ";
printArray(arr);
heapSort(arr);
cout << "Sorted array: ";
printArray(arr);
return 0;
}
适用场景分析：
1. 空间复杂度要求低：堆排序是一种原地排序算法，不需要额外的大量空间，空间复杂度为O(1)。因此，在空间有限的情况下，堆排序是一个不错的选择。
2. 数据量大且对稳定性无要求：堆排序的时间复杂度为O(n log n)，在平均、最坏和最好情况下都是如此，性能相对稳定。如果数据量较大且对稳定性没有要求（即相同元素的相对顺序在排序后可以改变），堆排序是一个高效的排序算法。
3. 在线排序：堆排序可以在数据不断到来的情况下进行排序，只需要将新数据插入堆中，然后进行调整即可。这对于需要实时处理数据的场景非常有用。
总的来说，堆排序适用于对空间要求严格、数据量大且对稳定性无要求的排序场景。