堆排序

tangr206 发布于2019-08-16 12:30 / 1972人阅读

摘要：计算机算法理论简介建立初始堆首末元素互换即得到最大元素放入数组最末尾调整堆第二步的操作明显会将堆破坏所以需要调整堆跳回第二步建立初始堆在建堆之前需要将数组转成二叉树图方便理解如果将父左子右子当做树的最小单元组称为父子单元那么只需要保证每个父

@(Study)[计算机, 算法]

理论简介

建立初始堆

首末元素互换, 即得到最大元素放入数组最末尾.

调整堆. 第二步的操作明显会将堆破坏, 所以需要调整堆.

跳回第二步.

建立初始堆

在建堆之前需要将数组转成二叉树图, 方便理解:

如果将父>左子|右子当做树的最小单元组, 称为父子单元, 那么只需要保证每个父子单元满足最大堆规则, 那么整体树就满足了最大堆.
==>定义一个方法(unitAdjust())用来调整父子单元, 将单元中最大的值推到该单元的根部, 成为父, 原来的父降到最大值之前的位置, 作为子. 但是这样有可能使得以这个新子为父结点的下一层的父子单元不满足最大堆规则. ==>设置规则, 如果发生了交换, 则递归调用方法自身, 调整新子为父结点的父子单元. 如此反复.

上述过程可以说是自上而下的下钻过程.

但是如果使得整个树成为最大堆, 那么就是需要针对树中的每个父子单元进行调整. 只需要对树中的每个非叶子节点进行遍历, 使用上述方法unitaAdjust()调整即可. 进一分析, 可以发现这里有个问题: 遍历的方向是自上而下还是自下而上呢?

如果自上而下会出现什么情况呢?
如下图, 第一趟循环中, 操作的对象是以根结点34为父结点的父子单元. 循环体内部将调用unitAdjust(), 34和50将互换, 由于发生了交换, unitAdust()方法将发生递归调用, 去操作以新子34为父结点的父子单元, 经过比较, 未发生交换情况, 第一趟循环结束. 图中发生了比较或者互换的位置以绿色标出, 这时聪明的你不难发现, 当程序向下遍历走到第三个节点时, 便发生了重复比较, 当然你或许能够想到规避重复比较的方法, 但是我是没有想出, 或者也可以认为重复比较无所谓.

其实, 换一种思路, 进行自下而上遍历情况就完全不一样了.

从最后一个非叶子节点67开始, 67↔90

50节点不动

23↔90, 触发下钻机制.

23↔67

34↔90, 触发下钻机制

34↔67, 再次下钻

未动

最终得到初始堆如下图所示, 其中蓝色表示交换过位置.

可见, 整体是自下而上遍历, 具体单元操作时采取自上而下, 总之, 自上而下和自下而上的相结合.

建立堆的过程其实有点冒泡的味道, 数值大逐渐的冒到上面, 好像密度大的即使开始在水底部, 但随着遍历, 密度大的终将上浮到上部.

堆排序

初始堆建立好了后, 堆顶的元素自然就是最大值, 于是将第一个元素和最后一个元素互换, 即完成将最大值放到最末尾, 完了第一次排序.

由于交换使得堆被破坏, 所以需要对的n-1个元素进行调整, 使其成为堆. 具体做法就是调用unitAdjust()对以根节点为父结点的父子单元进行调整, 刚换来的最末位元素自然会被移到子节点位置, 这样递归调用机制被触发, 于是继续保证所有下层调整为堆.

接着将倒数第二个元素和堆顶元素互换, ......如此反复.

代码实现

思路:

//建立初始堆//
for (i=n/2;i>=1;i--) {
    unitAdjust()
}
//堆排序//
for (i=n; i>=1; i--) {
    首末交换
    unitAdjust()调整
}

Java代码:

测试结果:

10亿长度, 内存爆掉;

1亿长度, 35693ms.

package LearningLog;

/*
 * - 10亿长度, 内存爆掉
 * - 1亿长度, 35693ms.
 */

public class demo25 {
    public static void main(String[] args) {
        int[] arr=MyJava.randomArr(100000000, 10000,123);
//        System.out.println(Arrays.toString(arr));
//        initHeap(arr);
        long t0 = System.currentTimeMillis();
        heapSort(arr);
        long t1 = System.currentTimeMillis();
        System.out.println((t1-t0)+"ms");
//        System.out.println(Arrays.toString(arr));
    }
    /* ====unitAdjust()===========================================
     * 父子单元调整
     * I: 父结点的索引, 数组长度: 非常非常非常关键, 因为后续调用的时候, 需要卡住最大的遍历位置, 否则将会将尾部已经排好序的较大数值顶到上面去了, 那就糟糕呕吐了
     */
    public static void unitAdjust(int array[],int fatherNode, int sub_size) {
        int lchild = 2*fatherNode+1;
        int rchild = lchild+1;

        int max = fatherNode; // 默认最大值索引就是父结点的索引
        int tmp = 0;
        if (fatherNode=0; i--) {
            unitAdjust(array, i, array.length);   //大的值不断上浮
        }

    }
    
    /*
     * ====heapSort()=================================================
     * 堆排序
     */
    public static void heapSort(int[] array) {
        int tmp=0;
        //建立堆//
        initHeap(array);
        for(int i=array.length-1; i>=0; i--) {
            //首尾互换/
            tmp = array[i];
            array[i] = array[0];
            array[0] = tmp;
            
            //剩下的i-1个元素需要调整//
            unitAdjust(array, 0, i); //始终只用调整第一个父子单元即可
        }
    }
    
    
    
    
    
}

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

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

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

JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

摘要：之所以把归并排序快速排序希尔排序堆排序放在一起比较，是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此，快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 评论0 收藏0
七大排序算法总结(java)

摘要：前面介绍了七大算法的思想与实现步骤，下面来做一个归总。直到无序区中的数为零，结束排序。步骤以从小到大为例，排序数组大小为。比较完以后则排序结束。堆排序思想堆排序是采用树的形式的数据结构来进行排序的，其中每一个堆都是完全二叉树。前面介绍了七大算法的思想与实现步骤，下面来做一个归总。排序方法平均复杂度最坏复杂度最好复杂度辅助空间稳定性直接选择排序 O(n^2...

cartoon 2019-08-14 14:09 评论0 收藏0
堆排序就这么简单

摘要：一堆排序介绍来源百度百科堆排序是指利用堆积树堆这种数据结构所设计的一种排序算法，它是选择排序的一种。一、堆排序介绍来源百度百科：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。前面我已经有二叉树入门的文章了，当时讲解的是二叉查找树，那上面所说的完全二...

NickZhou 2019-08-19 10:43 评论0 收藏0
基础算法学习之(三):堆排序

摘要：奇妙的记忆点不稳定内排序基本思想分为两步建堆与维持堆的性质首先我们要先理解堆是什么东西堆其实就是一个完全二叉树我们可以使用顺序表存储一个二叉树如下图所示来存储其中分为最大堆最小堆而最大堆就是上头大下头小最小堆则反之明白了堆的定义我们就可以开奇妙的记忆点: 不稳定内排序基本思想: 分为两步,建堆与维持堆的性质,首先我们要先理解堆是什么东西.堆其实就是一个完全二叉树,我们可以使用...

mrli2016 2019-08-20 11:34 评论0 收藏0
常见八大排序（C语言实现）及动图演示

摘要：当到达时等同于直接插入排序，此时序列已基本有序，所有记录在统一组内排好成有序序列。当面对大量数据时，希尔排序将比直接插入排序更具优势图示讲解第一趟取增量，所有间隔为的元素分在一组，在各个组中分别进行直接插入排序。 ...

不知名网友 2021-11-26 11:11 评论0 收藏0