堆排序 Java 代码详解214

堆排序是一种基于二叉树数据结构的高效排序算法，它以其时间复杂度较低和易于实现的优点而著称。在此篇文章中，我们将深入探讨堆排序的原理并提供 Java 代码示例，帮助您理解并在自己的项目中应用这种排序算法。

1. 堆的概念

堆是一种特定的二叉树数据结构，它满足以下两个性质：* 最大堆：每个节点的值都大于或等于其子节点的值。
* 最小堆：每个节点的值都小于或等于其子节点的值。

我们将重点讨论最大堆，因为堆排序算法使用的是最大堆。

2. 堆排序算法

堆排序算法包含以下步骤：1. 构建堆：将输入数组转换为一个最大堆。
2. 排序：重复以下步骤，直到堆为空：
* 交换堆顶（最大值）和最后一个元素。
* 重新调整剩余堆，使其仍然满足最大堆性质。
3. 返回：排序后的数组存储在原输入数组中。

2.1 构建堆

要构建最大堆，可以使用自下而上的方法，从最后一个非叶节点开始：```java
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
```

在此，`heapify` 方法负责调整以`i`为根的子树，使其成为最大堆。

2.2 重新调整堆

每次从堆顶移除元素后，都需要重新调整堆以保持最大堆性质：```java
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);
}
}
```

3. Java 代码示例

以下 Java 代码展示了堆排序算法的实现：```java
import .*;
public class HeapSort {
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
heapSort(arr);
((arr)); // 输出：{5, 6, 7, 11, 12, 13}
}
private static void heapSort(int[] arr) {
int n = ;
// 构建堆
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;
}
}
```