冒泡排序（Bubble Sort）[编辑 | 编辑源代码]

冒泡排序是一种简单的比较排序算法，通过重复遍历待排序列表，依次比较相邻元素并交换位置，使较大（或较小）元素逐渐“浮”到列表末端。因其排序过程中元素像气泡一样上浮而得名。

算法原理[编辑 | 编辑源代码]

核心思想[编辑 | 编辑源代码]

1. 相邻比较：从列表首部开始，比较相邻的两个元素。 2. 交换条件：若前一个元素大于后一个元素（升序排序时），则交换它们的位置。 3. 遍历终止：每一轮遍历会将当前未排序部分的最大元素移动到正确位置，下一轮遍历范围减少一位。

动态示例[编辑 | 编辑源代码]

代码实现[编辑 | 编辑源代码]

以下是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

# 示例
input_list = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", input_list)
print("排序后:", bubble_sort(input_list))

输出结果：

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

复杂度分析[编辑 | 编辑源代码]

时间复杂度与空间复杂度
情况	时间复杂度	说明
最优情况（已有序）	$O (n)$	通过swapped标志提前退出
平均情况	$O (n^{2})$	嵌套循环导致平方级复杂度
最差情况（逆序）	$O (n^{2})$	需完全执行所有比较
空间复杂度	$O (1)$	原地排序，仅需常数空间

优化策略[编辑 | 编辑源代码]

1. 提前终止：若某轮遍历未发生交换，说明列表已有序。 2. 记录最后交换位置：下一轮遍历只需到该位置即可。

实际应用场景[编辑 | 编辑源代码]

教学工具：因逻辑简单，常用于算法入门教学。
小规模数据：当数据量极小（如 $n < 50$ ）时，可能优于复杂排序算法。
部分有序数据：若列表基本有序，优化后的冒泡排序效率接近 $O (n)$ 。

与其他排序算法对比[编辑 | 编辑源代码]

优点：实现简单、空间效率高。
缺点：大规模数据性能差，不适合实际生产环境。

页面模块:Message box/ambox.css没有内容。

练习问题[编辑 | 编辑源代码]

手动模拟冒泡排序对列表 `[7, 3, 9, 2, 5]` 的排序过程。
尝试用其他编程语言（如Java/C++）实现冒泡排序。