文档章节

排序-堆排序

F
 FAT_mt
发布于 02/23 19:44
字数 822
阅读 4
收藏 0

在说明堆排序的过程前得先了解什么是堆:

先看下图(来源于java数据结构和算法(第二版)):

堆是个完全二叉树,并且父节点总是大于(小于)它的孩子,因此根节点永远是最大或者最小的元素。

堆排序的方法是将根节点与最后元素进行交换,并将数组容量减1,交换后最后一个元素不断下沉直至找到合适的位置。以上图为例,交换过程如下:

1、将100与5交换

2、将5下沉到合适的位置选出次大的元素,5和90进行比较将90提到根节点位置,然后5和60进行交换,最后5和55进行交换;

3、将数组容量设为12,最后一个元素的下标为11;

4、重复1和2两个步骤直至剩下1个元素为止。

此例就是按照从小到大进行排序,可将该堆称为最大堆,相应的如果元素需按照从大到小进行排序就需要建立最小堆。

由于给定的排序序列一般是无序的,因此首先需将序列转换成堆。试想一下上面第二个步骤能够执行的条件是整个完全二叉树为堆,并且每个子树都为堆,

并且下沉到正确的位置后又是一个新的堆,那么我们可以构想将整个序列当作一个完全二叉树,然后从最后一个子树开始不断调用第二个算法步骤建立新堆。

对于上图而言就是从5号节点所在的子树开始调用下沉算法一直到根节点所在的整个树为止,这样一个堆就建成了。

实际上堆排序算法也是选择排序算法中的一种,因为它每次都从中选择一个最大或者最小的元素依次排列到合适的位置。

时间复杂度分析:

1、数据下沉的时间复杂度与树的高度有关,在每层中都要比较2次,因此时间复杂度为2(h-1),有n个元素的完全二叉树的最大高度h为log(n)+1;

2、每层子树的最大个数为,因此建堆的时间复杂度为,子树的总个数为(n-3)/2

3、对于上例而言,高度h=4,比较总次数为1*(2*3)+2*(2*2)+  3*2=20

4、建好堆后,排序的时间复杂度为

5、总的复杂度就是两者之和,有兴趣的将两个公式的和求出个最终结果,可以肯定的是该结果的复杂度是0(nlogn)级别的。

在具体实现时采用数组存储,大家可以直接看lucene中sorter类源码的heapsort方法。

 

© 著作权归作者所有

共有 人打赏支持
F

FAT_mt

粉丝 2
博文 47
码字总数 26924
作品 3
南京
高级程序员
私信 提问
MySQL:关于排序order by limit值不稳定的说明(1)

水平有限,有过有误请谅解和指正,仅仅作为抛砖引玉。谢谢! 源码版本:5.7.14 本文约定:PQ 就是 Priority Queue 及优先队列其核心是堆排序,文中代表一种算法。 一、问题抛出 数据如下: ...

gaopengtttt
2018/12/07
0
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
程序员必知的8大排序(java实现)

8种排序之间的关系:  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好...

小帅帅丶
2015/01/09
0
7
算法——堆排序

我们可以把任意优先队列编程一种排序方法。将所有元素插入一个查找最小元素的优先队列,然后再重复调用删除最小元素的操作来将他们按顺序删除。用无序数组实现的优先队列这么做相当于一次选择...

嘿胖丁
2018/03/05
3
0
【译】Swift算法俱乐部-堆排序

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下...

Andy_Ron
01/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何开发一款以太坊(安卓)钱包系列2 - 导入账号及账号管理

这是如何开发一款以太坊(安卓)钱包系列第2篇,如何导入账号。有时用户可能已经有一个账号,这篇文章接来介绍下,如何实现导入用户已经存在的账号。 导入账号预备知识 从用户需求上来讲,导...

Tiny熊
今天
2
0
intellJ IDEA搭建java+selenium自动化环境(maven,selenium,testng)

1.安装jdk1.8; 2.安装intellJ; 3.安装maven; 3.1 如果是单前用户,配置用户环境变量即可,如果是多用户,则需配置系统环境变量,变量名为MAVEN_HOME,赋值D:\Application\maven,往path中...

不最醉不龟归
今天
4
0
聊聊ShenandoahGC的Brooks Pointers

序 本文主要研究一下ShenandoahGC的Brooks Pointers Shenandoah Shenandoah面向low-pause-time的垃圾收集器,它的GC cycle主要有 Snapshot-at-the-beginning concurrent mark包括Init Mark(P......

go4it
昨天
4
0
Makefile通用编写规则

#简单实用的Makefile模板: objs := a.o b.o test:$(objs) gcc -o test $^ # .a.o.d .b.o.d dep_files := $(foreach f,$(objs),.$(f).d) dep_files := $(wildcard $(dep_files)) ifneq ($(d......

shzwork
昨天
3
0
《万历十五年》的读后感作文4000字

《万历十五年》的读后感作文4000字: 万历十五年,即1587年,距今已过去432年。在明朝276的历史中,这一年很平淡,并没有什么特别之处。黄仁宇的《万历十五年》一书,有别于其他的历史叙述方...

原创小博客
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部