双向交替折半插入排序法

• 作者: 王代星 袁琳琳
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 插入排序 双向 交替 折半插入 算法改进
• 年，卷（期）: 2020,（7）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 25-29
• 页数: 5页
• 分类号: TP301
• 字数: 5044字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2020.07.006

摘要

提出了一种2-路插入排序法的改进算法.首先在分析2-路插入排序算法和其他改进算法的基础上,给出了改进算法的思想、算法描述、算法分析.改进算法通过在待排序序列的两端交替地插入排序,有效地减少了数据移动次数.同时保证两端的有序序列同步增长,排序在序列的中间点结束,有效地避免了2-路插入排序效率受分界元素影响的缺点.算法的空间复杂度为O(1).实验数据证明,在对随机序列排序时,数据移动次数比折半插入排序降低了50％、比2-路插入排序降低了25％;在对正序序列排序时,数据比较次数为2n–3次,数据移动次数为0次,而2-路插入排序的数据比较次数为nlog2 n次,移动数据为2n次;在对逆序数据排序时,相比2-路插入排序而言,数据比较次数降低了47.37％,数据移动次数降低了25％.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	袁琳琳		4	2	1.0	1.0