堆排序---自己的总结与实现 堆排序的实现

1.堆排序是一种树型选择排序,它的特点是:在排序过程中,将R[1…n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在联系,在当前无序区中选择关键字最大(或最小)的记录。

2.堆排序只需要一个记录大小的辅助空间。实现堆排序需要解决两个问题:

一、如何将一个无序序列建成一个初始堆。

二、如何在输出堆顶元素后,调用剩余元素使之成为一个新的堆。

3.所谓筛选就是将以结点i为根结点的子树调整为一个堆。筛选算法的前提是结点i的左右子树必须已是堆。

4.显然只有一个结点的树是堆。根据完全二叉树的性质可知,具有n个结点的完全二叉树第n/2个结点之后的结点均是叶子结点,因此这些结点为根的子树都已是堆,我们只需要将非叶子结点作为根的子树调用成堆即可。即筛选须从第n/2个元素开始,逐层向上倒退,直至根结点。

4.初始堆建立以后,就可以进行排序了。

5.堆是一种顺序表示的具有堆序性的完全二叉树。

堆的定义:  
n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):
 (1)ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)
堆排序---自己的总结与实现 堆排序的实现

 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

堆的这个性质使得可以迅速定位在一个序列之中的最小(大)的元素.

堆排序算法的过程如下:1)得到当前序列的最小(大)的元素2)把这个元素和最后一个元素进行交换,这样当前的最小(大)的元素就放在了序列的最后,而原先的最后一个元素放到了序列的最前面 3)的交换可能会破坏堆序列的性质(注意此时的序列是除去已经放在最后面的元素),因此需要对序列进行调整,使之满足于上面堆的性质.重复上面的过程,直到序列调整完毕为止.

自己实现如下:

#include "stdafx.h"

void sift(inta[],int i,int length)

{

int temp=a[i];

int j=2*i+1;

while(j<length)

{

if(j<length-1&&a[j]<a[j+1])

j++;

if(temp<a[j])

{

a[i]=a[j];

i=j;

j=2*i+1;

}

else

break;

}

a[i]=temp;

}

void HeapSort(inta[],int length)

{

int i;

int temp;

for(i=length/2-1;i>=0;i--)

sift(a,i,length);

for(i=length-1;i>0;i--)

{

temp=a[i];

a[i]=a[0];

a[0]=temp;

sift(a,0,i);

}

}

int _tmain(int argc,_TCHAR* argv[])

{

int i;

inta[]={777,555,4,4,4,3,3,445,555,33,66,22,566,88,55,44,66,33,55,2,7,9,0,-1,-99,4555,444,33,2,3,4,54,5,4,3,3,4,4,5,65,44,3,4};

int length=sizeof(a)/sizeof(int);

HeapSort(a,length);

for(i=0;i<length;i++)

printf("%dn",a[i]);

getchar();

return 0;

}

  

爱华网本文地址 » http://www.413yy.cn/a/25101014/235580.html

更多阅读

工作心得总结 怎么写自己的工作心得

工作心得总结——简介珍惜自己的工作。今天,在我身边,有数以万计、刚刚走出校园艰难择业的大学生,也有很多下岗的员工,而我很庆幸,拥有一个可以为之奋斗的企业,拥有一间窗明几净的办公室,拥有一份属于自己的工作。说句实话,我感到非常的幸运

家长育子心得交流----让孩子成为自己的主人 女主人与乞丐的心得

让孩子成为自己的主人 -----王惠东家长我是王惠东的家长。应该说,王惠东在班里不是表现特别突出的学生,学习上还不够优秀,也不是班内进步最快的学生,但是,我对她还是比较满意的,她思想纯正,心态比较稳定,学习状态也不错,对父母非常尊重,没有

能力培养 如何提高自己的管理能力? 创新能力培养与提高2

资料来源:网站网页 编辑制作:《长庚书库》【能力培养】如何提高自己的管理能力?一、目标志向能力1.经常订立长期、短期目标、并向它挑战 2.达成目标后,立刻向下一个目标挑战 3.预测将来趋势,努力达成目标 4.订定具体的计划以达成目标与方针

声明:《堆排序---自己的总结与实现 堆排序的实现》为网友轻度疯分享!如侵犯到您的合法权益请联系我们删除