双向交替折半插入排序法

摘要

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