排序算法五:堆排序

马谦马谦马谦 2019年4月27日12:10:54 发表评论
文章最后编辑于:2020-3-14 21:51:24

一、堆排序原理

通过最大堆的性质可以知道:一个堆中最大的元素总是在堆顶的,即数组下标0的位置。基于这一点,我们可以每次都把堆中的最大值提取出来,放到当前数组的后面。然后重新构建最大堆,重复这个过程,以此来完成一个数组的排序。

例如,一个已知的最大堆为:

排序算法五:堆排序

把最大的元素16提取出来,放到最后。然后重新建堆,此时堆中最大的元素为15,更新后的堆为:

排序算法五:堆排序

再把15提取出来,重新建堆,得到:

排序算法五:堆排序

如此往复,直到最后堆中的元素只有一个,就完成了整个数组的排序。

二、代码实现

堆排序的关键点在于构造堆,如何构造堆可参考数据结构之堆。基于模板的最大堆化函数实现:

实现堆排序,堆排序的关键点在于从后往前排:

时间复杂度

堆排序的时间主要消耗再建堆上面,每次拿掉一个元素之后,都重新执行最大堆化

每次构造最大堆的时间复杂度为O(log(n)),因此堆排序的总时间复杂度为n(log(n)),n代表元素个数。

本文共执行66次查询,耗时0.494秒!
马谦马谦马谦

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: