堆排序

概念

堆排序是选择排序的一种，堆通常是一个可以被看做一棵完全二叉树的数组对象。
堆是一种不稳定的内部排序算法，时间复杂度无论最好，最差，平均都是$log(n)$,此处n表示待排序元素个数。

• 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
• 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

补充

不稳定排序：数组中相同的元素，在经过排序，前后顺序会发生变化，即不稳定。细节可参照数据结构严蔚敏版。
内部排序：只在内存中进行的排序，不会有数据和磁盘进行交换。

性质

以下假设构造大根堆，则堆必须满足以下要求：

• 堆是一个完全二叉树，这样才能保证根节点i能直接2*i的方式映射到孩子节点
• 根节点必须大于左右孩子节点

步骤

提供一组数据，这组数据为堆对应完全二叉树的层次遍历结果，使用堆排序完成升序排序（构造大根堆）

1. 构建大根堆
2. 交换堆顶和堆最后一个元素（把此轮最大值放到数组后方，后续只对剩下的无序堆排序，每次排序少一个需要排序的元素）
3. 调整剩下的无序堆为有序大根堆：从最后一个非叶子节点，从下往上，从左往右（利用性质一），之后2，3不交替进行，直至需要带排序元素个数为0.

点此链接，可以查看在线效果图

代码

Java版本

package sort.exchange;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author ShaoYJ
 * @date 2022/10/7 周五
 * @desc 选择排序的一种，主要分为三步，
 * 1. 构建一个堆
 * 2. 将堆顶元素与末尾元素交换
 * 3. 重新调整结构，2和3交替执行
 */
public class HeapSort {
    public static void main(String[] args) {
//       输入测试参数
//        Scanner sc = new Scanner(System.in);
//        ArrayList<Integer> list = new ArrayList<>();
//        System.out.print("输入一串数字，空格分开，以#结束:");
//        while (!sc.hasNext("#")) {
//            int a = sc.nextInt();
//            list.add(a);
//        }
//        Integer[] arr = new Integer[list.size()];
//        list.toArray(arr);

//        Integer[] arr = {6, 5, 4, 3, 2, 1};
        Integer[] arr = {1, 2, 3, 4, 5, 6};
        System.out.println("排序前：" + Arrays.toString(arr));
        sort(arr);
        System.out.println("排序前：" + Arrays.toString(arr));
    }

    public static void sort(Integer[] arr) {
        /**
         * 第一步 ：构建大顶堆
         *  1. 堆可以看为完全二叉树，
         *  2. 从最后一个非叶子节点开始从下往上， 从右向左构建
         *  3. 因此 索引i的初始值为最后一个非叶子节点的索引
         *  4. 从arr的后面往前移动一个一个大调整堆
         */
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }

        //2,3步 => 调整堆结构+交换堆顶元素与末尾元素
        for (int j = arr.length - 1; j > 0; j--) {
            //第二步 ： 将堆顶元素与末尾元素进行交换
            int temp = arr[0];
            arr[0] = arr[j];
            arr[j] = temp;
            // 第三步 ：只需要对剩余的元素重新进行调整
            adjustHeap(arr, 0, j-1);
        }

    }

    /**
     *
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(Integer[] arr, int i, int length) {
//        把根节点的值保存下来。
        int temp = arr[i];
        /*
         * 从i结点的左子结点开始，也就是2i+1处开始,
         * 存在一层调整后，下一层不满足的情况，需要把整棵子树都调整
         * 例如 子树为 1 5 3 2 -》 1和 5交换之后，5 1 3 2 ，还要继续 交换2*i+1 【数值1】和 2*(2*i+1)+1 【数值2】
         */
        for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
            // 如果存在右孩子节点， 指针需要指向大的子节点
            if(j+1<length){
                j = arr[j] > arr[j + 1] ? j : j + 1;
            }
//           如果子节点的值大于根节点，交换值
            if (arr[j] > temp) {
//                父节点的值修改为子节点值
                arr[i] = arr[j];
//                子节点值设置为原本父节点的值
                arr[j] = temp;
//                及时同步原本父节点的指针为子节点指针，并开始下一轮调整
                i = j;
            }
//           根节点>大的那个子节点  即 根节点大于所有节点
            else {
                break;
            }

        }
    }
}

学习收获

• 堆排序不稳定。
• 堆排序可以视作完全二叉树。
• 注意Java代码难点部分，for (int j = i * 2 + 1; j < length; j = j * 2 + 1) 可以先画图理解后，对应索引变化编写代码。