排序算法之堆排序

傷城~ 2023-07-21 03:21 92阅读 0赞

**参考文章**：[https://blog.csdn.net/u010452388/article/details/81283998][https_blog.csdn.net_u010452388_article_details_81283998]

**1.堆的概述**

堆是具有以下特点的完全二叉树：  
（1）每个结点的值都大于或等于其左右子结点的值，称为大顶堆  
（2）或者每个结点的值都小于或等于其左右子结点的值，称为小顶堆

![format_png][]

对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

![format_png 1][]

堆中任意结点与其左右子结点及父结点的关系公式如下：

（也就是顺序存储二叉树的特点，顺序存储二叉树通常只考虑完全二叉树，堆是具有某些特点的完全二叉树）

（1） i : 表示堆中的第几个元素（也是该堆映射的数组下标）(按 i 从 0 开始编号)  
（2）第 i 个元素的左子结点为 2 \* i + 1  
（3）第 i 个元素的右子结点为 2 \* i + 2  
（4）第 i 个元素的父结点为 (i-1) / 2

该数组从逻辑上讲就是一个堆结构，用公式来描述堆的性质如下：  
（1）大顶堆：arr\[i\] >= arr\[2i+1\] && arr\[i\] >= arr\[2i+2\]  
（2）小顶堆：arr\[i\] <= arr\[2i+1\] && arr\[i\] <= arr\[2i+2\]

**2.堆排序的基本思想**

（1）将待排序数组中的 n 个元素构造成一个大顶堆，此时，数组中的最大值就在堆结构的顶端（即树的根结点）（映射到数组就是下标为 0 处的元素）  
（2）将顶端的数与末尾的数交换（通过数组完成），此时，末尾的数为最大值，数组中剩余待排序的元素个数为 n-1  
（3）将剩余的 n-1 个数再构造成大顶堆，再将顶端数与 n-2 位置的数交换，反复执行，就能得到有序数组

**3.堆排序的详解过程**

将无序数组构造成一个大顶堆（升序用大顶堆，降序就用小顶堆）

构造大顶堆的核心：新加入的数据与其父结点比较，确定新加入的数据的位置

假设存在以下数组

![70][]

3.1构造大顶堆的主要思路：

第一次保证 0~0 位置大顶堆结构（废话），第二次保证 0~1 位置大顶堆结构，第三次保证 0~2 位置大顶堆结构 ... 直到保证 0~n-1 位置大顶堆结构（每次新插入的数据都与其父结点进行比较，如果插入的数比父结点大，则与父结点交换，循环一直向上交换，直到小于等于父结点，或者来到了顶端）

（1）插入 6 的时候，6 大于它的父结点 3，即 arr(1) > arr(0) ，则交换；此时，保证了0~1位置是大顶堆结构，如下图

![70 1][]

(友情提示：待交换的数为蓝色，交换后的数为绿色)

（2）插入 8 的时候，8 大于它的父结点 6，即 arr(2) > arr(0) ,则交换；此时，保证了 0~2 位置是大顶堆结构，如下图

![70 2][]

（3）插入 5 的时候，5 大于它的父结点 3，即arr(3) > arr(1)，则交换，交换之后，5 又发现比 8 小，所以不交换；此时，保证了 0~3 位置大顶堆结构，如下图

![70 3][]

（4）插入 7 的时候，7 大于它的父结点 5，即arr(4) > arr(1)则交换，交换之后，7 又发现比 8 小，所以不交换；此时整个数组已经是大顶堆结构

![70 4][]

3.2固定最大值后数组剩下的元素继续构造成大顶堆  
（1）此时，我们已经得到一个大顶堆，下面将顶端的数与最后一位数交换，然后将剩余的数再构造成一个大顶堆

![70 5][]

（友情提示：黑色的为固定好的数字，不再参与排序）

此时最大数 8 已经来到末尾，则固定不动，后面只需要对顶端的数据进行操作即可，拿顶端的数与其左右孩子较大的数进行比较，如果顶端的数大于其左右孩子较大的数，则停止，如果顶端的数小于其左右孩子较大的数，则交换，然后继续与下面的孩子进行比较

（2）下图中，5 的左右孩子中，左孩子 7 比右孩子 6 大，则 5 与 7 进行比较，发现 5<7 ，则交换；交换后，发现 5 已经大于他的左孩子，说明剩余的数已经构成大顶堆，后面就是重复固定最大值，然后构造大顶堆

![70 6][]

（3）如下图：顶端数 7 与末尾数 3 进行交换，固定好 7

![70 7][]

（4）剩余的数开始构造大顶堆 ，然后顶端数与末尾数交换，固定最大值再构造大顶堆，重复执行上面的操作，最终会得到有序数组

![70 8][]

3.3上面的流程总结如下：  
（1）首先将无序数组构造成一个大顶堆（新插入的数据与其父结点比较）  
（2）然后固定一个最大值，将数组中剩余的数据重新构造成一个大顶堆，重复这样的过程

**4.代码实现**

package com.zzb.sort;
    
    import java.util.Arrays;
    
    /**
     * @Auther: Administrator
     * @Date: 2020/4/2 14:04
     * @Description: 堆排序
     */
    public class HeapSort {
        public static void main(String[] args) {
            // 无序数组
            int[] array = {3, 6, 8, 5, 7};
            // 堆排序
            heapSort(array);
            System.out.println(Arrays.toString(array));
        }
    
        /**
         * 堆排序
         *
         * @param array 无序数组
         */
        private static void heapSort(int[] array) {
            // 将 无序 数组构造成大顶堆这种逻辑结构映射的数组（新加入的节点与其父节点进行比较，确定去加入位置）
            heapInsert(array);
            int length = array.length;
            // 堆顶的值 与 堆末尾的值 交换位置，然后从堆顶开始将数组中剩余的元素重新构造为大顶堆
            while(length > 1) {
                // 固定最大值
                swap(array, 0, length - 1);
                // 相当于数组对应的堆结构在构造大顶堆时少一个节点
                length--;
                // 数组剩下的元素继续构造大顶堆
                heapify(array, 0, length);
            }
        }
    
        /**
         * 将无序数组构造成大顶堆（新加入的节点与其父节点进行比较，确定其加入位置）
         *
         * @param array 无序数组
         */
        private static void heapInsert(int[] array) {
            // 当前节点的指针
            int currentIndex;
            // 当前节点的父节点的指针
            int fatherIndex;
            // 循环取出数组中的所有元素来构造大顶堆
            for(int i = 0; i < array.length; i++) {
                currentIndex = i;
                fatherIndex = (currentIndex - 1) / 2;
                while(array[currentIndex] > array[fatherIndex]) {
                    // 如果当前节点的值大于父节点的值，则交换两个节点在数组中的位置，进行大顶堆的构造
                    swap(array, currentIndex, fatherIndex);
                    // 继续向上比较构造大顶堆
                    currentIndex = fatherIndex;
                    fatherIndex = (currentIndex - 1) / 2;
                }
            }
        }
    
        /**
         * 从堆顶开始将数组中剩余的元素重新构造为大顶堆
         *
         * @param array 待排序数组
         * @param index 堆顶（对应数组的下标 0 ）
         */
        public static void heapify(int[] array, int index, int length) {
            int maxIndex; // index节点 作为父节点的左右子结点中的最大值索引
            int leftValue; // index节点的左子节点值
            int rightValue; // index节点的右子节点值
            while(2*index+1 < length) { // index作为父节点节点 有 左子节点 才会执行（排序到最后只有一个顶端节点，根本不会执行到，即完成了堆排序）
                // 求出 index节点作为父节点的左右子结点中的最大值
                maxIndex = 2*index+1; // 最大值索引，默认为左子节点的索引
                // （不一定有右子节点，因为固定一个最大值后，数组的逻辑结构 堆 就相当于少了一个节点，而少的那一个节点必定是从右子节点开始的）
                leftValue = array[2*index+1]; // index作为父节点的左子节点值
                if(2*index+2 < length) { // index节点作为父节点存在右子节点
                    rightValue = array[2*index+2]; // index作为父节点的右子节点值
                    if(leftValue >= rightValue) {
                        maxIndex = 2*index+1;
                    }
                    if(leftValue < rightValue) {
                        maxIndex = 2*index+2;
                    }
                }
                // 比较父节点与最大值的关系，如果最大值大于父节点，则交换两者在数组中的位置，反之不做任何操作
                if(array[maxIndex] > array[index]) {
                    swap(array, maxIndex, index);
                    // 继续向下比较构造大顶堆
                    index = maxIndex;
                }
                // 相等，退出循环，剩下的数组元素成为了大顶堆这样的逻辑结构
                if(array[maxIndex] == array[index]) {
                    break;
                }
            }
        }
    
        /**
         * 交换两个元素在数组中的位置
         *
         * @param array 数组
         * @param x 大值下标（升序排序）
         * @param y 小值下标（升序排序）
         */
        private static void swap(int[] array, int x, int y) {
            int temp;
            temp = array[x];
            array[x] = array[y];
            array[y] = temp;
        }
    }

[https_blog.csdn.net_u010452388_article_details_81283998]: https://blog.csdn.net/u010452388/article/details/81283998
[format_png]: /images/20230528/b2e81a874e014b25a7fe3d7de813a406.png
[format_png 1]: /images/20230528/caf9c09968bc40beb79da2807dcae792.png
[70]: /images/20230528/453af62418424274a179a300a44d1805.png
[70 1]: /images/20230528/29bbd9708aaf4b91944e3d6dc331fb34.png
[70 2]: /images/20230528/54b7425151cb48c1bf850505a3559d7c.png
[70 3]: /images/20230528/7a5d524354dc4a72a003aa0df1619fe7.png
[70 4]: /images/20230528/a829d8c806e44e2984b96cd76dca40b0.png
[70 5]: /images/20230528/52becc8dbc074ec6b3eea5fbbe2737a2.png
[70 6]: /images/20230528/0b8cb8c1b9424e9aa5fcb27767434956.png
[70 7]: /images/20230528/838a8078c21c4d36af5dd38c6a795189.png
[70 8]: /images/20230528/759690048161475bb5f57997439f4725.png