在上节中,我们学习了直接插入排序法,本次我们来学习它的改进方法:折半插入排序法.

  折半插入排序是对直接插入排序算法的一种改进,折半插入排序与直接插入排序算法原理相同.只是,在向已排序的数据中插入数据时，采用折半查找（二分查找）.先取已经排序的序列的中间元素,与待插入的数据进行比较,如果中间元素的值大于待插入的数据,那么待插入的数据属于数组的前半部分，否则属于后半部分。
与直接插入相比,折半插入改善了算法中比较次数的数量级大的问题,但是对于移动元素的时间耗费并没有改变,因此折半插入排序法的时间复杂程度还是O(n2),只是寻找插入位置时更省时间.

折半插入排序法的图例如下:

折半插入排序法的代码如下

def BinaryInsertSort(mylist):
    for i in range(1, len(mylist)):
        """将当前元素暂存起来"""
        tmp = mylist[i]
        """在当前位置之前的范围查找插入"""
        low = 0
        high = i - 1
        """将范围折半再查找"""
        while low <= high:
            m = int((low + high) / 2)
            """tmp比范围中点大，范围后半段作为新的查找范围"""
            if tmp > mylist[m]:
                low = m + 1
            else:
                """tmp比范围中点小，范围前半段作为新的查找范围"""
                high = m - 1
        """此时mylist[high]的元素比tmp小"""
        j = i - 1
        """mylist[high]之后的元素往后挪一位"""
        while j >= high + 1:
            mylist[j + 1] = mylist[j]
            j -= 1
        """将tmp放在mylist[high]之后"""
        mylist[high + 1] = tmp
 
if __name__ == "__main__":
    mylist = [49, 38, 65, 87, 76, 13, 27, 49]
    BinaryInsertSort(mylist)
    print(mylist)

输出:

[13, 27, 38, 49, 49, 65, 76, 87]