冒泡排序优化实现

冒泡排序通过重复遍历列表，比较相邻元素并交换位置实现排序。优化版本通过以下改进提升效率：

1. 提前终止：当某次遍历无交换时，说明已有序
2. 减少遍历范围：每次遍历后，最大元素已就位

def optimized_bubble_sort(arr):
    n = len(arr)
    # 外层循环控制遍历次数
    for i in range(n):
        swapped = False  # 交换标志位
        # 内层循环范围逐渐缩小（n-i-1）
        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

算法说明

1. 时间复杂度：
   • 最优情况（已排序）：$O(n)$
   • 最差情况（逆序）：$O(n^2)$
2. 空间复杂度：$O(1)$（原地排序）
3. 稳定性：稳定排序（相等元素不交换）

使用示例

# 测试排序
data = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", data)
optimized_bubble_sort(data)
print("排序后:", data)

输出结果

排序前: [64, 34, 25, 12, 22, 11, 90]
排序后: [11, 12, 22, 25, 34, 64, 90]

此优化版本在最好情况下只需$O(n)$时间，比基础版本效率更高，特别适合处理接近有序的数据集。