C++堆排序算法详解（从零开始掌握高效排序技术）

堆排序的基本思想

堆排序的核心步骤如下：

1. 将待排序数组构建成一个最大堆；
2. 将堆顶（最大值）与堆的最后一个元素交换，并将堆的大小减一；
3. 对新的堆顶执行“向下调整”（heapify），使其重新满足堆的性质；
4. 重复步骤2和3，直到堆的大小为1。

C++堆排序算法实现

下面我们用 C++ 编写完整的堆排序代码，并逐行解释。

#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};    std::cout << "原始数组: ";    printArray(arr);    heapSort(arr);    std::cout << "排序后数组: ";    printArray(arr);    return 0;}

代码解析

• heapify 函数负责维护堆的性质。它从指定节点开始，向下比较并交换，确保子树满足最大堆条件。
• heapSort 函数首先构建最大堆，然后反复将堆顶（最大值）移至数组末尾，并缩小堆的范围。
• 构建堆时，我们从最后一个非叶子节点（索引为 n/2 - 1）开始向上调整，这样能高效地建立整个堆。

时间与空间复杂度

总结

通过本教程，你已经掌握了 C++堆排序算法 的原理与实现。堆排序不仅效率高，而且是原地排序，非常适合内存受限的场景。无论你是准备面试，还是学习数据结构堆排序，这套代码都能为你打下坚实基础。

记住，多动手实践是掌握算法的关键！尝试修改数组、调试代码，你会对堆排序实现有更深的理解。希望这篇C++排序教程对你有所帮助！