冒泡排序（Bubble Sort）是一种简单的排序算法，通过多次比较相邻元素，将较大的元素逐步“冒泡”到列表的末尾。虽然效率不高，但冒泡排序的原理直观，适合理解排序算法的基础。

冒泡排序算法步骤

1. 外层循环：控制需要的排序轮数。每轮循环会将剩余未排序的部分最大值冒泡到末尾。
2. 内层循环：从列表开头开始，两两比较相邻的元素。如果前一个元素大于后一个元素，就交换它们。
3. 优化点：可以使用标志位检查本轮是否有交换发生，如果没有交换说明数组已排序，可以提前终止。

冒泡排序的 Python 实现

python

def 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

return arr

示例

python

# 示例数组

array = [64, 34, 25, 12, 22, 11, 90]

# 调用冒泡排序

sorted_array = bubble_sort(array)

print("排序后的数组:", sorted_array)

代码解析

• for i in range(n)：外层循环控制轮次，每一轮将未排序区域的最大值“冒泡”到最末尾。
• for j in range(0, n - i - 1)：内层循环比较相邻的元素，n - i - 1 确保不比较已经排序的部分。
• arr[j], arr[j + 1] = arr[j + 1], arr[j]：如果前一个元素比后一个大，交换它们。
• 提前退出条件：swapped 作为标志位，在本轮内没有发生任何交换，说明数组已排序，直接结束。

输出

plaintext

排序后的数组: [11, 12, 22, 25, 34, 64, 90]

复杂度分析

• 时间复杂度：平均和最差情况为 O(n2)O(n^2)O(n2)，最好情况（已排序数组）为 O(n)O(n)O(n)。
• 空间复杂度：O(1)O(1)O(1)，只需要常量级额外空间。