王代星，袁琳琳

(1.贵州大学 教育教学评估中心、高等教育研究所，贵州 贵阳 550025;2.贵州职业技术学院，贵州 贵阳 550023)

0 引 言

插入排序是计算机内部排序中最简单的排序算法之一。它的基本思想是把第一个元素当作初始有序序列，从第二个元素开始，逐个将所有元素向前插入到该序列之中。插入排序主要有两个基本操作，即查找插入位置时的数据比较和插入时的数据移动，通常把数据比较次数和数据移动次数作为算法的时间复杂度。根据查找插入位置方式的不同，又分为直接插入排序和折半插入排序。折半插入排序也可视为直接插入排序的改进算法，通过折半查找方式，减少了数据比较次数，但数据移动次数没有改变。2-路插入排序[1]是折半插入排序的改进算法，能相对减少排序过程中数据的移动次数，但空间复杂度从O(1)增加到了O(n)，时间复杂度受第一个元素影响。当第一个元素是最大或最小的元素时，算法的时间复杂度变得与折半插入排序一致。针对这些不足，文中提出一种改进算法，即双向交替折半插入排序算法。通过在待排序序列的两端交替地插入排序，使数据移动次数比折半插入排序降低了50%、比2-路插入排序降低了25%，避免了2-路插入排序效率受分界元素影响的缺点，排序在序列的中间点结束，空间复杂度恢复为O(1)。

1 2-路插入排序算法简介

对于长度为n的待排序序列r[0…n-1]，另设置等长的同类型数组d，将r[0]赋给d[0]，将数组d视为一个循环向量，排序在d中进行。……