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

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

/* i为根节点,n为节点总数 */
void sift(int a[], int i, int n)
{
    int child, tmp;
    for (tmp = a[i]; n >= 2 * i; i = child)
    {
        /* i的左孩子为2*i,右孩子为2*i+1 */
        child = 2 * i;

        /* 让child指向孩子中较大的一个 */
        if (child != n && a[child + 1] > a[child])
        {
            child++;
        }

        /* 如果孩子节点大 */
        if (tmp < a[child])
        {
            /* 交换孩子节点和根节点 */
            a[i] = a[child];
        }
        else break;
    }
    /* 将根放在合适位置 */
    a[i] = tmp;
}

/* 对a[1...n]进行排序 */
void heapsort(int a[], int n)
{
    int i, tmp;

    /* 将a[1...n]建成大根堆 */
    for (i = n / 2; i >= 1; i--)
    {
        sift(a, i, n);
    }

    /* 进行n-1趟排序 */
    for (i = n; i >= 2; i--)
    {
        /* 交换堆顶元素和最后一个元素 */
        tmp = a[1];
        a[1] = a[i];
        a[i] = tmp;

        /* 将a[1...i-1]重建为堆 */
        sift(a, 1, i-1);
    }
}

/* i为根节点,n为节点总数 */

void sift(int a[], int i, int n)

{

int child, tmp;

for (tmp = a[i]; n >= 2 * i; i = child)

{

/* i的左孩子为2*i,右孩子为2*i+1 */

child = 2 * i;

/* 让child指向孩子中较大的一个 */

if (child != n && a[child + 1] > a[child])

{

child++;

}

/* 如果孩子节点大 */

if (tmp < a[child])

{

/* 交换孩子节点和根节点 */

a[i] = a[child];

}

else break;

}

/* 将根放在合适位置 */

a[i] = tmp;

}

/* 对a[1...n]进行排序 */

void heapsort(int a[], int n)

{

int i, tmp;

/* 将a[1...n]建成大根堆 */

for (i = n / 2; i >= 1; i--)

{

sift(a, i, n);

}

/* 进行n-1趟排序 */

for (i = n; i >= 2; i--)

{

/* 交换堆顶元素和最后一个元素 */

tmp = a[1];

a[1] = a[i];

a[i] = tmp;

/* 将a[1...i-1]重建为堆 */

sift(a, 1, i-1);

}

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

这个代码有问题吧，第一次循环时，child并没有初始化啊

123413年前（2013-07-24）回复

哥，你这个程序有问题哦。。。大的思想没问题，在索引上没处理好

hoot14年前（2012-09-08）回复

怎么说呢？
Slyar14年前（2012-09-08）回复
- 运行下就知道了，数组越界了。。n >= 2 * i ；child+1的时候就越界了
  hoot14年前（2012-09-08）回复

@Yao 没错...好吧，我把代码统一了...

Slyar17年前（2009-11-18）回复

@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。不知道我理解是否有误？

Yao17年前（2009-11-18）回复

已阅。

Yao17年前（2009-11-17）回复

@, 每次删除堆顶元素后难道不需要重新维护堆么？

Slyar18年前（2009-04-24）回复

楼上的代码有问题。。。。。。堆排每次应该对于堆顶元素进行删除。。。。而不是重新建立一个堆。。。

匿名18年前（2009-04-24）回复

@闲人, a[0]

Slyar18年前（2009-02-11）回复

你这是从a[0]还是从a[1]开始的啊

闲人18年前（2009-02-11）回复

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

And You18年前（2008-10-25）回复

呃。。。我空间不大，为了节省数据库。。。囧。。。
Slyar18年前（2008-10-25）回复

同上，的确，你的代码能不能打空格呢？？期待啊！我一般不用堆排，一是有些慢，二是太麻烦。我用快速排序或选择排序。虽然选择排序和堆排一样慢都是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]); }

汗。。。有些题你不用堆排是会超时的。。。
Slyar18年前（2008-10-25）回复
哦，那就用快排！~~ 好像快排更复杂！
And You18年前（2008-10-25）回复
堆排是O(nlogn)。。。
felix02118年前（2008-10-25）回复

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

felix02118年前（2008-10-18）回复

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

与本文相关的文章

Hi，您需要填写昵称和邮箱！

网友最新评论 (18)