随笔 - 70  文章 - 160  trackbacks - 0

公告:
知识共享许可协议
本博客采用知识共享署名 2.5 中国大陆许可协议进行许可。本博客版权归作者所有,欢迎转载,但未经作者同意不得随机删除文章任何内容,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。 具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言。

常用链接

留言簿(8)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 176451
  • 排名 - 147

最新评论

阅读排行榜

评论排行榜

建议先看看前言:http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html

首先介绍几个概念:

卫星数据:一个带排序的的数通常是有一个称为记录的数据集组成的,每一个记录有一个关键字key,记录的其他数据称为卫星数据。

原地排序:在排序输入数组时,只有常数个元素被存放到数组以外的空间中去。

 

在第二章介绍了两种排序:插入排序和合并排序,接下来两章要介绍的是推排序和快速排序,这四个排序都属于比较排序(comparison sort)。

 

我以前总结过堆排序,并具体实现了堆排序,代码中给出了详细的注释,所以在这里就不重复发了,大家可以去看看,个人觉得总结的还是比较给力的:

http://www.wutianqi.com/?p=1820

这里再补充几点:

1.区别length[A]和heap-sort[A]。(P73)(这个在下一篇的优先级队列中将会具体区别)

2.总体上看堆排序由三个函数组成:①.MAX-HEAPIFY ②.BUILD-MAX-HEAP ③.HEAP-SORT

 

另外,在这里给大家补充一点个人经验,有时理论难以理解,代码难以理解,这个时候,就要靠秘诀了:拿起手中的笔和纸,自己给出一组输入,按照书上的代码,自己去模拟这组输入的执行过程。(这个过程人人都知道,但并不是人人都去做了!学算法,就要自己去模拟,去画图,去推!怎么样容易理解就怎么去做!)

所以这也是我喜欢《算法导论》的原因,接下来,就要强烈推荐大家看《算法导论》上非常非常给力的堆排序实现图了—图6-4。

 

 

总结:本章最基础也是最重要的就是理解堆这种结构!

堆是什么?来看看《算法导论》上的图6-1:

dui

图(a)是一个最大堆,图(b)是最大堆的数组表示。可以看到堆的数组并不是已排序好的。

让我们来回忆下最大堆的定义(P74):

在最大堆中,最大堆特性是指除了根以外的每个结点i,有A[PARENT(i)] >= A[i]。这样,堆的最大元素就存放在根结点中。

对,堆排序就是利用的这个特性—“堆的最大元素就存放在根结点中”

每次堆化,这样就找到了当前堆的最大元素。

所以说,理解了其本质特征,堆排序其实很简单的。

至于堆排序的具体应用,在后面的最短路算法—Dijkstra中,会用到由堆来优化普通的Dijkstra算法。

下一篇将实现最大优先级队列。

Tanky Woo 标签:
posted on 2011-04-15 12:43 Tanky Woo 阅读(1302) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理