堆排序(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

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]重建为堆 */ } }