堆排序：堆排序如何实现？时间复杂度详解

堆排序是利用“堆”（特殊完全二叉树）实现的排序算法，常用大顶堆（父节点≥子节点）。核心思想是“先建堆，再排序”：先将数组转为大顶堆（堆顶为最大值），再反复交换堆顶与末尾元素，调整剩余元素为堆，完成排序。 堆的基本概念：完全二叉树结构，数组中索引i的左子节点2i+1、右子节点2i+2、父节点(i-1)//2。大顶堆父≥子，小顶堆父≤子。 实现分两步：1.构建大顶堆：从最后非叶子节点开始，通过“堆化”（比较父与子节点，交换最大值并递归调整子树）确保大顶堆性质；2.排序：交换堆顶与未排序末尾元素，缩小堆规模后重复堆化，直至完成。 时间复杂度：构建堆O(n)，排序过程O(n log n)，总O(n log n)，空间复杂度O(1)（原地排序）。特点是不稳定，适合大规模数据排序。