搜索

图解堆排序

gecimao 发表于 2019-04-23 11:05 | 查看: | 回复:

  (如果对堆的插入和删除不清楚,强烈建议先看堆),今天我们聊聊堆排的思想,复杂度以及稳定性

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

  如果将这个数组调整为小根堆,那么根据小根堆堆顶一直是最小元素的特性,我可以不断地取(删除)堆顶的元素,直到堆中只剩下一个元素,这样就可以得到一个递减的元素序列了

  我可以遍历数组中的每个元素,给一个空堆不断插入元素,直到插完所有元素,这样就可以构造一个堆了

  恩恩,这确实是一种方法,但更常见的是用下沉(sink)操作自底向上构造一个堆

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

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

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

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

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

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

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

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

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

  ●本文编号555,以后想阅读这篇文章直接输入555即可返回搜狐,查看更多

本文链接:http://baumseelen.com/duipaixu/304.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部