【你问我答】什么是堆排序?

问题描述:

什么是堆排序?

回答有奖:

选取一位认真回答问题的牛友,赠送200牛币!
▶回答尽量有自己的思考,不要单纯的只是复制粘贴定理定义,或者他人blog哦~

你问我答问题汇总:点击进入
关注你问我答栏目:点击关注

你问我答 - 答问题,成大佬,拿牛币!
你问我答是牛客新栏目,每周1期几个面试中真实遇到的问题,
牛友在问题贴下留下自己的知识,经验与见解,
帮助更多牛友了解更多技术相关知识!

#悬赏##Java##面试题目#
全部评论
先将无序数组按从前到后的顺序构建成一个堆,然后从最后一个数也就是堆的底部开始和子叶节点相比,假如比他大就置换,假如比他小就保持不变,并将这个子叶再以此类推和他上面的节点相比较,然后置换,最后和堆顶置换完毕后,就形成了大顶堆,然后把堆顶和最后一个堆底置换,,然后重新调整堆的结构使其满足大堆顶,然后再重复上面的步骤,反复进行使得最后形成有序的序列
点赞 回复
分享
发布于 2020-05-26 15:20
堆排序可以分为两个阶段。在堆的构造阶段,我们将原始数组重新组织安排进一个堆中;然后在下沉排序阶段,我们从堆中按顺序取出所有元素并得到排序结果。 1.堆的构造,一个有效的方法是从右到左使用sink()下沉函数构造子堆。数组的每个位置都有一个子堆的根节点,sink()对于这些子堆也适用,如果一个节点的两个子节点都已经是堆了,那么在该节点上调用sink()方法可以把他们合并成一个堆。我们可以跳过大小为1的子堆,因为大小为1的不需要sink()也就是下沉操作,有关下沉和上浮操作可以参考我写的优先队列那篇。 2.堆的排序,我们通过第一步操作构造了一个堆,在这个堆中,根节点永远是最大值的节点,所以我们把根节点的值与数组最后的值进行交换,在使用sink()下沉来维护堆的结构即可。
点赞 回复
分享
发布于 2020-05-26 15:41
秋招专场
校招火热招聘中
官网直投
堆排序是排序算法中内排序的一种,属于选择排序的一种,但是我觉得相比简单选择排序,从时间复杂度上来看,性能优。 时间复杂度(平均)是O(nlog2n) 时间复杂度(最坏)是O(nlog2n) 时间复杂度(最好)是O(nlog2n) 空间复杂度是O(1) 是个不稳定的排序算法。 基本思想: 1.首先将待排序的数组构造成一个大根堆,此时,整个数组的最大值就是堆结构的顶端 2.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1 3.将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组
点赞 回复
分享
发布于 2020-06-01 16:07

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务