java堆排序算法代码

在计算机科学中，排序算法是基础而重要的一环，它关乎数据的组织和检索效率。今天，我将带你深入了解堆排序算法，这是一种利用二叉堆数据结构来实现的排序算法。

定义与目的

堆排序是一种比较类排序算法，它利用了二叉堆的数据结构特性。二叉堆是一种特殊的完全二叉树，可以看作一个数组来实现。堆排序的目的是将一个数据序列通过堆结构进行排序，以便快速找到最大（或最小）元素。

条件与重要知识点

堆排序的基本条件是待排序的元素可以存储在一个数组中，且可以进行随机访问。它不需要额外的存储空间，因为排序过程直接在原数组上进行。堆排序的时间复杂度为O(nlogn)，这使得它在处理大数据集时非常高效。

区别与对比

堆排序与其他排序算法相比，如快速排序、归并排序，具有不同的特性。例如，快速排序在平均情况下更快，但在最坏情况下（如输入数组已经排序）性能会下降。而堆排序则提供了一个稳定的O(nlogn)时间复杂度，无论输入如何。归并排序在空间复杂度上较高，因为它需要额外的存储空间来辅助排序。

对比表格

以下是堆排序与其他两种常见排序算法的对比表格：

核心类与方法

堆排序的核心在于构建最大堆（或最小堆），然后进行一系列的下沉操作。在Java中，可以使用PriorityQueue类来实现堆的功能，或者自定义一个堆类来管理数组。

使用场景

堆排序适用于那些需要稳定时间复杂度的场景，尤其是当数据量较大时。它也常用于那些需要频繁查找最大（或最小）元素的应用，如求Top K问题。

代码案例

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

// 案例1：使用PriorityQueue实现堆排序
import java.util.PriorityQueue;

public class HeapSortExample1 {
    public static void heapSort(Integer[] array) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
        for (int i = 0; i < array.length; i++) {
            maxHeap.add(array[i]);
        }
        for (int i = 0; i < array.length; i++) {
            array[i] = maxHeap.poll();
        }
    }
    public static void main(String[] args) {
        Integer[] array = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        heapSort(array);
        System.out.println("Sorted array: " + java.util.Arrays.toString(array));
    }
}

// 案例2：自定义堆排序
public class HeapSortExample2 {
    public static void sort(int[] array) {
        int n = array.length;
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(array, n, i);
        for (int i = n - 1; i >= 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            heapify(array, i, 0);
        }
    }
    private static void heapify(int[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && array[left] > array[largest])
            largest = left;
        if (right < n && array[right] > array[largest])
            largest = right;
        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;
            heapify(array, n, largest);
        }
    }
    public static void main(String[] args) {
        int[] array = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        sort(array);
        System.out.println("Sorted array: " + java.util.Arrays.toString(array));
    }
}

以上两个案例分别展示了使用Java内置的PriorityQueue类实现堆排序以及自定义堆排序的方法。第一个案例更为简洁，而第二个案例则展示了如何手动实现堆排序算法的核心逻辑。

总结

通过本文，我们了解了堆排序算法的定义、目的、重要知识点、使用场景以及如何实现。堆排序作为一种稳定时间复杂度的排序算法，适用于各种大数据集的排序任务。希望这些知识能够帮助你更好地理解和应用堆排序。