基于划分的基数交换排序算法改进研究

作者：吴俊斌; 吴晟^*; 吴兴蛟; 丁家满

来源：昆明理工大学学报(自然科学版), 2020, 45(02): 58-65.

DOI：10.16112/j.cnki.53-1223/n.2020.02.008

• 基数交换
• 非比较排序
• 算法优化
• 算法改进

基于划分提出了一种改进的基数交换排序算法.改进后的算法只需少量额外内存即可将时间复杂度调整到Θ(mn),其中m为数据二进制的存储位数,而且除了处理整数外算法还能处理浮点数.针对提出的改进算法,本文还进行了优化,通过定理4论证,正(负)整数的时间复杂度降至Θ(nlog2(ω)),其中ω=max⊕min表示序列最小值与最大值的位异或结果,引理1证明,算法时间复杂度降至Θ(min(mn,nlog2n)).本文提出的改进算法能从时间以及空间上提升算法效率.

• 单位
  自动化学院; 昆明理工大学; 华东师范大学