当前位置：首页 > java >正文

重温经典算法——堆排序

java 2025/7/12 22:38:28

版权声明

本文原创作者：谷哥的小弟
作者博客地址：http://blog.csdn.net/lfdfhl

在这里插入图片描述

基本原理

堆排序是一种基于二叉堆的排序算法，时间复杂度为O(n log n)。堆排序核心步骤包括构建最大堆和反复取出堆顶元素排序：首先从最后一个非叶子节点开始调整构建最大堆，然后将堆顶元素与末尾元素交换，并重新调整剩余元素为新堆。该算法时间复杂度 O(n log n)，空间复杂度 O(1)。

代码实现

import java.util.Arrays;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--) {swap(arr, 0, i);    // 将堆顶元素交换到数组末尾heapify(arr, i, 0); // 调整剩余元素为新堆}}private static void heapify(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) {swap(arr, i, largest);heapify(arr, n, largest);}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {int[] arr = {4, 10, 3, 5, 1};heapSort(arr);System.out.println("Sorted array: " + Arrays.toString(arr));// 输出：Sorted array: [1, 3, 4, 5, 10]}
}