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() 即可。