堆排序 订阅
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 展开全文
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
信息
外文名
Heapsort
发明人
罗伯特·弗洛伊德
类    别
排序算法
中文名
堆排序
起源于
罗伯特·弗洛伊德
堆排序简介
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 [1] 
收起全文
精华内容
下载资源
问答
  • 主要介绍了Python实现堆排序的方法,结合实例形式详细分析了堆排序的原理,实现方法与相关注意事项,需要的朋友可以参考下
  • 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 堆排序的平均时间复杂度为Ο...
  • 1) 至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。 2) 统计每一种排序方法的性能(以上机...
  • 堆排序

    2021-01-20 11:36:38
    文章目录堆排序 堆排序 想要了解堆排序,最好先掌握堆的基本操作。 思路 思考取出堆元素的操作,每取出一个元素,堆里面的元素就减少一个,但是存储堆元素的数组空间大小是不变的。所以可以把一个元素从堆取出后,将...
  • 主要介绍了C语言实现基于最大堆和最小堆的堆排序算法示例,分别是基于最大堆的升序排序和基于最小堆的降序排序实例,需要的朋友可以参考下
  • 课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • 堆排序(R)

    2018-04-20 21:28:39
    在排序算法中,堆排序是一个快速排序方法,下面是我用R语言编写的最大堆排序
  • 堆排序动画演示

    2018-01-10 20:02:59
    仔细讲解了堆排序的过程,通过动画进行演示,适合用作课堂展示,也适合自己学习。
  • 本文实例为大家分享了C语言堆排序源代码,供大家参考,具体内容如下 1. 堆排序 堆排序的定义及思想可以参考百度百科: 用一句概括,堆排序就是一种改进的选择排序,改进的地方在于,每次做选择的时候,不单单把最大...
  • 堆排序 1.原理 2.实现 3.性能分析 堆排序 1.原理 基本原理也是选择排序,只是不再使用遍历的方式查找无序区间的最大数,而是通过堆来选择无序区间的最大数 升序:大顶堆;降序:小顶堆 堆排序的基本思路: a.将无需...
  • 找工作期间整理的各种排序方式。有相关的Java代码和时间复杂度空间复杂度分析。
  • 把待排序的数组构造出最大堆是进行堆排序操作的基本方法,这里将带大家来解读堆排序算法及用C++实现基于最大堆的堆排序示例,首先从堆排序的概念开始:
  • 堆排序之Java实现

    2017-07-27 17:03:37
    堆排序算法Java实现
  • C#堆排序实现方法

    2020-09-03 20:41:21
    主要介绍了C#堆排序实现方法,实例分析了C#对排序的实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • 堆排序及其用途

    2016-03-25 13:46:16
    以前徐老师要我讲课的时候自己打的课件……现在是时候放上来了……
  • C++实现希尔、快速、堆排序、归并排序算法,一些中文注释可能成乱码了,但是不影响代码执行。
  • 堆排序 对一个含有N整数的数组,使用堆排序让其由小到大输出 样例输入 6 43 2 56 1 22 9 样例输出 1 2 9 22 43 56 堆排序 对一个含有N整数的数组,使用堆排序让其由小到大输出 样例输入 6 43 2 56 1 22 9 样例...
  • 堆与堆排序 软件学院王建文 752堆和堆排序 堆和堆排序的概念 堆的调整 建堆 四堆排序 堆的定义: 若n个元素的序列{a1a2an}满足 或 a:a1 al1a2i+1 aa2i+1 则分别称该序列{a1a2,an}为小根堆和大根堆 从堆的定义可以看出...
  • 堆排序算法c语言实现

    2015-10-25 14:24:42
    学习堆排序时自己编的代码,里面有自动生成随机数的代码段方便大家测试
  • 数据结构堆排序.ppt

    2020-08-03 05:02:57
    数据结构精品资源共享课 选择排序之排序 主讲人:程玉胜 2013.12.20 知识点引入 内容提要 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序 内容提要 堆定义及其存储 建堆 堆排序 堆定义及其存储 ...
  • C++堆排序实现算法

    2015-06-01 00:44:16
    简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
  • 本篇文章主要介绍了堆排序的简介,定义,算法实现以及堆排序的性质。想要了解的朋友可以参考下
  • 数据结构——堆排序 数据结构——堆排序 数据结构——堆排序 数据结构——堆排序 数据结构——堆排序 数据结构——堆排序
  • 主要介绍了C语言实现堆排序的简单实例,讲述了堆排序的原理,需要的朋友可以参考下
  • 主要介绍了堆排序算法(选择排序改进),有需要的朋友可以参考一下
  • 如果将堆理解为二叉树,那么树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字,堆排序的时间复杂度为O(N*logN),这里我们就来详解堆排序算法原理及Java版的代码实现
  • 堆排序算法(图解详细流程)

    万次阅读 多人点赞 2018-08-04 11:21:17
    堆排序的时间复杂度O(N*logN),额外空间复杂度O(1),是一个不稳定性的排序 目录 一 准备知识 1.1 大根堆和小根堆 二 堆排序基本步骤 2.1 构造堆 2.2固定最大值再构造堆 三 总结 四代码 一 准备知识 堆的...

    堆排序的时间复杂度O(N*logN),额外空间复杂度O(1),是一个不稳定性的排序

    目录

    一 准备知识

    1.1  大根堆和小根堆

    二 堆排序基本步骤

    2.1 构造堆

    2.2 固定最大值再构造堆

    三 总结

    四 代码

     


    一 准备知识

    的结构可以分为大根堆和小根堆,是一个完全二叉树,而堆排序是根据的这种数据结构设计的一种排序,下面先来看看什么是大根堆和小根堆

    1.1  大根堆和小根堆

    性质:每个结点的值都大于其左孩子和右孩子结点的值,称之为大根堆;每个结点的值都小于其左孩子和右孩子结点的值,称之为小根堆。如下图

     我们对上面的图中每个数都进行了标记,上面的结构映射成数组就变成了下面这个样子

    还有一个基本概念:查找数组中某个数的父结点和左右孩子结点,比如已知索引为i的数,那么

    1.父结点索引:(i-1)/2(这里计算机中的除以2,省略掉小数)

    2.左孩子索引:2*i+1

    3.右孩子索引:2*i+2

    所以上面两个数组可以脑补成堆结构,因为他们满足堆的定义性质:

    大根堆:arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)

    小根堆:arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)

    二 堆排序基本步骤

    基本思想:

    1.首先将待排序的数组构造成一个大根堆,此时,整个数组的最大值就是堆结构的顶端

    2.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1

    3.将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组

    2.1 构造堆

    将无序数组构造成一个大根堆(升序用大根堆,降序就用小根堆)

    假设存在以下数组

    主要思路:第一次保证0~0位置大根堆结构(废话),第二次保证0~1位置大根堆结构,第三次保证0~2位置大根堆结构...直到保证0~n-1位置大根堆结构(每次新插入的数据都与其父结点进行比较,如果插入的数比父结点大,则与父结点交换,否则一直向上交换,直到小于等于父结点,或者来到了顶端)

    插入6的时候,6大于他的父结点3,即arr(1)>arr(0),则交换;此时,保证了0~1位置是大根堆结构,如下图:

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

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

    插入5的时候,5大于其父结点3,则交换,交换之后,5又发现比8小,所以不交换;此时,保证了0~3位置大根堆结构,如下图 

    插入7的时候,7大于其父结点5,则交换,交换之后,7又发现比8小,所以不交换;此时整个数组已经是大根堆结构 

     

    2.2 固定最大值再构造堆

    此时,我们已经得到一个大根堆,下面将顶端的数与最后一位数交换,然后将剩余的数再构造成一个大根堆

                                        (友情提示:黑色的为固定好的数字,不再参与排序) 

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

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

    如下图:顶端数7与末尾数3进行交换,固定好7,

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

     

    三 总结

    到这里,大家应该对堆排序都有了自己的见解,我们对上面的流程总结下:

    1、首先将无需数组构造成一个大根堆(新插入的数据与其父结点比较)

    2、固定一个最大值,将剩余的数重新构造成一个大根堆,重复这样的过程

    四 代码

    代码中主要两个方法:

    1、将待排序数组构造成一个大根堆(元素上升)

    2、固定一个最大值,将剩余的数再构造成一个大根堆(元素下降)

        //堆排序
        public static void heapSort(int[] arr) {
            //构造大根堆
            heapInsert(arr);
            int size = arr.length;
            while (size > 1) {
                //固定最大值
                swap(arr, 0, size - 1);
                size--;
                //构造大根堆
                heapify(arr, 0, size);
    
            }
    
        }
    
        //构造大根堆(通过新插入的数上升)
        public static void heapInsert(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                //当前插入的索引
                int currentIndex = i;
                //父结点索引
                int fatherIndex = (currentIndex - 1) / 2;
                //如果当前插入的值大于其父结点的值,则交换值,并且将索引指向父结点
                //然后继续和上面的父结点值比较,直到不大于父结点,则退出循环
                while (arr[currentIndex] > arr[fatherIndex]) {
                    //交换当前结点与父结点的值
                    swap(arr, currentIndex, fatherIndex);
                    //将当前索引指向父索引
                    currentIndex = fatherIndex;
                    //重新计算当前索引的父索引
                    fatherIndex = (currentIndex - 1) / 2;
                }
            }
        }
        //将剩余的数构造成大根堆(通过顶端的数下降)
        public static void heapify(int[] arr, int index, int size) {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            while (left < size) {
                int largestIndex;
                //判断孩子中较大的值的索引(要确保右孩子在size范围之内)
                if (arr[left] < arr[right] && right < size) {
                    largestIndex = right;
                } else {
                    largestIndex = left;
                }
                //比较父结点的值与孩子中较大的值,并确定最大值的索引
                if (arr[index] > arr[largestIndex]) {
                    largestIndex = index;
                }
                //如果父结点索引是最大值的索引,那已经是大根堆了,则退出循环
                if (index == largestIndex) {
                    break;
                }
                //父结点不是最大值,与孩子中较大的值交换
                swap(arr, largestIndex, index);
                //将索引指向孩子中较大的值的索引
                index = largestIndex;
                //重新计算交换之后的孩子的索引
                left = 2 * index + 1;
                right = 2 * index + 2;
            }
    
        }
        //交换数组中两个元素的值
        public static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

                                                                  友情提示:手机观看,可以左右滑动 

     

     

     

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 304,769
精华内容 121,907
关键字:

堆排序