摘要
近年来,人们提出了不少排序运算量为O(N)的新算法。但对这些算法分析研究的结果表明,普遍存在着以下两点不足:(1)附加空间开销大;(2)排序效率过分依赖于键值的均匀分布。对此,本文提出了一个新的排序算法——二次分级连接排序法。该方法保证排序时间在最坏情况下为O(N)的基础上,仅需附加空间开销N+(ΔM)^(1/2)+2。这里,ΔM为键值的变化范围。
Some sorting methods that the expected,time-complexity is of O(N) were discussed in the related papers in the past few years. But, the analysis of algorithm shows that there are two drawbacks in these algorithms, (1) requires a large amount of extra space and (2) the property of the expected time-complexity is limited to
uniformly distributed inputs. So, a new sorting method-twice grading and
linking sort-method is given in this paper, which keeps the run-time complexity of O(N) in a worst-case and the extra space requirements is only of N+2, where △M is the value range of the data sorted.
出处
《计算机应用与软件》
CSCD
1995年第1期33-36,42,共5页
Computer Applications and Software