堆排序【带图演示】

74 阅读 0 评论 49 点赞

我是靠谱客的博主淡淡乐曲，最近开发中收集的这篇文章主要介绍堆排序【带图演示】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、前提知识预备

在了解堆排序前，补充一下堆的知识吧，它的结构可以分为大根堆和小根堆，是一颗完全二叉树

大根堆和小根堆

每个节点的值都大于等于其左右节点的值称为大根堆，那小于等于就称为小根堆。如下图：
既然是个完全二叉树，节点之间有规则可言，假如已知节点的下标为 i，那么：
- 父节点的下标为：( i - 1 ) / 2
- 左孩子的下标为： i * 2 + 1
- 右孩子的下标为：i * 2 + 2
所以当一个数组要排序的时候，需要建立一个堆，并满足以下性质：
- 大根堆：arr[ i ] >= arr[ i * 2 + 1 ] && arr[ i ] >= arr[ i * 2 + 2 ]
- 小根堆：arr[ i ] <= arr[ i * 2 + 1 ] && arr[ i ] <= arr[ i * 2 + 2 ]

二、堆排序算法基本步骤

我这里构造大根堆，以下描述全部是大根堆

构造一个大根堆，这样，堆顶的数据是最大的
然后把堆顶的数据和末尾的元素交换，这样，待排序的元素长度就变了 n - 1，末尾的元素下标也随之 - 1
然后将剩下的 n - 1 个元素再次构造成大根堆，也是取堆顶的最大元素与末尾元素交换，如此反复，得到的是一个有序的数组。

1、构造堆

构造堆的具体步骤就不用演示了，比较容易，就拿上面的大根堆来举例子：

待排序数组为：
在这里插入图片描述

构造成大根堆：
1、依次插入 4 、3 、2，这里刚好都比父节点小，不需要变化
在这里插入图片描述
2、再插入 6 的时候，会发现 6 比父节点大，那就交换呗，先跟 3 交换，交换完后还是比父节点打了，那就继续交换

3、再插入8的时候，也需要交换

4、插入 9 的时候，也需要交换

5、最后插入 1 ，至此，大根堆已构建完毕
在这里插入图片描述

2、反复取出堆顶值和重构堆

现在为止，大根堆构建完毕，那就要开始操作了，现在堆顶的值为 9 ，与最后一个元素交换，如下图（黑色的为已经固定的值，下次构建不需要带上它）
在这里插入图片描述
现在重新构造大根堆，堆顶元素 1 与左右元素分别比较，谁最大交换谁，那就与 6 和 8 比较，8比较大，就与 8 交换，如下图：

现在堆顶元素变成了 8 ，然后把 8 和最后一个元素 1交换，然后再继续构建成大顶堆即可。。。
在这里插入图片描述
最后贴个整图

代码实现

/**
 * 堆排序  100 W 条数据平均耗时  0.158 s
 */
public class HeapSort {

    public static void headSort(int[] arr) {
        int length = arr.length;
        buildHead(arr, length);
        for (int i = length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            length--;
            sink(arr, 0, length);
        }
    }

    /**
     * 构建堆  建大堆
     *
     * @param arr
     * @param length
     */
    private static void buildHead(int[] arr, int length) {
        //倒数第一个非叶子节点索引
        int index = (length - 2) / 2;
        for (int i = index; i >= 0; i--) {
            sink(arr, i, length);
        }
    }

    /**
     * 下沉调整
     *
     * @param arr    数组
     * @param index  当前待调整节点的下标
     * @param length 待调整的数组长度
     */
    private static void sink(int[] arr, int index, int length) {
        //左儿子下标
        int leftChild = index * 2 + 1;
        //右儿子下标
        int rightChild = index * 2 + 2;
        //当前待调整节点下标，也就是左右儿子他爹
        int present = index;

        //leftChild < length  和  rightChild < length  是防止没有做左、右儿子
        if (leftChild < length && arr[leftChild] > arr[present]) {
            present = leftChild;
        }
        if (rightChild < length && arr[rightChild] > arr[present]) {
            present = rightChild;
        }

        //如果当天待调整节点下标不等于原来的下标，说明经过调换了，交换即可
        if (present != index) {
            int temp = arr[index];
            arr[index] = arr[present];
            arr[present] = temp;
            sink(arr, present, length);
        }
    }

    public static void main(String[] args) {
        Random random = new Random();
        int[] arr = new int[1000000];
        for (int i = 0; i < 1000000; i++) {
            int num = random.nextInt(3000000);
            arr[i] = num;
        }
        long start = System.currentTimeMillis();
        headSort(arr);
        long end = System.currentTimeMillis();
        System.out.println((end - start) / 1000.0);
    }
}