资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
堆排序堆排序堆排序是利用堆的性质进行的一种选择排序,下面先讨论一下堆。1.堆堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:Keyi=Key2i+1void HeapAdjust(int *a,int i,int size) /调整堆 int lchild=2*i; /i 的左孩子节点序号 int rchild=2*i+1; /i 的右孩子节点序号 int max=i; /临时变量 if(iamax)max=lchild; if(rchildamax)max=rchild;if(max!=i)swap(ai,amax);HeapAdjust(a,max,size); /避免调整之后以 max 为父节点的子树不是堆 void BuildHeap(int *a,int size) /建立堆 int i;for(i=size/2;i=1;i-) /非叶节点最大序号值为 size/2 HeapAdjust(a,i,size); void HeapSort(int *a,int size) /堆排序 int i;BuildHeap(a,size);for(i=size;i=1;i-)/cout0)int i;for(i=1;iai;HeapSort(a,size);for(i=1;i=size;i+)coutai“;coutendl;return 0;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号