[教程]掌握Python冒泡排序，轻松输出最终排序结果

引言冒泡排序是一种简单的排序算法，它重复地遍历待排序的列表，比较每对相邻的项目，并在必要时交换它们的位置。这个算法的名字来源于较小的元素会逐渐“冒泡”到列表的顶端。虽然冒泡排序不是最高效的排序算法，但...

引言

冒泡排序是一种简单的排序算法，它重复地遍历待排序的列表，比较每对相邻的项目，并在必要时交换它们的位置。这个算法的名字来源于较小的元素会逐渐“冒泡”到列表的顶端。虽然冒泡排序不是最高效的排序算法，但它易于理解，是学习排序算法的好起点。

冒泡排序的基本原理

冒泡排序的工作原理是通过重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行，直到没有再需要交换，也就是说该数列已经排序完成。

Python实现冒泡排序

下面是一个使用Python实现的冒泡排序算法的示例：

def bubble_sort(arr): n = len(arr) # 遍历所有数组元素 for i in range(n): # Last i elements are already in place for j in range(0, n-i-1): # 遍历数组从0到n-i-1 # 交换如果发现元素是递减的 if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j]
# 测试冒泡排序函数
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的数组:")
for i in range(len(arr)): print("%d" % arr[i], end=" ")

代码解释

1. bubble_sort(arr): 这是冒泡排序的函数定义，arr 是一个列表，包含了要排序的元素。
2. n = len(arr): 获取列表的长度。
3. 外层循环 for i in range(n): 表示遍历整个列表。
4. 内层循环 for j in range(0, n-i-1): 表示对列表的未排序部分进行遍历。
5. if arr[j] > arr[j+1]: 如果当前元素比下一个元素大，就交换它们的位置。
6. arr[j], arr[j+1] = arr[j+1], arr[j]: 使用元组解包来实现元素的交换。
7. 最后，打印排序后的数组。

冒泡排序的优化

虽然冒泡排序是一个简单的算法，但它的时间复杂度是O(n^2)，在处理大量数据时效率较低。以下是一个优化版本的冒泡排序，它可以在发现数组已经排序好的情况下提前终止：

def optimized_bubble_sort(arr): n = len(arr) for i in range(n): swapped = False for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True # 如果在某一趟遍历中没有发生交换，说明数组已经排序完成 if not swapped: break
# 测试优化后的冒泡排序函数
arr = [64, 34, 25, 12, 22, 11, 90]
optimized_bubble_sort(arr)
print("优化排序后的数组:")
for i in range(len(arr)): print("%d" % arr[i], end=" ")

在这个优化版本中，我们引入了一个布尔变量 swapped，如果在某一趟遍历中没有发生交换，那么就可以提前终止排序过程，因为这意味着数组已经是有序的。

总结

冒泡排序是一个基础且易于实现的排序算法。虽然它的效率不是很高，但对于小规模数据或者教学目的来说，它仍然是一个很好的选择。通过理解和实现冒泡排序，你可以加深对排序算法和编程语言的理解。