堆排序实现及复杂度分析

一、算法概述

堆排序(Heap Sort)是一种基于二叉堆数据结构的比较排序算法。它利用了堆这种数据结构的特性：

• 最大堆：每个节点的值都大于或等于其子节点的值
• 最小堆：每个节点的值都小于或等于其子节点的值

堆排序是不稳定排序算法，时间复杂度为O(nlogn)，空间复杂度为O(1)

二、算法步骤

1. 构建初始堆

将无序数组构建成一个最大堆（升序排序时）

2. 交换与调整

• 将堆顶元素（最大值）与末尾元素交换
• 缩小堆的范围，重新调整堆结构

3. 重复步骤2

直到堆的大小缩减为1，排序完成

三、复杂度分析

时间复杂度

• 建堆过程：O(n)
• 调整堆过程：每次调整O(logn)，共n-1次 → O(nlogn)

总时间复杂度：O(nlogn)

空间复杂度

堆排序是原地排序算法，空间复杂度为O(1)

四、代码实现

Java实现

public class HeapSort {public void sort(int arr[]) {