冒泡排序是所有排序算法中最简单、最易实现的算法。实现思路是:比较相邻两个元素的值,如果后者比前者的值小就交换它们的位置;一趟排序完成后,则无序区减少一个数,有序区增加一个数。时间复杂度为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)

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/208