首页 › Python 实例 › 冒泡排序

Python 冒泡排序

算法实例 038

题目

实现冒泡排序:反复比较相邻元素,把较大的元素逐步"冒"到末尾。加入提前结束的优化。

参考代码

def bubble_sort(items):
    data = list(items)
    n = len(data)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
                swapped = True
        print(f"第 {i + 1} 轮:{data}")
        if not swapped:
            break
    return data

print("结果:", bubble_sort([5, 1, 4, 2, 8, 3]))
执行以上代码输出结果为:
第 1 轮:[1, 4, 2, 5, 3, 8]
第 2 轮:[1, 2, 4, 3, 5, 8]
第 3 轮:[1, 2, 3, 4, 5, 8]
第 4 轮:[1, 2, 3, 4, 5, 8]
结果: [1, 2, 3, 4, 5, 8]

代码解析

每一轮结束后,最大的元素会被放到未排序部分的末尾。如果某一轮没有发生交换,说明已经有序,可以提前结束。冒泡排序的时间复杂度是 O(n²),实际开发中直接使用 sorted() 即可。