论文部分内容阅读
近年来,人们提出了不少排序运算量为O(N)的新算法。但对这些算法分析研究的结果表明,普遍存在着以下两点不足:(1)附加空间开销大;(2)排序效率过分依赖于键值的均匀分布。对此,本文提出了一个新的排序算法——二次分级连接排序法。该方法保证排序时间在最坏情况下为O(N)的基础上,仅需附加空间开销N+(ΔM)~(1/2)+2。这里,ΔM为键值的变化范围。