首页 > 编程相关 > 堆排序(Heap Sort) 算法实现 C语言版

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

2008年10月18日 13:52 Slyar 发表评论 阅读评论

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/* 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);
    }
}
分类: 编程相关 标签: ,
  1. 2009年11月18日12:34 | #1

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

  2. Yao
    2009年11月18日11:37 | #2

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

  3. Yao
    2009年11月17日18:59 | #3

    已阅。

  4. 2009年4月24日14:26 | #4

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

  5. 匿名
    2009年4月24日14:22 | #5

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

  6. 2009年2月11日17:00 | #6

    @闲人, a[0]

  7. 闲人
    2009年2月11日16:52 | #7

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

  8. 2008年10月25日10:42 | #8

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

    Slyar 回复:

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

  9. 2008年10月25日10:41 | #9

    同上,的确,你的代码能不能打空格呢??
    期待啊!

    我一般不用堆排,一是有些慢,二是太麻烦。
    我用快速排序或选择排序。
    虽然选择排序和堆排一样慢都是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 回复:

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

    And You 回复:

    哦,那就用快排!~~
    好像快排更复杂!

    felix021 回复:

    堆排是O(nlogn)。。。

  10. 2008年10月18日23:07 | #10

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

bnuep:0801010047