【堆排序算法java】堆排序是一种基于二叉堆数据结构的比较排序算法，具有较高的效率和稳定的性能。它通过构建最大堆或最小堆来实现排序，是内部排序中较为高效的一种方法。
一、堆排序基本原理
堆排序的核心思想是将待排序的数组构造成一个堆结构，然后不断提取堆顶元素（最大值或最小值），并将剩余元素重新调整为堆，从而逐步得到有序序列。
- 最大堆：父节点的值大于等于子节点的值。
- 最小堆：父节点的值小于等于子节点的值。
在堆排序中，通常使用最大堆来进行升序排序，或者使用最小堆进行降序排序。
二、堆排序步骤
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 i : arr) {
System.out.print(i + " ");
}
}
}
```
四、堆排序特点总结
| 特点 | 描述 |
| 时间复杂度 | O(n log n)（最好、平均、最坏情况） |
| 空间复杂度 | O(1)（原地排序） |
| 稳定性 | 不稳定（相同元素可能改变顺序） |
| 适用场景 | 需要高效排序且内存有限的场景 |
| 实现难度 | 中等 |
| 是否需要额外空间 | 否 |
五、优缺点对比
| 优点 | 缺点 |
| 排序效率高，时间复杂度稳定 | 不稳定排序 |
| 原地排序，空间消耗小 | 对于小规模数据不如插入排序快 |
| 可用于优先队列实现 | 实现逻辑相对复杂 |
六、总结
堆排序是一种高效的排序算法，尤其适合大规模数据的排序任务。其核心在于堆结构的构建与维护，虽然实现过程稍显复杂，但其稳定的性能和较低的空间占用使其在实际应用中非常受欢迎。在Java中，通过构建最大堆并不断交换堆顶元素的方式，可以高效完成排序操作。
