【十大经典排序算法】堆排序及其JAVA代码实现

  • 2
  • 1,451 views
  • A+
所属分类:JAVA 原创 开发&源码

之前写了十大经典排序算法的桶排序,现在,我们再来看看堆排序以及其Java代码的实现...

原理

既然是堆排序,肯定是涉及到数据结果中的堆,堆排序是利用堆来实现排序;其排序既用到完全二叉树的特性,又用到了堆父节点大于子节点的特性。

先将所有数据当成一颗完全二叉树,然后使得所有的父节点都大于子节点(满足堆的特性),然后将完全二叉树最后一个叶子节点与根节点交换(此时最后一个节点属于有序的,我们暂称其存在于有序区,而其他节点存在无序区),此时数据不再满足堆的特性,因此再继续调整,让所有父节点大于子节点,再替换最后一个叶子节点与根节点(此时有序区存在两个节点),依此循环,直至所有节点都加入有序区,则排序完成。

示意图

发现自己上面表达得有点太啰嗦了,却又不知道怎么去更改,暂且自认为已经表达了意思吧。

我们再来看看其示意图(画图太麻烦,只好百度之,注:下图来自网络)

【十大经典排序算法】堆排序及其JAVA代码实现

堆排序

java代码

堆排序算法java实现代码如下:

复杂度

由上面可以看出,堆排序时间复杂度为T(n) = O(nlogn)

原文博客:IT老五(【十大经典排序算法】堆排序及其JAVA代码实现)

【十大经典排序算法】堆排序及其JAVA代码实现
IT老五(it-lao5):关注公众号,一起源创,一起学习!
weinxin
我的微信公众号
我的微信公众号扫一扫
Liu, Thinkin

发表评论

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

目前评论:2   其中:访客  2   博主  0

    • avatar 千叶 8

      good

      • avatar 匿名 8

        ☺☝☝☝