插入排序，按照顺序将选中的顺序与前方的数字进行比较，在比前面小的场合与其交换位置并且再次进行比较，直到比前方数字大的场合停止，对下一个数字进行如上操作。

def insertionSort(arr):
    for i in range(1, len(arr)):   # 从第二个元素开始比较，i表示当前的要插入的元素
        key = arr[i]
        j = i - 1
        # 把arr[i]插入到arr[0:i]中，arr[0:i]是有序的
        while j>=0 and arr[j]>key:  # 如果满足条件,arr[j]就往后移
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key