python-二分法插入排序（Binary Insert Sort）
前注：面试的时候被问到各种排序算法的时间复杂度，那时候回答的是插入排序最快可以达到nlogn。后来想了想我那时候为什么会这么回答，突然想到将二分查找和插入排序结合起来就可以做到了，于是就有了这篇文章。之后去网上查才发现已经有这种算法了，我还是太菜了。
一.代码
1.直接插入排序
def insert_sort(l) :
length = len(l)
for i in range(1,length) :
j = i - 1
while l[j] > l[i] and j >= 0:
j -= 1
l.insert(j + 1, l.pop(i))
return l注：这里的直接插入排序是将第i个的数找到在前i-1个已经排序好的数中的位置并插入，移除原来位置上的数。
时间复杂度为O(n²)，空间复杂度为O(1)
2.二分法插入排序
def binary_insert_sort(l) :
length = len(l)
for i in range(1, length) :
be, en = 0, i - 1
mid = (en + be) // 2
while True :
if mid < 0 or l[mid] == l[i] or (be >= en):
if mid >= 0 and l[mid] > l[i] :
l.insert(mid, l.pop(i))
else :
l.insert(mid + 1, l.pop(i))
break
elif l[mid] > l[i] :
en = mid - 1
else :
be = mid + 1
mid = (en + be) // 2
return l注：二分法插入排序是将第i个数，使用二分法查找在前i-1个有序排列的数中的位置，再进行插入操作，并移除原来位置上的数。
时间复杂度为O(nlogn)，空间复杂度为O(1)
二.效率
使用python中list自带的sort与上述两种插入排序进行比较。
（注:此处仅以sort为基准，sort的实现是基于混合的排序算法，且经过优化）
测试代码：
（注：需import random）
def main(num) :
time1, time2, time3 = 0, 0, 0
for i in range(1,num + 1) :
print("\rnow is", i * 100.0 / num, "%", end = "")
l = list(range(num))
random.shuffle(l)
l1, l2 = l[:], l[:]
tb = time.clock()
binary_insert_sort(l)
tf = time.clock() - tb
time1 += tf
tb = time.clock()
l1.sort()
tf = time.clock() - tb
time2 += tf
tb = time.clock()
insert_sort(l2)
tf = time.clock() - tb
time3 += tf
print("\rbinary_insert_sort use", time1)
print("origin sort use", time2)
print("insert_sort use", time3)测试结果：
（单位：秒）
