二次立体堆排序算法设计与分析

《二次立体堆排序算法设计与分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据第29卷第5期V01．29N0．5菏泽学院学报Joumal0fHe∞Univers畸2007年lO月0ct．2007文章编号：1673—21∞(2町7)∞一0∞l一∞二次立体堆排序算法设计与分析帅训波，周相广(中国石油勘探开发研究院廊坊分院地球物理与信息研究所．河北廊坊，呦)摘要：通过对立体堆排序算法的分析，从分段优化数据处理技术角度，提出了二次立体堆排序算法，给出了算法思想、算法描述和算法分析，论证了二次立体堆排序算法，随着排序数量增加，排序速度快于立体堆排序算法越显著。关键词：立体堆排序；二次立体堆排序；数据处理；分段中图分类号：TP3叭．6文献标识码：A引

2、言排序既是计算机算法设计的基本理论之一，也是计算机应用中的一项重要技术【It“。对于基于比较的一类排序算法，理论上已证明算法的时间复杂度下界为nlo醪¨“J。要提高基于比较方式的排序效率，不但要采用时间复杂度为D(nlo醪)的最佳排序算法，而且在排序过程中，也要设法采用优化数据处理技术，减小数据操作中的时问耗费[”。通过最佳排序算法与优化数据处理技术的结合，获取高效的排序算法效果。在对排序的研究过程中发现，立体堆排序(SHEAPS0砌1)算法具有较优的平均时间复杂度，减少了堆排序算法复杂性的常数因子【g】。本文应用数据优化处理技术，提出了二次立体堆排序(1SHEAPs0

3、RT)算法，即把数据个数为n的立体堆排序过程，划分为多个较小的立体堆排序过程，使数据操作在较小的存储空间范围内进行，避免了由于远距离存储空间的操作引起的时问耗费。由于数据得到分段排序优化处理，鸭HEAPsORT算法排序速度，随着排序数量增加，排序速度快于sHEAPsoRT算法越显著，取得理想的排序效果。1立体堆排序(sHEAPSORT)算法设t^l，如⋯⋯，^。)是个数为n的元素序列，若札孚J+。≥鱼(1≤L主亏三J+1≤n)，则称{^1．^2⋯⋯，k)序列为立体堆L“”J。SHEAPsORT算法思想和堆排序一样，首先，把需要排序的n个元素构成一个立体堆；然后移走立体堆

4、顶元素，重新进行立体堆调整：将其前、左、后、右4个子结点中的大者上升一层，每上升一层，只需J要做3次比较。结点上升过程重复进行到{^层(^为当前立体堆的深度)，再将最后一个叶子结点元素移人该层当前所缺的结点上。当这个新移人的结点需要上升时，通过逐次与其父结点做1次比较来实现．直至根结点；当它需要下渗时，通过前、左、后、右4个子结点中的大者比较，沿着某条路径下渗，每下渗一层需做4次比较，直至叶子结点。这样使得剩余n—l的个元素重新构成一个立体堆。再移去根结点上的次大值元素，如此反复执行，便能得到已排序的序列。定理lsHEAPSoRT算法时间复杂度为r(n)={n+鼍∑(L

5、l罐‘j+2)．证明设排序元素个数为f，根据立体堆的性质可得高度‘81^=L{Io毒‘J+l。输出堆顶元素后，通过前、左、后、右4个子结点间的3次比较，使大者上升一层，此过程只进行到{^层，则比较次数为J3·{^；而新移入该层上的结点，在最坏情况下，要J么上升至第一层，则进行{^次比较，要么下渗至叶·收稿日期：：帅一町一06作者简介：帅训渡(1卯9一)，男，山东单县人，工程师，硕士，研究方向：算法设计与分析，人工智能、数据挖掘等。21万方数据2007阜菏泽学院学报第5期子结点，至多进行4·{^次比较。立体堆的调整比较次数为：s·詈一+n一{··詈一，一·吉一)=警一=萼

6、(L{b毋J+-)．因此，n个元素的立体堆调整时间耗费为：封萼(L{喇+-)】=詈薹(Lb纠+2)；而n个数据初始立体堆的比较次数为{n[⋯，所以sHEAPsoRT算法时间复杂度r(4)=詈n+{∑(Ll罐‘J+2)，证毕。因为{基(Llo毋j+2)：詈(。10醪一。10蓝+nIo醛+nlo耋+2)<{nlo篮(当n≥4时)，即JsH队PSoRT算法时间复杂度r(n)<导n+{nlo醪。而常规堆排序的时间复杂度r(n)=4n+2nlo醴[11]。因此，SHEAPSORT算法不仅具有较优的平均时间复杂度’，而且减少了堆排序算法复杂性的常数因子。这也是我们选取sHEAPso

7、RT算法，应用分段排序的优化数据处理技术，以取得高效排序效果而进行探索的出发点。2二次立体堆排序(TsHEAPSORT)算法2．1算法思想为实现n个数据的排序过程，首先对数据进行分段排序优化处理。设对数据的地址只作较少操作的存储空间曰uF，B卯中能存人t个数，把n个数据分成m=L詈J个段，对每一段中的々个数据用sHEAPsoRT算法进行排序。然后对这m个有序段各取堆顶数据．再角sHEAPSORT算法进行第二次立体堆排序。其中立体堆排序为新结点的数据不大于孩子结点数据，取二次立体堆排序的堆顶元素存入另一存储空间。重新调整子立体堆，每当二次立