Slyar Home

来自"Slyar Home"的最新文章，如果您不希望再收到此邮件，请退订；如果您需要更换其它邮箱接收邮件，请点击这里！

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

Sat, 18 Oct 2008 13:52:08 +0800

文章作者：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]重建为堆 */
}
}

返回顶部

熟能生巧:有感于大学第一次剪头发

Fri, 17 Oct 2008 20:19:58 +0800

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

周五，没课。一直在想博客今天发什么，但却没有素材。于是乎，聪明的SLYAR决定自己创造素材。。。

吃过晚饭，我和Jet跑到海2楼下剪头发，这是我上大学以来第一次剪头发，当然要评估一下这间理发店。理发店还算大，灯光效果也不错，卫生状况良好，咦？有奶粉！恩，还好，不是三号长颈鹿。。。

洗头的时间好长啊，洗来洗去。。。(后来才知道，原来洗发吹头是要10块钱的)

(镜头转移)理发师的手随着剪刀。。。呃不对，是剪刀随着理发师的手上下飞舞，那动作快的，刷刷刷刷刷刷。。。眼花缭乱。此情此景，我不禁感慨，技艺真的是熟能生巧啊。。。想家里那边的理发店，一个星期来剪头发的估计也没有这里一天剪头发的多，这里的理发师日复一日地做着"上下飞舞"的动作，技艺岂不高哉？

当然了，技艺高不高我不知道，起码速度达到我的要求了，算账的时候发现要价20，一经询问才知道"单剪"10块，"洗吹"10块。。。我靠，不洗能剪么？哎，真是熟能生奸啊。。。

剪头发的事情先告一段落，我剪得很短，这样可以在很长一段时间不用管头发了。。。

再说说学校的Online Judge，超级不爽，哪有每个题目都这么写Input的：

1、有多组，每组一行，输入n,m( 0<10, 0<10) 输入0 0表示结束。

2、有多组输入，每组输入用空行分隔开，输入以EOF结束。

几乎所有的OJ都是给10个单独的数据，哪有这么偷懒只给1个输入文件里面一堆数据的。。。对这个OJ失去兴趣。。。

返回顶部

您可以直接回复此邮件与作者联系，该服务由Feedsky提供技术支持，祝您使用愉快