地址排序的一种新算法—链缓冲排序.pdf

维普资讯
地址排序的一种新算法
——链缓冲排序
锌珞苏秀蜂
武汉工业大学天津第二塑料厂
。本算法用

算法优亍快速排序算法.
计算机处理问题时所用的时间有以上是在进行排序工作。多年来人们设计了许多
优秀算法,如快速排序、堆排序、冒泡排序等等。这些方法只注重每一元素与其他元素
的比较,
的方法”, 但存在着以下两条艉制: ①寻找除数因子难②对。聚集起来的数据束手无
策。为此我们研究设计了一种能够很好地解决上述两方面问题的新的地址排序算法,使排序
时间维持在级。当数据量犬、存储空间足够时,排序效果极佳, 内存较小时本击不适
用, 数据量小时效果也不是很明显
一
、算法描述和算法分折
. 算法描述
本算法利用如下的数据结梅链表数纽:
十::
:
:; : 、·,
个数据元素分别敏入.,≤≤。在排序时利用的链记录冲突信息,
利用的链作冲突元素的链缓冲区。排序过程如下:
找出数据元素的最大元和最小元。第一次调用本算法时为所有输入数据中的最大、
最小元, 以后各次调用只是找出当前冲突链内的最太,最小元。
由域太、最小元之差与待排序元索个数之比求出除数匿子。
用除数因子计算各元素的地址。按其地址或将其连到链缓冲区中,或将其放入
々. 中
把. 申的元索及其链上的元素按顺序倒回.
中。对有冲突的元素将其返回后的首址及冲突个数记录下来。此时那些投有冲突的
一—
维普资讯
元素就已经到位。
当链不空时,说明还有没有排序的冲突元素,则依次取出个数及首址进行再
次排序, 直到链空为止。这时全部数据元素才排序完毕。
. 算法分析
若不进行递归调用, 排序过程主要分三个阶段: ①求最大、最小元②按地址放数据元
素于相应链缓冲区⑤顺序返回。第一阶段每一元素比较两次, 故⋯, 一
第二阶段每一元素有次比较,故⋯一。:第三阶段对每一元素进行
次比较, 故⋯。一。所以算法执行一遍时, 。
定义某数据元素被调用处理第次时,称当前调用深度为。
定理链缓冲排序算法的最好时间复杂性为。
定理链缓冲排痔算法的最坏时间复杂性为十—一, 为元素最长
位数。
为了证明定理, 我们先给出下面一个辅助定理。
辅助定理链缓冲排序算法调用的最大深度为。
本定理的证明可参阅文献,。下面我们考查定理的正确性。
当递归调用时, 未排序元素个数随调用深度的增加而减少。第一调用深度至少使最
大、最小两个元素定位,未排序元素至多还有”一个,到第调用深度还剩一个元素
需排序到次调用时即最大调用深度至多对一个元素进行排序。所以最坏时
间复杂性为:
”一—⋯一—一
由此可知定理正确。
由辅助定理和定理的论证不难看出,调用深度为时,任何冲突链缓冲区中元素
个数小于等于。否则就有可能在本次调用后再产生冲突, 即还有第次调用。对待排
序的数据元素的最坏情况,前次调用可定位个元素每次调用定位当前最大、最小元
素,第十次调用时最多为个元素,故而总共能定位个元素。