堆排序

堆排序（Heap Sort）是一种基于比较的排序技术，利用了二叉堆的数据结构。堆排序可以分为两种主要类型：最大堆和最小堆。在最大堆中，父节点总是大于或等于其子节点；而在最小堆中，父节点总是小于或等于其子节点。堆排序利用堆这种特性来高效地排序元素。

堆是一种特殊的完全二叉树，它满足以下性质：

• 形状性质：堆是一棵完全二叉树。
• 堆序性质：对于任意节点C，若P是C的父节点，则$Parent(C)\le C$ 或 $Parent(C)\ge C$（取决于是最大堆还是最小堆）。

基本思想

堆排序的基本思想是：

1. 构建一个最大堆（或最小堆），此时堆顶元素就是所有元素中的最大值（或最小值）；
2. 将堆顶元素与最后一个元素交换，然后去除最后一个元素，将其从堆中排除；
3. 调整剩余的元素使其满足堆的性质，重新构建最大堆；
4. 重复步骤2和3，直到所有元素都被取出，完成排序。

代码实现

查看代码

public class HeapSort {

    // 用于调整最大堆的方法
    private static void heapify(int[] arr, int heapSize, int rootIndex) {
        int largest = rootIndex; // 初始化根节点为最大值
        int leftChild = 2 * rootIndex + 1; // 左子节点
        int rightChild = 2 * rootIndex + 2; // 右子节点

        // 如果左子节点比根节点大，则更新最大值索引
        if (leftChild < heapSize && arr[leftChild] > arr[largest])
            largest = leftChild;

        // 如果右子节点比当前最大值还大，则更新最大值索引
        if (rightChild < heapSize && arr[rightChild] > arr[largest])
            largest = rightChild;

        // 如果最大值不是根节点，则交换它们，并递归地调整受影响的子树
        if (largest != rootIndex) {
            int swap = arr[rootIndex];
            arr[rootIndex] = arr[largest];
            arr[largest] = swap;
            heapify(arr, heapSize, largest);
        }
    }

    // 主要的堆排序方法
    public static 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);
        }
    }

    // 打印数组的方法
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("原始数组:");
        printArray(arr);
        
        sort(arr);
        
        System.out.println("排序后的数组:");
        printArray(arr);
    }
}

时间复杂度

堆排序的时间复杂度为 $O(nlogn)$，无论是在最好情况、平均情况还是最坏情况下都是如此。

这是因为每次heapify操作的时间复杂度为$O(logn)$，而构建初始堆以及后续的$n$次heapify操作都需要线性数量级的操作。

空间复杂度

堆排序是一种原地排序算法，除了需要存储数组本身之外，不需要额外的存储空间，因此它的空间复杂度为 $O(1)$。