插入排序

参考: 插入排序(动图理解)

# insertsort
"""
拿后一个数跟前一个数比
如果后面的数大于前面的数就忽略，否则交换位置
交换位置后，再继续跟前一个数比，然后重复这个步骤，直到没比他小的或索引为0
"""


def insert_sort(li):
    n = len(li)
    # 认为第一个数有序，每次从后面取一个数
    for j in range(1, n):

        # 从后面取一个数据（倒着取数），跟插入到前面的有序序列中
        for i in range(j, 0, -1):
            # 拿当前位置与前面位置数据进行比较
            if li[i] < li[i - 1]:
                li[i], li[i - 1] = li[i - 1], li[i]
            else:
                break


if __name__ == '__main__':
    l = [4, 2, 3, 5, 1]
    l = [5, 4, 3, 2, 1]
    insert_sort(l)
    print(l)
    # 稳定性：稳定
    # 最坏时间复杂度：O(n^2)
    # 最优时间复杂度：O(n)