双向交替折半插入排序法

摘要：

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

关键词：插入排序、双向、交替、折半插入、算法改进

所属期刊栏目：30

分类号：TP301(计算技术、计算机技术)

资助基金：贵州省自然科学基金黔科合基础[2019]1130号

在线出版日期：2020-07-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：25-29