|
|||||
|
|
| 基于划分的基数交换排序算法改进研究 | |
| 引用本文： | 吴俊斌,吴晟,吴兴蛟,丁家满.基于划分的基数交换排序算法改进研究[J].昆明理工大学学报(理工版),2020,45(2):58-65. |
| 作者姓名： | 吴俊斌 吴晟 吴兴蛟 丁家满 |
| 作者单位： | 昆明理工大学信息工程与自动化学院,云南昆明650500;华东师范大学计算机科学与技术学院,上海200062 |
| 摘 要： | 基于划分提出了一种改进的基数交换排序算法.改进后的算法只需少量额外内存即可将时间复杂度调整到Θ(mn),其中m为数据二进制的存储位数,而且除了处理整数外算法还能处理浮点数.针对提出的改进算法,本文还进行了优化,通过定理4论证,正(负)整数的时间复杂度降至Θ(nlog_2(ω)),其中ω=max⊕min表示序列最小值与最大值的位异或结果,引理1证明,算法时间复杂度降至Θ(min(mn,nlog_2n)).本文提出的改进算法能从时间以及空间上提升算法效率. |
| 关 键 词： | 基数交换 非比较排序 算法优化 算法改进 |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |