堆排序

具体实现

GitHub版本库的堆排序。

算法实现

实现

该算法按照二叉树的原理。
完全二叉树:深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树

 原数组 52,85,6,3,57,27,77,37,96,52
        0   1 2 3 4  5  6  7  8  9
              52
            /   \
           /     \
          85      6
         / \     / \
        /   \   /   \
        3   57 27   77
       / \  /
      6  3 25
 实现堆的排序,在起始数组为0的情况下:
 1. 数组下标i的左子节点在位置  (2*i+1)
 2. 数组下标i的右节点在位置    (2*i+2)
 3. 数组下标i的父节点在位置    floor(i-1)/2

 最大堆
               96
             /    \
            /      \
           85      77
          / \      / \
         /   \    /   \
         57  52  37   27
        / \  /
       25 6  3

 最小堆
               3
             /    \
            /      \
           6       25
          / \      / \
         /   \    /   \
        27   37  52   57
       / \   /
      77 85 96

难点

  1. 数组元素个数为n,则从最后一个父元素(最后一个非叶子节点)开始访问,即$i = floor($n/2)-1
  2. 从根元素开始访问,再访问左节点,再到右结点,称为先序遍历。
  3. 最大的堆,完成排序之后,是从小到大的数组。因为建立最大堆,是最大的在堆顶,但是第二次循环之后,
  4. 最大的被置换到数组最后一个数组。
  5. 最小堆,完成排序的数组是从大到小的数组。

耗时分析

机器配置 ThinkPad T440s CPU i5-4300U Memory 8GB
maxheap num 1000 sort cost time is 0.011452198028564 s
minheap num 1000 sort cost time is 0.0060770511627197 s
maxheap num 10000 sort cost time is 0.092055082321167 s
minheap num 10000 sort cost time is 0.090849161148071 s
maxheap num 100000 sort cost time is 1.2427570819855 s
minheap num 100000 sort cost time is 1.1724309921265 s

算法分析

最坏时间复杂度 О(nlog n)
最优时间复杂度 О(nlog n)
平均时间复杂度 О(nlog n)
空间复杂度   О(n)

参考链接

  1. 堆排序
  2. 堆排序(Heap Sort)算法学习

Press One

https://press.one/p/address/v?s=a7a1bb3ec261cdfa79b42dd6913dc46ec4daf0d8a83ccdd98c989da18e6a602f4cfb34c72d64a8ad988220a5a0c19797db4cc9d03b59521ab6edd335efb781b00&h=886316c032f1585dbc856dad15c66831772d5fbedc4f3f1d3c06f6415c504583&a=7c94f3669c472f7057f10aa21a7159ea89ab4a28&f=P1&v=2

2017年终总结

关于工作

这一年,我完成了从被管理者到管理者的转变。之前是只需要做好自己的工作,现在需要管理整个团队,整个业务,整个部门。从整体的角度,去思考如何更好的发展以及成长。这是一个没有相关经验可以学习借鉴的阶段。带领整个研发团队是一个不小的挑战,只有靠自己慢慢摸索,一边学习,一边实践。不仅要完成内部研发人员的管理,还有对外的沟通,还有业务的正常运行以及个人技术管理的学习提升。如果以10分计,我认为能给到自己的只有7.5分。实际上与自己的理想的阶段,差距较大,有很大的进步空间。下一年的目标,会从下方面进行改进、学习、探索。

  1. 对人员的相关技术培训,关心团队的成长。
  2. 加强大家的沟通以及聚会,多和组员沟通。
  3. 新技术如何快速落地,更好服务业务。
  4. 新人如何快速融入团队。
  5. 如何打造自己的团队文化。

关于技术

这一年,学习了新的前端技术VueJS,完成了VueJS在新业务上落地以及相关实践。但整体过程来看,还有很多不完善的地方,还需要花费更多的时间去调整优化。在业务上也开始涉及到了App客户端的编程开发,开始正式切入服务器端编程的阶段。在App客户端这块,其实可以做优化的比较多。目前我觉得比较紧迫的是,优化h5页面开屏优化方案。这个问题一直并没有达到我们的预期,但一直没有时间去优化。整个前后端的计划,从下面几个方面改进优化。

  1. VueJS技术的培训,后续的维护更新优化。
  2. 整个业务技术栈从PHP5更新到PHP7。
  3. 对现有的项目优化,更好的适用于业务的发展。
  4. 完善前后端技术栈,对新新技术的定位以及改进优化。
  5. 持续完善并优化App后端技术以及促进VueJS的应用。

关于生活

今年刚好完成年初计划的还贷,相对来讲,生活压力也相对来讲小一些。自认为做得不好的地方,应该是家庭关系。实际是个人承担这块做得比较少,简单的来说,基本上,我的老婆承担了大部分家务以及十一的上下学接送,个人生活的照顾。感谢我的老婆,为这家庭付出了很多。这也是我个人欠缺的地方。因此我只有在工作上做得更好来回报家人的付出。世事难两全。想在工作、投资上有所收获的话,就可能需要放弃其他的东西。希望在明年这块有一些改进的机会。

关于投资

真正改变我的一件事是,有同事投资数字货币,获得一笔可观的回报。在认真研究区块链以及数字货币后,在2018年会计划投资一些有价值的数字货币。尽管投资这块,也是刚刚开始摸索学习,但数字货币、区块链在2018年会有一个爆发。后来看到了吴郎发起的不出局就出彩,经过一段时间的思考,重新调整计划目标,那就是实现财富自由。借用笑来的话,实现财富自由是一个没有终点的旅程。实现财富自由后,就再也不用为了生活必需品出售自己的时间,只需要把时间花费在自己的成长上面。这才是我想要过的生活。这也是我一直想要的人生。

关于个人成长

今年我29岁了。常言道,人在三十而立,我是一个平凡的人,但我对很多东西都不甘心。我父母的人生轨迹,在看我来,是辛苦一生到头来得到回报的很少,反而失去了家庭最重要的亲情。父母在外,这么多年,聚少离多,导致沟通起来会比较麻烦。每个人的意见都不统一,相处起来不是很和谐。一个家庭的统一和谐很重要。大家都为了同一个目标努力,这才是家庭的意义。在过去的这一年,大家终于达成了比较和谐一致的目标,这是一个好的开始。明年会不会越来越好呢?

始发于微信公众号:神秘极客