改进的堆排序算法及其复杂度分析

《改进的堆排序算法及其复杂度分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、改进的堆排序算法及其复杂度分析张玉林1.推排序算法简介排序(Sorting)是计算机程序设计屮的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列重新排列成一个按关键字有序的序列。假设含n个记录的序列为｛Rl,R2,…，Rn｝(l)其相应的关键字序列为｛KI,K2,Kn｝,需确定1,2,n的一•种排序Pl,P2,Pn,使其相应关键字满足如下的非递减(或非递增)的关系KP1

2、次关键字，其至是若干数据项的组合。排序算法有：插入排序，合并排序，冒泡排序，选择排序，希尔排序，堆排序，快速排序，计数排序，基数排序等，各个算法的时间和空间复杂度也不同。而对n个关键字KI,K2,Kn进行堆排序的算法是威洛姆斯(WilliomsJ)在1964年提出的。堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占一个存储空间。原始的推排序算法只有n*log(n)的时间复杂度，其思想是利用堆这种数据结构，堆可以看成一个完全二叉树，所以在排序中比较的次数可以做到很少。加上其是原地排序，不需要中请额外的空间，效率也不错。定义n个元素的序列｛KI,K2,…，Kn｝当且仅当满足

3、下列关系时，称之为堆:KiK2i+l,其中i=l,2,对深度为h的堆，筛选算法中进行的关键字比较次数至多为2(h-l)次，则在建立含n个元素、深度为h的堆时，总共进行的关键字比较次数不超过4n。而n个结点的完全二义树的深度为[log2n]+l，贝U调整建新堆时调用Heapadjust过程次，总共进行的比较次数为t(n)=工[log2/]=2(12+22?+…+/?(“—2"))=2nh—2h+2+4/=2由此，在最坏的情况下，堆排序的时间复杂度为O(nlog2n)+0(〃)理论上已经证明任何一种比较排序算法在最坏的情况下所需做的键

4、比较次数至少是[log277!]=Jag2xdx=nlog2n-(n-1)log2e故堆排序算法的任何改进已不可能降低数量级，而只能设法降低复杂度因子。因此，对算法的改进应从降低t(n)开始。1.推排序改进思想及程序从堆的特性可以看出，在KI,K2,…，Kn是基本有序时，尾结点在从堆底逆序上升至堆顶后往往又被筛回到底层附近，而每下筛一层需进行2次键比较，这使得重新建堆的算法往往运行在最坏情况下。为了减少重新建堆过程中的键比较次数，设计先从根开始，每次只通过一次键比较使最大的子结点上升一层，在进行至第d次Z后，通过将尾结点键值和当前结点的父结点键值作比较，决定尾结点是上升还是下

5、筛。如果仍需下筛，则再通过d次键比较使当前结点下降d层，然后再判定尾结点是要上升述是下筛。这样一直做下去，可知最坏情况是降至底层后再上升d层，所以每次重新建堆至多作(h+[h/d]+d)次键比较。设KI,K2,…，Kn存于数组k[l]至k[n]中，则改进后的算法可描述为：建立初始堆buildheap(){for(i=n/2;i>=1；i—)shift(i,n);}/3buildheap3/shift(inti,intn)/3将k[i]〜k[n]整理成堆3/{x=k[i];j=23i;while(j<=n)n&&k[j]vk[j+l])++j;if(x>=k[j])break;k

6、[i]=k[j];i=j;j=23i;}k[i]=x;}/3shift3重新建堆rebuild(intx;intn;intdeep){i=1;j=23i;d=0;while(j<=n){d=d+1;if(j=k[j])break;}k[i]=k[j];i=j;j=23i;}while(i>1&&x>k[n/2])[log2/?!]«Jlog2xdx=nlog2n_(n-1)og2e{k[i]=k[n/2];i=n/2;}k[i]=x;}/3rebuild3/在堆深hW[log2n]时(此时堆中的元

7、素一般说来已基本冇序),重新建堆实际上变成先通过h次比较降至堆底，然后再适当上升将尾结点放在正确的位置。heapsort(){buildheap;for(j=n;j>=2;j-){x=k[j];k[j]=k[l];rebuild(x,j-1,[log2n])}}1.算法的复杂度分析堆排序算法因其比较和所需额外空间少而被广泛地采用。最坏的情况卜•有+1"T心)=X([1昭2j]+[log?/]/d+d)=——^[log2i]+d(n-1)i=2dj=2=空1(7?/?-2/,+l+2)+d(〃