马士兵java架构师

您现在的位置是:java学习笔记 >

java学习笔记

java堆排序工具类

2024-05-20 21:45:35java学习笔记 本文浏览次数:0 百度已收录

本 文 目 录

java堆排序工具类
作为一名软件开发者,我经常需要处理大量的数据排序问题。在众多排序算法中,堆排序以其独特的优势而脱颖而出。堆排序是一种基于二叉堆数据结构的比较排序算法,它能够提供相对稳定的排序性能,无论是最好、最坏还是平均情况,时间复杂度都能保持在O(n log n)。

堆排序与快速排序、归并排序等其他排序算法相比,它不需要额外的存储空间,因为它是在原数组上进行排序的。然而,快速排序在平均情况下性能更好,但最坏情况下可能退化到O(n^2)的时间复杂度。而归并排序虽然稳定,但需要额外的存储空间。

核心类与方法

堆排序的核心在于构建堆和堆调整。堆是一种特殊的完全二叉树,它满足两个特性:任意节点的值都大于或等于其子节点的值(大顶堆),或者任意节点的值都小于或等于其子节点的值(小顶堆)。构建堆的过程通常通过下沉操作来完成,即从最后一个非叶子节点开始,逐个向下调整,以满足堆的性质。

使用场景

堆排序适用于那些需要对大量数据进行排序的场景,尤其是在内存受限的环境中。由于它不需要额外的存储空间,因此对于内存使用有严格要求的系统来说,堆排序是一个不错的选择。

代码案例

以下是两个堆排序的Java工具类代码案例。

案例1:大顶堆排序

public class MaxHeapSort {
    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);
        }
    }
}

案例2:小顶堆排序

public class MinHeapSort {
    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 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 swap = arr[i];
            arr[i] = arr[smallest];
            arr[smallest] = swap;

            heapify(arr, n, smallest);
        }
    }
}

补充知识

以下是堆排序与其他排序算法的对比表格:

排序算法 时间复杂度 空间复杂度 是否稳定 是否需要额外空间
堆排序 O(n log n) O(1)
快速排序 O(n log n) O(log n)
归并排序 O(n log n) O(n)

通过上述代码案例和表格,我们可以看到堆排序在某些场景下的优势。它是一种值得考虑的排序算法,特别是在对内存使用有限制的情况下。