排序三人组：冒泡、选择与插入

三个算法的时间复杂度都为 O(n²)。

冒泡排序

遍历列表的每一个值，如果当前值大于当前值的后面一个值，则交换两个值的位置，使较大的值处于后面。重复遍历直到排好序为止。
算法实现:

def bubble_sort(li):
    """冒泡排序
    遍历 len(li)-1 趟 (从0开始)
    """
    cycles = len(li) - 1
    for i in range(cycles):
        is_exchanged = False
        for j in range(cycles - 1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                if not is_exchanged:
                    is_exchanged = True
        if not is_exchanged:
            break

选择排序

遍历列表，找到最小的值，将它放到一个新的位置。如此反复直到剩下的所有值都转移到新位置为止。算法实现:

def select_sort(li):
    """选择排序
    遍历 len(li) - 1 趟 (从0开始)"""
    li_length = len(li)
    for i in range(li_length-1):
        
        # 找到并记录最小元素所在位置
        min_loc = i     
        for j in range(i+1, li_length):
            if li[j] < li[min_loc]:
                min_loc = j
        
        if min_loc != i:
            li[min_loc], li[i] = li[i], li[min_loc]

插入排序

插入排序类似于摸牌，每当摸到一张新牌时，就和手里面的牌依次进行比较，如果小于被比较的牌，则将被比较的牌往后移一位，直到大于被比较的牌或前面没有牌可以比较时(即摸到的牌为当前手里牌最小的牌)，将摸到的牌插入到当前位置的后一位。算法实现：

def insert_sort(li):
    """插入排序
    类似于打牌，从列表中依次取一张牌
    用获取的牌与手中的牌依次对比
    如果获取的牌比对比的牌小，则将它插入到对比的牌的前面
    """
    for i in range(1, len(li)):
        # 假定第一张牌为手中的牌
        # i 表示获取的牌的下标
        tmp = li[i]
        # j 表示手里牌的下标
        j = i - 1
        while j >= 0 and li[j] > tmp:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp