堆排序是一种基于比较的排序算法，它利用了二叉堆这种数据结构的特点，分为最大堆和最小堆两种形式。最大堆的特点是父节点的值总是大于或等于其子节点的值，而最小堆则相反。通过构建一个最大堆，我们可以轻松地将数组中的元素按照从大到小的顺序排列。

首先，我们需要构建一个最大堆。这个过程可以通过调整堆的结构来完成。具体来说，就是从最后一个非叶子节点开始，逐步向上进行堆调整，确保每个父节点都满足最大堆的性质。一旦最大堆构建完成，我们就可以将堆顶元素（即数组中最大的元素）与最后一个元素交换位置，并缩小堆的范围，再次对剩余部分进行堆调整。重复这一过程，直到整个数组有序。

下面是一个简单的Java实现：👇

```java

public class HeapSort {

public static void sort(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);

}

}

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) {

int swap = arr[i];

arr[i] = arr[largest];

arr[largest] = swap;

// 递归调整堆

heapify(arr, n, largest);

}

}

}

```

通过上述代码，我们可以看到堆排序的核心在于堆的构建与调整。尽管其实现相对复杂，但堆排序的时间复杂度稳定为O(n log n)，是一种非常高效的排序方法。💪

编程 算法 Java