Java排序算法（七）堆排序

堆排序

二叉树

二叉树： 当前结点最多有两个子树的树结构。如下：

😀根结点： 没有父结点的结点，如图中的7；
😁左孩子： 二叉树中一个结点的左分支，如图中的4；
😂右孩子： 二叉树中一个结点的右分支，如图中的3；
🤣叶子结点： 也叫终端结点，是度为 0 的结点，如图中的6 8 0 1；
😊分枝结点： 度不为0的结点，如图中的4 3 2；
😎完全二叉树： 二叉树上的每一层都是满的，或者最后一层没填满并且最后一层的叶子结点都是靠最左边存放，图中的二叉树就是一个完全二叉树。

大顶堆和小顶堆

堆是一颗顺序存储的完全二叉树，分为大顶堆和小顶堆。
😜大顶堆： 每个结点的值大于等于其左、右孩子的值，这样的堆称为大顶堆。
如图示例：

大顶堆特点： arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2 * i + 2] 其中i对应第几个节点，i从0开始编号。

😝小顶堆： 每个结点的值小于等于其左、右孩子的值，这样的堆称为小顶堆。

小顶堆特点： arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2 * i + 2] 其中i对应第几个节点，i从0开始编号。

算法思想

堆排序是指利用堆这种数据结构进行设计的一种排序算法。堆排序利用了大顶堆（或小顶堆）堆顶记录的关键字最大（最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。 一般升序排序采用大顶堆，降序排序采用小顶堆。

算法描述

堆排序首先是根据元素构建堆。然后将堆的根节点取出（一般是与最后一个节点进行交换），将前面 len - 1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。
用大顶堆排序的基本思想
① 先将待排序序列建成一个大顶堆，此堆为初始的无序。
② 此时，整个序列的最大值就是堆顶的根节点。
③ 将其与末尾元素进行交换，此时末尾就是最大值。
④ 然后将剩余n-1个元素重新建成一个堆，这样会得到n个元素的次小值。如此反复执行，便得到一个有序的序列了。

算法图示

要求:给你一个数组 {4,6,8,5,9}，要求使用堆排序法，将数组升序排序。
步骤一： 构造初始堆。将给定的无序序列构造成一个大顶堆。原始数组： {4,6,8,5,9}
① 假定给定的无序序列结构如下

② 此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length / 2 - 1 = 1，也就是下面的6结点），从左到右，从下到上进行调整。

③找到第二个非叶子结点4，由于【4 9 8】中9最大，4和9交换。

④这时，交换了导致【4 5 6】结构混乱，继续调整，【4 5 6】中6最大，4和6交换。

此时我们就将一个无序序列构造成了一个大顶堆。

步骤二：将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
①将堆顶元素9和末尾元素4进行交换。

②重新调整结构，使其继续满足堆定义。

③再将堆顶元素8与末尾元素5进行交换，得到第二大元素8。

④后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序。

代码演示

import java.util.Arrays;

public class SortTest07 {
    public static void adjust(int[] arr,int begin,int end) {
        //1.保存begin位置的值
        int temp = arr[begin];
        //2.挑选左右孩子中的较大值
        for (int i = 2 * begin + 1;i <= end;i = 2 * i + 1) {
            if (i + 1 <= end && arr[i] < arr[i + 1]) {
                i = i + 1;
            }
            //3.较大值与begin位置的值比较
            if (arr[i] > temp ) {
                arr[begin] = arr[i];
                begin = i;//交换以后 更新begin
            }else {
//                arr[begin] = temp;
                break;
            }
        }
        //越界了，最后把temp值赋给begin位置的值
        arr[begin] = temp;

    }
    public static void heapSort(int[] arr) {
        //将堆调整成大根堆的形式(从倒数第一个非叶子结点开始)
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            adjust(arr,i,arr.length - 1);
        }
        //交换0号下标元素和“相对最后”的元素
        for (int i = 0;i < arr.length;i++) {
            int temp = arr[0];
            arr[0] = arr[arr.length - 1 - i];
            arr[arr.length - 1 - i] = temp;
            adjust(arr,0,arr.length - 1 - 1 - i);
        }

    }

    public static void main(String[] args) {
        int[] arr = {4,6,8,5,9};
        System.out.println("排序前:" + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

运行结果：

堆排序算法分析

🙈时间复杂度： 最优时间复杂度：O(nlog₂n)，平均时间复杂度：O(nlog₂n)，最坏时间复杂度：O(nlog₂n)
🙊空间复杂度： O(1)
🙉稳定性分析： 不稳定