10.16112/j.cnki.53-1223/n.2020.02.008
基于划分的基数交换排序算法改进研究
基于划分提出了一种改进的基数交换排序算法.改进后的算法只需少量额外内存即可将时间复杂度调整到Θ(mn),其中m为数据二进制的存储位数,而且除了处理整数外算法还能处理浮点数.针对提出的改进算法,本文还进行了优化,通过定理4论证,正(负)整数的时间复杂度降至Θ(nlog2(ω)),其中ω=max⊕min表示序列最小值与最大值的位异或结果,引理1证明,算法时间复杂度降至Θ(min(mn,nlog2n)).本文提出的改进算法能从时间以及空间上提升算法效率.
基数交换、非比较排序、算法优化、算法改进
45
TP311.1(计算技术、计算机技术)
国家自然科学基金项目51467007
2020-06-11(万方平台首次上网日期,不代表论文的发表时间)
共8页
58-65