冒泡排序算法

冒泡排序是所有排序算法中最简单、最易实现的算法。实现思路是：比较相邻两个元素的值，如果后者比前者的值小就交换它们的位置；一趟排序完成后，则无序区减少一个数，有序区增加一个数。时间复杂度为O(n^2)。

代码示例

def bubble_sort(lst):
    for i in range(len(lst) - 1):
        for j in range(len(lst) - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
        # print(lst)

lst = [4, 3, 1, 6, 5, 2]
# print(lst)
bubble_sort(lst)

代码优化

优化思路：如果没有需要交换的元素，则循环结束。如果本来就是排好序的，则只需要走一趟循环。

def bubble_sort(lst):
    for i in range(len(lst) - 1):
        flag = False
        for j in range(len(lst) - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
                flag = True
        if not flag:
            break

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