class Sort:
    # 插入排序0
    # 算法思想：将当前元素插入到左边以排序好的序列中，插入过程中两两比较交换位置实现元素插入到所在位置
    # 算法特性：
    # （1）与初始状态有关
    # 时间复杂度：O(n^2)
    # 空间复杂度：T(1)
    # 稳定性：稳定
    def insertion0(self, m):
        length = len(m)
        for i in range(1, length):
            for j in range(i, 0, -1):
                if m[j] < m[j-1]:
                    temp = m[j]
                    m[j] = m[j-1]
                    m[j-1] = temp
        return m

    # 插入算法改进版
    # 算法思想：不再是两两换位置，而是将比当前大的数尽量放后边
    def insertion1(self, m):
        length = len(m)
        for i in range(1, length):
            temp = m[i]
            j = i
            while j > 0:
                if temp < m[j-1]:
                    m[j] = m[j-1]
                else:
                    break
                j -= 1
            m[j] = temp
        return m

if __name__ == '__main__':
    s = Sort()
    m = [3, 2, 1]
    print(s.insertion1(m))