双向交替折半插入排序法

来源：计算机技术与发展杂志2020年第07期北京时间：

作者：王代星;袁琳琳

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

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