【堆排序算法java】堆排序是一种基于二叉堆数据结构的比较排序算法，它利用了完全二叉树的性质，将待排序数组构造成一个最大堆或最小堆，然后通过不断提取堆顶元素来实现排序。在Java中，堆排序的实现通常依赖于数组的操作，具有较高的时间效率和较低的空间复杂度。
一、堆排序的基本思想
堆排序的核心思想是：
1. 构建堆：将待排序的数组构造成一个最大堆（或最小堆）。
2. 交换与调整：将堆顶元素（最大值或最小值）与末尾元素交换，然后对剩余元素重新调整为堆。
3. 重复步骤2，直到所有元素排序完成。
二、堆排序的步骤说明
| 步骤 | 操作 | 说明 |
| 1 | 构建初始堆 | 将数组转换为一个最大堆或最小堆 |
| 2 | 交换堆顶与最后一个元素 | 将当前最大的元素放到已排序区域末尾 |
| 3 | 调整堆 | 对剩下的元素重新调整为堆结构 |
| 4 | 重复步骤2-3 | 直到所有元素排序完成 |
三、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);
}
}
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);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
heapSort(arr);
System.out.println("排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
四、堆排序特点总结
| 特性 | 说明 |
| 时间复杂度 | O(n log n)（最坏、平均、最好） |
| 空间复杂度 | O(1)（原地排序） |
| 稳定性 | 不稳定（相同元素顺序可能改变） |
| 适用场景 | 数据量较大，内存有限时使用 |
| 实现难度 | 中等（需要理解堆结构和递归调整） |
五、小结
堆排序是一种高效的排序算法，尤其适合大规模数据的排序。其核心在于堆的构造与维护，而Java中的实现则主要依赖于数组操作和递归函数。虽然堆排序不稳定，但其良好的时间复杂度使其在实际应用中具有较高价值。