排序算法(2)

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

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

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

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

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

输出:

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