《堆排序算法分析(c语言版)》由会员分享,可在线阅读,更多相关《堆排序算法分析(c语言版)(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;