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

• 作者: 丁家满 吴俊斌 吴兴蛟 吴晟
• 来源期刊: 昆明理工大学学报（自然科学版）
• 学科: 工学
• 关键词: 基数交换 非比较排序 算法优化 算法改进
• 年，卷（期）: 2020,（2）
• 所属期刊栏目: 机械、电子信息与自动控制
• 页码范围: 58-65
• 页数: 8页
• 分类号: TP311.1
• 语种: 中文
• DOI: 10.16112/j.cnki.53-1223/n.2020.02.008

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴晟		87	334	10.0	15.0
2	丁家满		39	61	4.0	5.0
3	吴兴蛟		18	49	3.0	6.0
4	吴俊斌		6	7	1.0	2.0