Java实现堆排序算法

 
 
1. 堆排序原理图解

 
堆排序是一种基于二叉堆（通常利用最大堆）的排序算法。其核心思想是利用堆的性子（父节点的值大于或即是子节点的值）来高效地举行排序。堆排序分为两个主要阶段：建堆和排序。
 
堆排序步骤：

 
1. 建堆：
   - 将无序数组构建成一个最大堆。
   - 从末了一个非叶子节点开始，逐个调整节点，使其满足堆的性子。
 
2. 排序：
   - 将堆顶元素（最大值）与堆的末了一个元素交换。
   - 缩小堆的范围，重新调整堆，使其满足最大堆的性子。
   - 重复上述过程，直到堆的巨细为1。
 
图解示例：

 
假设数组为 `[4, 10, 3, 5, 1]`。
 
1. 初始状态：`[4, 10, 3, 5, 1]`
2. 建堆：
   - 调整节点，构建最大堆：`[10, 5, 3, 4, 1]`
3. 排序过程：
   - 将堆顶元素（10）与末了一个元素（1）交换：`[1, 5, 3, 4, 10]`
   - 调整剩余的堆（`[1, 5, 3, 4]`），使其满足最大堆的性子：`[5, 4, 3, 1]`
   - 将堆顶元素（5）与末了一个元素（1）交换：`[1, 4, 3, 5, 10]`
   - 调整剩余的堆（`[1, 4, 3]`），使其满足最大堆的性子：`[4, 1, 3]`
   - 将堆顶元素（4）与末了一个元素（3）交换：`[3, 1, 4, 5, 10]`
   - 调整剩余的堆（`[3, 1]`），使其满足最大堆的性子：`[3, 1]`
   - 将堆顶元素（3）与末了一个元素（1）交换：`[1, 3, 4, 5, 10]`
4. **终极结果**：`[1, 3, 4, 5, 10]`
 
 2. Java代码实现及解释
 
```java
import java.util.Arrays;
 
public class HeapSort {
    public static void main(String[] args) {
        int[] array = {4, 10, 3, 5, 1};
        heapSort(array);
        System.out.println("排序后的数组：");
        System.out.println(Arrays.toString(array));
    }
 
    // 堆排序主方法
    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;
            arr = temp;
 
            // 调整剩余的堆
            heapify(arr, i, 0);
        }
    }
 
    // 调整堆的方法
    private static void heapify(int[] arr, int heapSize, int rootIndex) {
        int largest = rootIndex; // 假设根节点是最大的
        int leftChild = 2 * rootIndex + 1; // 左子节点
        int rightChild = 2 * rootIndex + 2; // 右子节点
 
        // 如果左子节点大于根节点
        if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
 
        // 如果右子节点大于当前最大的节点
        if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }
 
        // 如果最大的节点不是根节点，交换它们
        if (largest != rootIndex) {
            int temp = arr[rootIndex];
            arr[rootIndex] = arr[largest];
            arr[largest] = temp;
 
            // 递归调整子树
            heapify(arr, heapSize, largest);
        }
    }
}
```
 
 3. 代码阐明

 
1. 建堆：
   - 从末了一个非叶子节点开始，逐个调整节点，使其满足最大堆的性子。
   - 利用 `heapify` 方法调整节点。
 
2. 排序：
   - 将堆顶元素（最大值）与堆的末了一个元素交换。
   - 缩小堆的范围，重新调整堆，使其满足最大堆的性子。
   - 重复上述过程，直到堆的巨细为1。
 
3. 时间复杂度：
   - **最坏环境**：`O(n log n)`。
   - **均匀环境**：`O(n log n)`。
   - **最好环境**：`O(n log n)`。
 
4. 空间复杂度：
   - `O(1)`，由于堆排序是原地排序算法，不必要额外的存储空间。
 
5. 稳定性：
   - 堆排序是**不稳定的**，由于交换操纵大概改变雷同值元素的相对次序。
 
4. 应用场景

 
1. 大规模数据排序：
   - 堆排序的时间复杂度为 `O(n log n)`，得当对大规模数据举行排序。
 
2. 优先队列实现：
   - 堆排序的核心思想可以用于实现优先队列，例如在使命调理中。
 
3. 教学和演示：
   - 堆排序的实现清楚，适实用于教学和算法演示。
 
 5. 总结

 
堆排序是一种高效的排序算法，基于二叉堆的性子实现。它的时间复杂度稳定在 `O(n log n)`，而且是原地排序算法，不必要额外的存储空间。然而，堆排序是不稳定的，因此在必要保持雷同值元素相对次序的场景中不实用。在实际应用中，堆排序常用于大规模数据排序和优先队列的实现。