思路:
把数组分为两个区间，已排序区间和待排序区间。初始已排序区间就是数组的第一个元素，之后遍历待排序区间所有元素，依次插入已排序区间的正确位置。
- 时间复杂度:
O(n**2) - 空间复杂度:
O(1) - 是否稳定: 稳定. 对于值一样的元素, 后出现的在后面
示例
以列表[5,7,4,6,3,1,2,9,8]展开
（1）把最开始的数值5当做有序，有序并不是真正的有序，而是相对的有序，因为之后可能还要往后移。
（2） 一个个往后走，和前面相对有序区进行比较，找到合适位置进行插入。然后就实现了所有的排序。
假设，摸到牌的下标是i，那么它前面的一位j=i-1，两两比较，然后替换，下标也替换，继续往前推进，有2种情况：
- 正常情况，当2不断向前推进，直到遇到j=1，进行比较的时候，li[j]<li[i]，那么这个时候，i的值就插入到j的后面，也就是j+1的位置
- 第二种情况是，4不断向前推进，到头了，此时假设5前面一位的下标是-1,那么也是插入到j+1即0的位置
所以，在j下标大于等于0，且j的数值比i的数值大的情况下，j数值就往后移一个下标，即 li[j+1] = li[j]， 同时j的下标要往前移动一个位置。只要不是这两种情况，即到头了或者是找到了小的值，这个时候就进行替换。
def insert_sort(li):
for i in range(1, len(li)): # i表示摸到的牌的下标
tmp = li[i] # 摸到的牌
j = i - 1 # j就是i往前不断推进的时候，j的下标
while j >= 0 and li[j] > tmp: # 只要往后挪就循环 2个条件都得满足。 如果 j=-1 停止挪 如果li[j]小了 停止挪
li[j+1] = li[j] # j位置的数就往后挪一下
j -= 1 # j不断的往前移
# j位置在循环结束的时候要么是-1要么是一个比tmp小的值
li[j+1] = tmp
li = list(range(10000))
random.shuffle(li)
insert_sort(li)
注意 : while循环的条件，最好将j >= 0放到and的前面，因为算法在语言间是通用的，具有布尔短路功能，即and前面的条件如果为False，就不会进行后面的计算了.
