03-堆排序算法

数据结构可视化：堆排序算法排序过程

实现一个堆排序算法，并分析其时间复杂度和空间复杂度。

public class HeapSort {
    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;

            //在缩减堆上调用Max heapify
            heapify(arr, i, 0);
        }
    }

    //对以节点i为根的子树进行堆积，节点i是arr[]中的索引。N是堆的大小
    static void heapify(int[] arr, int n, int i) {
        int largest = i; //将最大初始化为根
        int l = 2 * i + 1; //left = 2*i + 1
        int r = 2 * i + 2; //right = 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);
        }
    }
}

堆排序是一种基于完全二叉树的排序算法，它利用了堆的性质来实现排序。堆排序分为两个步骤：建堆和排序。

建堆的过程可以分为两种方式：最大堆和最小堆。最大堆的特点是父节点的值大于等于其子节点的值，最小堆的特点是父节点的值小于等于其子节点的值。在建堆的过程中，我们需要从最后一个非叶子节点开始，逐个向上调整节点的位置，使得整个堆满足最大堆或最小堆的性质。

排序的过程是将堆顶元素与堆底元素交换位置，然后将堆的大小减1，重新调整堆的结构，使其满足最大堆或最小堆的性质。重复这个过程，直到堆的大小为1，排序完成。

堆排序的时间复杂度为O(nlogn)，其中n为待排序的元素个数。建堆的时间复杂度为O(n)，排序的时间复杂度为O(nlogn)。空间复杂度为O(1)，因为堆排序算法只需要一个额外的空间来存储堆。

验证：

public static void main(String[] args) {
    int[] nums = {6, 3, 5, 1, 2, 8, 4, 9};
    HeapSort.sort(nums);
    //nums = [1, 2, 3, 4, 5, 6, 8, 9]
    System.out.println("nums = " + Arrays.toString(nums));
}