您当前的位置: 首页 >  c语言

暂无认证

  • 14浏览

    0关注

    93840博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

堆排序(C语言实现)

发布时间:2022-09-26 12:10:34 ,浏览量:14

堆排序)
  • 概念
  • 算法实现
  • 后续
概念
  1. 堆排序要结合顺序存储的完全二叉树的特性进行学习。 对于完全二叉树而言:
  • 结点 i 的左孩子是 2i
  • 结点 i 的右孩子是 2i+1
  • 结点 i 的父节点是 i/2
  • 编号 <= n/2的结点都是分支结点
  1. n个关键字序列L[1…N]称为堆。 当且仅当 L(i) >=L(2i) 且 L(i)>=L(2i+1) 可以将该一维数组视为一棵完全二叉树,满足此条件的堆称之为大根堆。大根堆的最大元素存放在根节点,且其任一非根节点的值小于等于其双亲结点值。 小根堆反之。
  2. 堆排序的思路很简单:首先将存放在L[1…N]中的N个元素建成初始堆,由于堆本身的特点(以大根堆为例),堆顶元素就是最大值。输出堆顶元素后,通常将堆底元素送入堆顶,此时根节点已不满足大顶堆的性质,对被破坏,将堆顶元素向下调整使其继续保持大顶堆的性质,再输出堆顶元素。如此重复,直到堆中仅剩一个元素为止。
  3. 构建初始堆的方法:先对完全二叉树的最右下边的子树调整,使其成为堆(如果此节点的孩子有比他大的,则将最大的孩子和父节点调换),之后向前依次对各节点([N/2]-1~1)为根的子树进行筛选,看该节点是否大于其左右孩子的值,若不大于则交换,交换后可能会破坏下一级的堆,于是采用上述方法继续构建下一级的堆,直到以该节点为根的子树构成堆为止。反复利用上述调整堆的方法建堆,直到根节点。
算法实现
#include  #include  #include  void BuildMaxHeap(int a[],int size); void HeadAdjust(int a[],int k,int size); void HeapSort(int a[],int size); int main() { int k; int num[9]={NULL,8,7,4,6,5,1,2,3}; int sortsize=sizeof(num)/sizeof(num[0]); HeapSort(num,sortsize-1); for(k=1;k<sortsize;k++) printf("\n%d",num[k]); system("pause"); return 0; } void BuildMaxHeap(int a[],int size) { int i; for(i=size/2;i>0;i--) HeadAdjust(a,i,size); } void HeadAdjust(int a[],int k,int size) { int i,j; int temporary; temporary=a[k]; for(i=2*k;i<=size;i*=2) { if(i<size&&a[i]<a[i+1]) i++; if(temporary>=a[i])break; else{ a[k]=a[i]; k=i; } } a[k]=temporary; } void HeapSort(int a[],int size) { int i; int temporary; BuildMaxHeap(a,size); for(i=size;i>1;i--) { temporary=a[i]; a[i]=a[1]; a[1]=temporary; HeadAdjust(a,1,i-1); } } 

后续

欢迎关注公众号:物联网知识

关注
打赏
1655258400
查看更多评论
立即登录/注册

微信扫码登录

0.2771s