冒泡排序

# bubblesort
"""
用第一个数和第二个数比较，如果前者小于后者，不做交换，否则交换位置
然后用第二个数和第三个数比较，如果前者小于后者，不做交换，否则交换位置
以此类推，然后最大的数在最右边，次要大的数在倒数第二个，最终实现排序
"""


def bubble_sort(li):
    n = len(li)
    # 内部循环每一次能把最大的数移动到最右边，共n-1次
    for j in range(n - 1):  # 0 1 2 3

        # 内部循环一遍，如果没有执行过交换，证明数据已经有序（提高效率）
        flag = 0

        # 定义游标，从0移动到倒数第二个位置
        for i in range(n - 1 - j):  # n-1 n-2 n-3
            # 拿当前位置与下一个位置的数据比较
            if li[i] > li[i + 1]:
                li[i], li[i + 1] = li[i + 1], li[i]
                flag += 1

        # 如果没有这个判断，对于大部分是有序，最后几个元素无序的列表来说
        # 会增加没有必要的循环，加上之后可以提高效率
        if flag == 0:
            return


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