堆排序详解（手把手教你用Java实现堆排序）

堆排序的基本思想

堆排序的核心步骤如下：

1. 将待排序数组构建成一个大顶堆；
2. 将堆顶元素（最大值）与末尾元素交换，然后将剩余元素重新调整为大顶堆；
3. 重复第2步，直到所有元素有序。

Java 实现堆排序

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

public class HeapSort {    // 堆排序主方法    public static void heapSort(int[] arr) {        int n = arr.length;        // 第一步：构建大顶堆（从最后一个非叶子节点开始）        for (int i = n / 2 - 1; i >= 0; i--) {            heapify(arr, n, i);        }        // 第二步：依次取出堆顶元素，放到数组末尾        for (int i = n - 1; i > 0; i--) {            // 将堆顶（最大值）与当前末尾交换            int temp = arr[0];            arr[0] = arr[i];            arr[i] = temp;            // 重新调整堆（排除已排序的末尾部分）            heapify(arr, i, 0);        }    }    // 调整堆结构，使其满足大顶堆性质    public static void heapify(int[] arr, int heapSize, int rootIndex) {        int largest = rootIndex; // 假设根节点最大        int leftChild = 2 * rootIndex + 1;  // 左孩子索引        int rightChild = 2 * rootIndex + 2; // 右孩子索引        // 如果左孩子存在且比根大        if (leftChild < heapSize && arr[leftChild] > arr[largest]) {            largest = leftChild;        }        // 如果右孩子存在且比当前最大值大        if (rightChild < heapSize && arr[rightChild] > arr[largest]) {            largest = rightChild;        }        // 如果最大值不是根节点，则交换并继续调整        if (largest != rootIndex) {            int swap = arr[rootIndex];            arr[rootIndex] = arr[largest];            arr[largest] = swap;            // 递归调整受影响的子树            heapify(arr, heapSize, largest);        }    }    // 测试方法    public static void main(String[] args) {        int[] arr = {12, 11, 13, 5, 6, 7};        System.out.println("排序前：" + java.util.Arrays.toString(arr));        heapSort(arr);        System.out.println("排序后：" + java.util.Arrays.toString(arr));    }}  

代码解析

• heapSort 方法先构建大顶堆，再逐步提取最大值；
• heapify 方法用于维护堆的性质，确保父节点始终大于子节点；
• 构建堆时，从最后一个非叶子节点（索引为 n/2 - 1）开始向上调整；
• 每次交换堆顶和末尾后，堆大小减一，避免已排序部分被干扰。

堆排序的优缺点

优点：

• 时间复杂度稳定：O(n log n)；
• 空间复杂度低：O(1)，属于原地排序；
• 不依赖输入数据分布，性能稳定。

缺点：

• 不是稳定排序（相同元素的相对位置可能改变）；
• 常数因子较大，实际运行速度可能不如快排。

总结

通过本教程，你已经掌握了堆排序的基本原理和 Java 实现方法。堆排序作为重要的数据结构堆排序应用之一，在面试和实际开发中都非常常见。建议你动手敲一遍代码，加深理解。如果你对Java堆排序还有疑问，欢迎留言交流！

关键词回顾：堆排序、Java堆排序、堆排序算法、数据结构堆排序