java 堆排序

原创admin 分类：热门问答 2024-05-07 17:53:00 0

java 堆排序
#### 引言在计算机科学的世界里，排序算法是基础且重要的一环。我经常思考，如何将一堆杂乱无章的数字变得井然有序。今天，我将深入探讨一种高效且有趣的排序算法——堆排序。堆排序不仅在理论上有着优雅的定义，而且在实际应用中也展现出了其独特的优势。它利用了二叉堆的数据结构，通过构建最大堆或最小堆来实现排序，这与快速排序、归并排序等其他算法有着明显的区别。

堆排序的定义与条件

堆排序是一种基于比较的排序算法，它使用二叉堆的概念来组织数据。一个二叉堆是一棵完全二叉树，可以看作是一个数组，并且满足以下两个条件：

堆序性质：即任意节点的值总是不大于（最大堆）或不小于（最小堆）其子节点的值。
形状性质：即除了最后一层外，每一层都被完全填满。

堆排序的目的是将一个无序的数组通过堆的调整转换为有序数组。它的时间复杂度为O(n log n)，这使得它在处理大数据集时非常有效。

核心类与方法

在Java中实现堆排序，我们主要关注以下几个核心概念和方法：

二叉堆的表示：通常使用数组来表示二叉堆。
上滤（heapify）：确保堆的某个节点满足堆的性质。
下沉（sift down）：调整堆，确保最大值能够下沉到底部。

使用场景

堆排序适用于那些需要对大量数据进行排序的场景，尤其是当数据源太大，无法一次性全部加载到内存中时。此外，它也是许多其他算法，如Dijkstra算法和Prim算法的基础。

代码案例

以下是两个Java堆排序的代码案例：

案例1：最大堆排序

public class HeapSortMax {
    public void sort(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);
        }
    }

    void heapify(int[] arr, int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        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};
        HeapSortMax heapSort = new HeapSortMax();
        heapSort.sort(arr);

        System.out.println("Sorted array is");
        for (int i : arr)
            System.out.print(i + " ");
    }
}

案例2：最小堆排序

public class HeapSortMin {
    // 构建最小堆
    void buildHeap(int[] arr, int n) {
        for (int i = n / 2 - 1; i >= 0; i--)
            minHeapify(arr, n, i);
    }

    // 调整最小堆
    void minHeapify(int[] arr, int n, int i) {
        int smallest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && arr[l] < arr[smallest])
            smallest = l;

        if (r < n && arr[r] < arr[smallest])
            smallest = r;

        if (smallest != i) {
            int temp = arr[i];
            arr[i] = arr[smallest];
            arr[smallest] = temp;

            minHeapify(arr, n, smallest);
        }
    }

    // 执行堆排序
    void heapSort(int[] arr) {
        int n = arr.length;

        // 构建最小堆
        buildHeap(arr, n);

        // 一个接一个地提取最小元素
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 重新调整堆
            minHeapify(arr, i, 0);
        }
    }

    public static void main(String args[]) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        HeapSortMin heapSort = new HeapSortMin();
        heapSort.heapSort(arr);

        System.out.println("Sorted array is");
        for (int i : arr)
            System.out.print(i + " ");
    }
}