文档章节

浅谈堆排序

无名氏的程序员
 无名氏的程序员
发布于 07/23 10:21
字数 709
阅读 9
收藏 0

一:定义

堆排序(英语:Heapsort)是指利用这种数据结构所设计的一种排序算法。堆排序是一种树形选择排序,在排序过程中可以把元素看成是一颗完全二叉树,每个节点都大(小)于它的两个子节点,当每个节点都大于等于它的两个子节点时,就称为大顶堆,也叫堆有序; 当每个节点都小于等于它的两个子节点时,就称为小顶堆

下面是我们要保存在数组中的堆的形式

二:堆排序算法

1.将长度为n的待排序的数组进行堆有序化构造成一个大顶堆

2.将根节点与尾节点交换并输出此时的尾节点

3.将剩余的n -1个节点重新进行堆有序化

4.重复步骤2,步骤3直至构造成一个有序序列

三:如何构造堆(大顶堆)

例:{5, 2, 6, 0, 3, 9, 1, 7, 4, 8}

第一次找到[n/2]处,进行构造:
我们比较父节点,左右孩子结点的大小,将最大的作为堆顶

 

第二次,我们对上次找到位置-1即可,找到结点0,对其左右孩子比较,构造这三个结点的最大堆

 

第三次,我们找到结点6,要对其进行构造,结果如下

第四次(重点),我们不止要构造双亲和左右孩子,我们还要比较其孩子结点为根的堆是否正确,不然我们需要进行调整

 

我们发现将8,7,2三个结点变为了最大堆,但是其中2,3子树不再是一个最大堆,我们需要对其修改

第五次:选取结点9进行构造   

发现以结点5为根的子树不是最大堆,我们需要进行调整

       

     完成构建:

 

四:堆排序(堆存储在数组中)

第一步:将最大值和最后的一个元素交换

第二步:将剩余的结点再次进行堆构造

第三步:参照第一步

按照上面循环,最终结果为

五:性能分析

运行时间主要消耗在构造堆和重建堆时的反复筛选上。
构造堆的时间复杂度为O(n)
重建堆时时间复杂度为O(nlogn)。
所以总体就是O(nlogn)。
不适合排序序列个数较少的情况

© 著作权归作者所有

无名氏的程序员
粉丝 0
博文 30
码字总数 29881
作品 0
广州
私信 提问
目录帖:​​​​​​​浅谈算法和数据结构

浅谈算法和数据结构: 一 栈和队列 浅谈算法和数据结构: 二 基本排序算法 浅谈算法和数据结构: 三 合并排序 浅谈算法和数据结构: 四 快速排序 浅谈算法和数据结构: 五 优先级队列与堆排序 浅谈...

安小乐
2018/09/04
60
0
mysql 在orderby和limit混合使用时重复数据问题

# 问题背景 select * from table_1 order by field_1,field_2 limit 0,10;select * from table_1 order by field_1,field_2 limit 10,10; 这样两条分页sql在查询数据时有两条数据既出现在第一......

小孑
2018/08/07
0
0
《浅谈JavaScript系列》系列技术文章整理收藏

《浅谈JavaScript系列》系列技术文章整理收藏 1浅谈JavaScript中面向对象技术的模拟 2浅谈javascript函数劫持[转自xfocus]第1/3页 3浅谈javascript 面向对象编程 4老鱼 浅谈javascript面向对...

开元中国2015
2015/07/27
1K
0
游戏开发与程序设计知识总结03——算法

更新日志 每此对思维导图有改动或者在github中有了对应的实现,则增加一条更新日志。 2017.9.2: 确定更新为系列文章并持续维护 前言 这是游戏开发与程序设计知识总结系列文章的第三篇算法,...

kashiwa
2017/09/02
0
0
细说JavaScript数据类型及转换

细说JavaScript数据类型及转换 JavaScript数据类型 1.Boolean(布尔) 布尔:(值类型)var b1=true;//布尔类型 2.Number(数字) 数值:(值类型)var n1=3.1415926;//数值类型 n1.toFixed...

开元中国2015
2015/07/13
95
1

没有更多内容

加载失败,请刷新页面

加载更多

只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
昨天
61
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
昨天
29
0
全世界到底有多少软件开发人员?

埃文斯数据公司(Evans Data Corporation) 2019 最新的统计数据(原文)显示,2018 年全球共有 2300 万软件开发人员,预计到 2019 年底这个数字将达到 2640万,到 2023 年达到 2770万。 而来自...

红薯
昨天
66
0
Go 语言基础—— 通道(channel)

通过通信来共享内存(Java是通过共享内存来通信的) 定义 func service() string {time.Sleep(time.Millisecond * 50)return "Done"}func AsyncService() chan string {retCh := mak......

刘一草
昨天
59
0
Apache Flink 零基础入门(一):基础概念解析

Apache Flink 的定义、架构及原理 Apache Flink 是一个分布式大数据处理引擎,可对有限数据流和无限数据流进行有状态或无状态的计算,能够部署在各种集群环境,对各种规模大小的数据进行快速...

Vincent-Duan
昨天
62
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部