堆排序

面试官:写一个堆排吧 我心想:幸好昨天刚看

堆排是基于堆的一种排序算法,对于堆的了解,请看可以管理时间的二叉堆(如果对堆的插入和删除不清楚,强烈建议先看堆),今天我们聊聊堆排的思想,复杂度以及稳定性

堆排思想

过了几天后,谦子高兴地跑到老师跟前

老师,你的那个方法太好了,现在做事非常有次序克

谦子心想:上次去溪边游玩不是已经出过这个题吗,当时学会了冒泡排序,这次肯定不是那么简单,肯定和前几天的堆有关系

这个应该用到堆

谦子画了一个图解释道

初始的时候,无序数组逻辑上可以看成一颗完全二叉树

每个叶子节点可以视为一个大小为一的堆,我们可以自底向上从非叶子节点开始每层从右至左给每个节点都调用下沉(sink)方法,这样以当前节点为根节点的树就变为堆了

然后给左边的节点4执行下沉(sink)操作(同一层从右向左)

最后根节点执行下沉(sink)操作

又要写代码,谦子心想,虽说心中这样想,但还是要写的,思考了一会,只见谦子写下了如下代码

这里的 heapSize/2 就是第一个非叶子节点的下标

过了一会谦子又写出了删除最小值的代码

恩恩,不错,那顺便写一下排序的代码吧

前两个都写出来了,剩下的排序就很简单了,按照之前的思路,先建立一个小根堆,然后不断地删除堆顶最小元素,删除N-1次就OK了

只需删除N-1次,剩下的那个自然是最大的,所以我循环N-1次

恩恩,很好,这个排序就是今天要给你说的另一个排序:堆排序

谦子暗自惊叹老师的功力,不知不觉又学到了一个排序方法

时间复杂度

那你分析一下这个堆排序的时间复杂度吧

看到数学头疼的可以直接跳过看结论

谦子还没缓过神,又来了一个最让他头疼的时间复杂度

这个。。。,弟子不才,还请老师指点

这个排序时间复杂度稍微有点难,但只要你静下心来一步一步算,其实也不难

克拿出了笔和纸

你想一下堆排的整个过程,第一步建堆,第二步执行N-1次deleteMin()方法,最后取两者复杂度较高的就行了

建堆时间复杂度

建堆的时候时间消耗在下沉操作上,而下沉操作最多下沉到底,显然,高度为h的节点下沉代价为O(h)

堆中所有元素下沉代价之和就是建堆的代价(时间复杂度)

叶子节点高度为0,下沉代价为0

把堆中不同高度中的所有节点相加起来就是全部的节点

所以问题变为:

① 高度最高多高(高度上界)

② 高度h有多少节点

这里你记住两个结论

这里我们把不同高度的每个节点执行sink所需要的代价累加起来

感觉复杂,你最终记住建堆复杂度为O(n)就行了

N-1次删除复杂度

接下来就是N-1次的删除了

n-1次调用deleteMin

deleteMin中包含 swap操作和 sink操作

swap操作代价为常数,sink操作代价为lgn,swap操作相对于sink操作可以忽略不计

则相当于进行了n-1次sink操作

则一共花费的代价为:(n-1)*lgn ~ nlgn

故时间复杂度为O(nlgn)

两个步骤相加的复杂度为:O(n)+O(nlgn),O(nlgn)复杂度高于O(n),所以堆排序的时间复杂度为O(nlgn)

哦,这样啊,懂了

那你说说堆排序是不是稳定的

不是稳定的,就拿5,7,13,5,这个序列来说吧,我用大根堆的结构排序,排序前后两个5的位置会发生变化

谦子说着说着画了一个图

初始状态的5的先后顺序和排完序的顺序明显不一样了(黄色5跑到红色5左边去了),所以这个排序不是稳定的

原文发布于微信公众号 - 趣谈编程(gh_51e791ad9174)

原文发表时间:2017-12-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏于晓飞的专栏

DualPivotQuickSort 双轴快速排序 源码 笔记

这个算法是Arrays.java中给基本类型的数据排序使用的具体实现。它针对每种基本类型都做了实现,实现的方式有稍微的差异,但是思路都是相同的,所以这里只挑了i...

11020
来自专栏ACM算法日常

How many integers can you find(容斥原理) - HDU 1796

看这题之前先复习一下容斥原理,不然肯定看不懂,呃,如果第一次接触容斥原理的题,可能弄懂了容斥原理你还是看不懂代码,是的,等会你就知道了。

9620
来自专栏desperate633

LeetCode 215. Kth Largest Element in an Array分析

显然最简单的思想就是排序,然后取出倒数第k个元素就可以了,我们可以直接调用内部的排序函数。

8720
来自专栏cmazxiaoma的架构师之路

Java小白必须会的一道面试算法题

2.4K30
来自专栏数据结构与算法

P1338 末日的传说

题目描述 只要是参加jsoi活动的同学一定都听说过Hanoi塔的传说:三根柱子上的金片每天被移动一次,当所有的金片都被移完之后,世界末日也就随之降临了。 在古老...

32990
来自专栏前端正义联盟

我来重新学习 javascript 的面向对象(part 5)

这是最后的最后了,我会顺便总结一下各种继承方式的学习和理解。(老板要求什么的,管他呢)

9710
来自专栏云霄雨霁

字符串排序----排序算法的选择

25900
来自专栏chenjx85的技术专栏

leetcode-561-Array Partition I

20170
来自专栏轮子工厂

八大排序算法稳定性分析,原来稳定性是这个意思...

2、在一趟选择中,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了;

27460
来自专栏java一日一条

面试中的 10 大排序算法总结

查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只...

22330

扫码关注云+社区

领取腾讯云代金券