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

2008年10月18日 13:52 . 分类 编程相关 . 被踩 947 次 .

文章作者：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语言实现，带注释。

void sift(int a[],int i,int n) /* i为根节点,n为节点总数 */
{
    int child,tmp;
    for (tmp=a[i];n>2*i;i=child)
    {
        child=2*i; /* i的左孩子为2*i,右孩子为2*i+1 */
        if (child!=n-1&&a[child+1]>a[child]) /* 让child指向孩子中较大的一个 */
        {
            child++;
        }
        if (tmp<a[child]) /* 如果孩子节点大 */
        {
            a[i]=a[child]; /* 交换孩子节点和根节点 */
        }
        else break;
    }
    a[i]=tmp; /* 将根放在合适位置 */
}

void heapsort(int a[],int n) /* 对a[1...n]进行排序 */
{
    int i,tmp;
    for (i=n/2;i>=0;i--) /* 建立初始堆 */
    {
        sift(a,i,n);
    }
    for (i=n-1;i>0;i--) /* 进行n-1趟排序 */
    {
        tmp=a[0]; /* 交换堆顶元素和最后一个元素 */
        a[0]=a[i];
        a[i]=tmp;
        sift(a,0,i); /* 将a[1..n-1]重建为堆 */
    }
}

您可能还对以下内容感兴趣

Tags: ,

收藏、分享这篇文章! 用 RSS feed 订阅本博客 什么是订阅？ Trackback

评论

7 条评论 关于 “堆排序(Heap Sort) 算法实现 C语言版”

  1. 由 felix021 发表于 2008年10月18日 23:07

    没有缩进的代码看起来太痛苦。

  2. 由 And You 发表于 2008年10月25日 10:41

    同上，的确，你的代码能不能打空格呢？？
    期待啊！

    我一般不用堆排，一是有些慢，二是太麻烦。
    我用快速排序或选择排序。
    虽然选择排序和堆排一样慢都是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]);
    }

    Slyar 回复 于 10月 25th, 2008 10:44:

    汗。。。有些题你不用堆排是会超时的。。。

    And You 回复 于 10月 25th, 2008 10:48:

    哦，那就用快排！~~
    好像快排更复杂！

    felix021 回复 于 10月 25th, 2008 18:25:

    堆排是O(nlogn)。。。

  3. 由 And You 发表于 2008年10月25日 10:42

    呵呵，你的博客怎么不管大多少打空格都会省略空格？？
    改进会好些啊！

    Slyar 回复 于 10月 25th, 2008 10:43:

    呃。。。我空间不大，为了节省数据库。。。囧。。。

发表您的评论[审核后显示]




关闭
E-mail It