在有序的序列中插入数值,完成插入后的序列保证其有序def insert_sort(orderlist, i):
ret = orderlist[:]
low = 0
hight = len(ret)#去掉减一,不影响整除2
while low < hight:
mid = (low + hight) // 2
if ret[mid] < i:
low = mid + 1 # 加1保证不会进入死循环
else:
hight = mid # 此处加减一不合适,加一增大原已经缩小的范围,减一会使数值插入错误,比如数值大于hight索引处的值,在hight索引处插入反而跑到该索引处值的前面
print(low, i)
ret.insert(low, i)
#数据插入式往后面挤,当数值处于ret[mid]和ret[mid + 1]之间时,最终hight=low=mid+1,
#所以插入后正好在ret[mid]和ret[mid + 1]之间
return ret
lst = [2,3,5,6,7,8,9,10,11,12,13]
newlist = sorted(lst)
for x in (14,5):
newlist = insert_sort(newlist, x)
print(newlist)