""" 
选择排序，从未排序序列中选择一个最小的值放到未排序序列首位
"""
def select(lst):
    for i in range(len(lst)-1):
        k = i
        for j in range(i+1, len(lst)):
            if lst[j] < lst[k]:
                k = j
        lst[i], lst[k] = lst[k], lst[i]
    return lst

lst = [4, 1, 3, 1, 5, 2, 7, 6]
print(select(lst))

""" 
冒泡排序， 比较相邻位置元素的大小， 把大的往后排， 最后会把最大的元素排到最后， 像冒泡一样。
"""
def buble(lst):
    for i in range(len(lst)- 1, 0, -1):
        for j in range(i):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst

lst = [4, 1, 3, 1, 5, 2, 7, 6]
print(buble(lst))

""" 
插入排序， 先选择一个基准元素， 然后在已排序区域
从右往左与基准元素进行比较，比基准元素大， 就往右移动， 和扑克牌一样
"""
def insert(lst):
    for i in range(1, len(lst)): # 第一个元素不用排序
        base = lst[i] 
        j = i - 1 # 已排序区域最右端元素
        while j >= 0 and lst[j] > base:  # 确保没有超出序列最左端， 以及元素比基准元素大
            lst[j+1] = lst[j]           # 元素后移
            j -= 1                      # 再比较左边的元素
        lst[j+1] = base                 # 将基准元素插入空出来的位置
    return lst

lst = [4, 1, 3, 1, 5, 2, 7, 6]
print(insert(lst))