最新消息:点击查看大S的省钱秘笈

堆排序(Heap Sort) 算法实现 C语言版

编程相关 Slyar 323浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

n个关键字序列Kl,K2,…,Kn称为堆(Heap),当且仅当该序列满足如下性质(简称为堆性质):

ki≤K2i且ki≤K2i+1 或  Ki≥K2i且ki≥K2i+1(1≤i≤ n)

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 (即如果按照线性存储该树,可得到一个不下降序列或不上升序列)

SLYAR整理了一下算法,用C语言实现,带注释。

转载请注明:Slyar Home » 堆排序(Heap Sort) 算法实现 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (18)

  1. 这个代码有问题吧,第一次循环时,child并没有初始化啊
    12343年前 (2013-07-24)回复
  2. 哥,你这个程序有问题哦。。。大的思想没问题,在索引上没处理好
    hoot4年前 (2012-09-08)回复
    • 怎么说呢?
      Slyar4年前 (2012-09-08)回复
      • 运行下就知道了,数组越界了。。n >= 2 * i ;child+1的时候就越界了
        hoot4年前 (2012-09-08)回复
  3. @Yao 没错...好吧,我把代码统一了...
    Slyar7年前 (2009-11-18)回复
  4. @Slyar 不好意思,昨天灌了下水;-) “ki≤K2i且ki≤K2i+1 或 Ki≥K2i且ki≥K2i+1(1≤i≤ n)” 这里的i是从1开始计。 但i在代码中从0开始计,这样 “child=2*i;”似乎应该改为child=2*i+1,∵2*i并非i左孩子(可以画出一棵树进行验证),而“for (i=n/2;i>=0;i--) /* 建立初始堆 */”中改为i=n/2-1。 不知道我理解是否有误?
    Yao7年前 (2009-11-18)回复
  5. 已阅。
    Yao7年前 (2009-11-17)回复
  6. @, 每次删除堆顶元素后难道不需要重新维护堆么?
    Slyar8年前 (2009-04-24)回复
  7. 楼上的代码有问题。。。。。。 堆排每次应该对于堆顶元素进行删除。。。。而不是重新建立一个堆。。。
    匿名8年前 (2009-04-24)回复
  8. @闲人, a[0]
    Slyar8年前 (2009-02-11)回复
  9. 你这是从a[0]还是从a[1]开始的啊
    闲人8年前 (2009-02-11)回复
  10. 呵呵,你的博客怎么不管大多少打空格都会省略空格?? 改进会好些啊!
    And You8年前 (2008-10-25)回复
    • 呃。。。我空间不大,为了节省数据库。。。囧。。。
      Slyar8年前 (2008-10-25)回复
  11. 同上,的确,你的代码能不能打空格呢?? 期待啊! 我一般不用堆排,一是有些慢,二是太麻烦。 我用快速排序或选择排序。 虽然选择排序和堆排一样慢都是O(n^2)的。 选择排序: #include"stdio.h" #include"conio.h" void selectSort(int a[],int count) { int i,j,min,temp; for(i=0;i<count-1;i++) { min=i; for(j=i+1;j<count;j++) if(a[j]<a[min]) min=j; if(min!=i) { temp=a[min]; a[min]=a[i]; a[i]=temp; } } } void main() { int a[7]={8,9,3,5,1,6,4}; int i; selectSort(a,7); clrscr(); for(i=0;i<7;i++) printf("%4d",a[i]); }
    And You8年前 (2008-10-25)回复
    • 汗。。。有些题你不用堆排是会超时的。。。
      Slyar8年前 (2008-10-25)回复
    • 哦,那就用快排!~~ 好像快排更复杂!
      And You8年前 (2008-10-25)回复
    • 堆排是O(nlogn)。。。
      felix0218年前 (2008-10-25)回复
  12. 没有缩进的代码看起来太痛苦。
    felix0218年前 (2008-10-18)回复