堆排序：堆排序如何实现？时间复杂度详解
堆排序是利用“堆”（特殊完全二叉树）实现的排序算法，常用大顶堆（父节点≥子节点）。核心思想是“先建堆，再排序”：先将数组转为大顶堆（堆顶为最大值），再反复交换堆顶与末尾元素，调整剩余元素为堆，完成排序。 堆的基本概念：完全二叉树结构，数组中索引i的左子节点2i+1、右子节点2i+2、父节点(i-1)//2。大顶堆父≥子，小顶堆父≤子。 实现分两步：1.构建大顶堆：从最后非叶子节点开始，通过“堆化”（比较父与子节点，交换最大值并递归调整子树）确保大顶堆性质；2.排序：交换堆顶与未排序末尾元素，缩小堆规模后重复堆化，直至完成。 时间复杂度：构建堆O(n)，排序过程O(n log n)，总O(n log n)，空间复杂度O(1)（原地排序）。特点是不稳定，适合大规模数据排序。
阅读全文使用C++实现堆排序算法
堆排序是基于堆数据结构的高效排序算法，时间复杂度O(n log n)，空间复杂度O(1)，适用于大规模数据。堆是特殊完全二叉树，分大顶堆（父≥子）和小顶堆，排序常用大顶堆。其存储为数组，索引i的父节点为(i-1)/2，左右子节点为2i+1和2i+2。核心步骤：1.构建初始大顶堆（从最后非叶子节点向上调整）；2.排序（交换堆顶与未排序末尾元素，调整堆，重复直至完成）。C++实现包含swap、max_heapify（迭代调整子树为大顶堆）、heap_sort（构建堆并排序）函数，主函数测试数组排序，输出结果正确。
阅读全文