堆排序

具体实现

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)算法学习

发表评论

电子邮件地址不会被公开。 必填项已用*标注