数据结构之排序三：插入排序

def insert_sort(ary):
    n = len(ary)
    for i in range(1,n):
        if ary[i] < ary[i-1]:
            temp = ary[i]
            index = i           # 待插入的下标
            for j in range(i-1,-1,-1):  # 从i-1 循环到 0 (包括0)  最后一个参数是步长，倒着取值要为负
                if ary[j] > temp :
                    ary[j+1] = ary[j]
                    index = j   # 记录待插入下标
                else:
                    break
            ary[index] = temp
    return ary

 时间复杂度:：

　　平均：O(n^2)

　　最坏：O(n^2)  # 倒序

　　最好：O(n)  # 有序的时候

空间复杂度：O(1)

稳定性：稳定