堆排序算法及其Java实现详解

由 Java Q&A Hub 使用 GPT-4o-mini 回答

问题：

堆排序

回答：

堆排序（Heap Sort）是一种基于比较的排序算法，利用堆这种数据结构来进行排序。堆是一种完全二叉树，具有以下性质：对于每个节点，节点的值总是大于或等于（或小于或等于）其子节点的值。根据这个性质，堆可以分为最大堆和最小堆。

堆排序的基本步骤

  1. 构建最大堆：将待排序的数组构建成一个最大堆。最大堆的根节点是最大的元素。
  2. 交换根节点与最后一个节点：将最大堆的根节点（最大值）与数组的最后一个元素交换。
  3. 调整堆：将剩余的元素重新调整为最大堆。
  4. 重复步骤2和3：直到所有元素都被排序。

堆排序的时间复杂度

  • 最坏情况：O(n log n)
  • 平均情况：O(n log n)
  • 最好情况：O(n log n)

堆排序的空间复杂度

  • O(1)：堆排序是原地排序算法，不需要额外的存储空间。

Java实现堆排序

下面是一个使用Java实现的堆排序的示例代码：

public class HeapSort {

    // 主方法
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("原始数组:");
        printArray(arr);

        heapSort(arr);

        System.out.println("排序后的数组:");
        printArray(arr);
    }

    // 堆排序方法
    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);
        }
    }

    // 堆调整方法
    public 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 printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

代码分析

  1. 构建最大堆：通过从最后一个非叶子节点开始，逐步向上调整堆，确保每个父节点都大于其子节点。
  2. 交换和调整：每次将最大值（根节点）与当前未排序部分的最后一个元素交换，然后对剩余部分进行堆调整。
  3. 递归调整：heapify方法用于维护堆的性质，确保每个父节点都大于其子节点。

总结

堆排序是一种高效的排序算法，适用于大规模数据的排序。它的原地排序特性使得它在内存使用上非常高效。通过理解堆的结构和调整过程，可以更好地掌握堆排序的实现和应用。

Related