java堆排序如何实现

Java

小亿

2024-12-07 08:44:37

栏目: 编程语言

Java堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）的比较类排序算法。二叉堆可以分为最大堆（Max Heap）和最小堆（Min Heap）。这里我将为您介绍如何使用最大堆实现堆排序。

以下是使用Java实现堆排序的步骤：

构建最大堆：将给定的无序数组转换为最大堆。
堆排序：重复从堆中提取最大元素并将其放到数组的末尾，然后调整堆结构。

下面是Java代码实现：

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        heapSort(arr);
        System.out.println("Sorted array is:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void heapSort(int[] arr) {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Extract elements one by one
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    public static void heapify(int[] arr, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // Left = 2*i + 1
        int right = 2 * i + 2; // Right = 2*i + 2

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }
}

这段代码首先定义了一个heapSort方法，用于对输入数组进行堆排序。在heapSort方法中，我们首先构建最大堆，然后通过循环提取最大元素并将其放到数组的末尾。最后，我们定义了一个heapify方法，用于调整堆结构。

当运行此代码时，您将看到已排序的数组输出：

Sorted array is:
5 6 7 11 12 13

java堆排序如何实现

最新问答

相关标签