冒泡排序是一种简单的排序算法,它通过不断比较相邻的元素并交换位置来逐步将数组中的元素按照升序或降序排列。以下是冒泡排序的基本步骤:
初始化:
- 设定一个标志变量
swapped
,用于表示在一轮迭代中是否发生过交换。
- 设定一个标志变量
遍历数组:
- 从第一个元素开始,依次比较相邻的两个元素。
交换元素:
- 如果前一个元素比后一个元素大(对于升序排序),则交换它们的位置。
更新标志变量:
- 如果发生了交换,则将
swapped
设置为true
,否则保持原值。
- 如果发生了交换,则将
检查是否已排序:
- 在每轮迭代结束后,如果
swapped
仍然为false
,说明已经没有需要交换的元素,此时可以提前结束排序过程。
- 在每轮迭代结束后,如果
以下是一个Python实现冒泡排序的例子:
def bubble_sort(arr):
n = len(arr)
swapped = True
while swapped:
swapped = False
for i in range(n-1):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
swapped = True
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)
在这个例子中,我们使用了一个布尔变量swapped
来跟踪是否有元素被交换。当不再有元素需要交换时,冒泡排序就可以停止了。这样可以提高算法的效率,特别是当输入数据已经是部分有序的情况下。