堆排序就这么简单

NickZhou 发布于2019-08-19 10:43 / 1283人阅读

摘要：一堆排序介绍来源百度百科堆排序是指利用堆积树堆这种数据结构所设计的一种排序算法，它是选择排序的一种。

一、堆排序介绍

来源百度百科：

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。

前面我已经有二叉树入门的文章了，当时讲解的是二叉查找树，那上面所说的完全二叉树是怎么样的一种二叉树呢？？还有满二叉树又是怎么的一种二叉树呢？？甚至还有完满二叉树？？

完全二叉树：除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。

满二叉树：除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。

完满二叉树：除了叶子结点之外的每一个结点都有两个孩子结点。

下面用图来说话：

完全二叉树(Complete Binary Tree)：

满二叉树(Perfect Binary Tree)：

完满二叉树(Full Binary Tree)：

参考资料：

http://www.cnblogs.com/idorax/p/6441043.html

简单来说：堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法

最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其左右孩子

那么处于最大堆的根节点的元素一定是这个堆中的最大值

这里我们讨论最大堆：当前每个父节点都大于子节点

完全二叉树有个特性：左边子节点位置 = 当前父节点的两倍 + 1，右边子节点位置 = 当前父节点的两倍 + 2

二、堆排序体验

现在我们有一个完全二叉树：左子树和右子树都符合最大堆-->父>子

但是我们会发现：根元素所在的数并不符合，明显的是：1是小于7的

我们就对其进行交换，交换完之后我们会发现：右子树又不符合了～

因为，右子树变成了这样：

最后，我们将右子数的最大值也交换到右子树的根元素上

于是我们第一次的建堆操作就完成了！

可以发现的是：一次堆建立完之后，我们的最大值就在了堆的根节点上

随后将堆顶最大值和数组最后的元素进行替换，我们就完成了一趟排序了。

接下来，剩下的数不断进行建堆，交换就可以完成我们的堆排序了

.........建堆，交换....建堆，交换...建堆，交换...建堆，交换..

三、堆排序代码实现

比较当前父节点是否大于子节点，如果大于就交换，直到一趟建堆完成～

    /**
     * 建堆
     *
     * @param arrays          看作是完全二叉树
     * @param currentRootNode 当前父节点位置
     * @param size            节点总数
     */
    public static void heapify(int[] arrays, int currentRootNode, int size) {

        if (currentRootNode < size) {
            //左子树和右字数的位置
            int left = 2 * currentRootNode + 1;
            int right = 2 * currentRootNode + 2;

            //把当前父节点位置看成是最大的
            int max = currentRootNode;

            if (left < size) {
                //如果比当前根元素要大，记录它的位置
                if (arrays[max] < arrays[left]) {
                    max = left;
                }
            }
            if (right < size) {
                //如果比当前根元素要大，记录它的位置
                if (arrays[max] < arrays[right]) {
                    max = right;
                }
            }
            //如果最大的不是根元素位置，那么就交换
            if (max != currentRootNode) {
                int temp = arrays[max];
                arrays[max] = arrays[currentRootNode];
                arrays[currentRootNode] = temp;

                //继续比较，直到完成一次建堆
                heapify(arrays, max, size);
            }
        }
    }

值得注意的是：在上面体验堆排序时，我们是左子树和右子数都是已经有父>子这么一个条件的了。

显然，一个普通的数组并不能有这种条件(父>子)，因此，我们往往是从数组最后一个元素来进行建堆

    /**
     * 完成一次建堆，最大值在堆的顶部(根节点)
     */
    public static void maxHeapify(int[] arrays, int size) {

        // 从数组的尾部开始，直到第一个元素(角标为0)
        for (int i = size - 1; i >= 0; i--) {
            heapify(arrays, i, size);
        }

    }

完成第一次建堆之后，我们会发现最大值会在数组的首位：

接下来不断建堆，然后让数组最后一位与当前堆顶(数组第一位)进行交换即可排序：

    for (int i = 0; i < arrays.length; i++) {

        //每次建堆就可以排除一个元素了
        maxHeapify(arrays, arrays.length - i);

        //交换
        int temp = arrays[0];
        arrays[0] = arrays[(arrays.length - 1) - i];
        arrays[(arrays.length - 1) - i] = temp;

    }

四、总结

堆排序是比其他排序要难一点，他用到了完全二叉树这么一个特性来进行排序，代码实现上也比其他排序要复杂一点。

参考资料：

http://www.cnblogs.com/skywang12345/p/3602162.html

如果文章有错的地方欢迎指正，大家互相交流。习惯在微信看技术文章，想要获取更多的Java资源的同学，可以关注微信公众号:Java3y

云服务器 GPU云服务器堆排序堆排序算法堆排序排序c语言 python的堆排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76363.html

方法和数组就是这么简单！

摘要：数组就是一个简单的线性序列，这使得元素访问非常快速。堆区堆内存用来存放创建的对象和数组。堆内存中的实体不再被指向时，启动垃圾回收机制，自动清除，这也是优于的表现之一中需要程序员手动清除。 showImg(https://segmentfault.com/img/remote/1460000019264541?w=600&h=242); 第三章方法和数组 3.1 概述还记得我们的He...

darkerXi 2019-08-16 17:40 评论0 收藏0
基于 Javascript 排序算法

摘要：适用于数据比较少或基本有序的情况。插入排序时间复杂度为，空间复杂度为，属于稳定排序。算法适用于少量数据的排序。就像下图这样，可以理解桶的意思下图是整个排序过程示意图基数排序时间复杂度为，空间复杂度为，属于稳定排序。写在前面个人感觉：javascript对类似排序查找这样的功能已经有了很好的封装，以致于当我们想对数组排序的时候只需要调用arr.sort()方法，而查找数组元素也只需要...

tommego 2019-08-23 11:47 评论0 收藏0
希尔排序就这么简单

摘要：这时就用简单插入排序将数列直至已序从直观上看希尔排序就是把数列进行分组不停使用插入排序，直至从宏观上看起来有序，最后插入排序起来就容易了无须多次移位或交换。一、希尔排序介绍来源百度百科：希尔排序(Shells Sort)是插入排序的一种又称缩小增量排序（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方...

paulli3 2019-08-19 10:43 评论0 收藏0
Java3y文章目录导航

摘要：前言由于写的文章已经是有点多了，为了自己和大家的检索方便，于是我就做了这么一个博客导航。前言由于写的文章已经是有点多了，为了自己和大家的检索方便，于是我就做了这么一个博客导航。由于更新比较频繁，因此隔一段时间才会更新目录导航哦～想要获取最新原创的技术文章欢迎关注我的公众号：Java3y Java3y文章目录导航 Java基础泛型就这么简单注解就这么简单 Druid数据库连接池...

KevinYan 2019-08-15 15:13 评论0 收藏0