异想天开

What's the true meaning of light, Could you tell me why

堆排序

日期:2015-03-27 21:20:14
  
最后更新日期:2015-03-27 21:22:27
【技术】
堆排序,稳定的O(n)的排序算法。堆排序分两个步骤,建堆和筛选。查看之前的博客时,发现了另外一个种建堆的方法。假设初始序列为: 49 38 65 97 76 13 27 49'。
建堆方法一:
从第floor(n/2)个元素开始筛选下来,接着floor(n/2)-1,直到第一个元素。为什么从floor(n/2)个节点开始筛选?因为第floor(n/2)是最后一个有子节点的节点。筛完floor(n/2)个节点那么就是一个堆了。
之前博客叙述:排序方法 建堆方法二:
利用迭代的方法。从堆的定义来看:
1.当只有root节点时,是一个堆。
2.把前面两个元素看成一棵二叉树时,第2个元素是新增的节点,那么只需要将其往上面冒泡(根据定义的排序规则),直到不能继续上冒的位置即可,从而前两个元素是一个堆了。
3.将前面3个元素看成二叉树,将第3个元素往上冒,即重复第2步的操作。
这样直到最后一个元素操作完后,感觉可以证明这是一个堆。
比较两种建堆的方法,第一种建堆的方法和我们即将用到的筛选的方法是一样的,若采用第一种建堆方法,只需要写一个筛选方法,即可实现堆排序。