冒泡排序

定义与基本思想

冒泡排序（Bubble Sort）是一种简单直观的排序方法。其基本思想是：每一趟从头到尾依次比较相邻元素，将较大（或较小）元素逐步“冒泡”到序列末尾，重复多趟直到全部有序。

冒泡排序演示

4321

下一步

算法描述

1. 从头到尾依次比较相邻元素，若顺序错误则交换
2. 每一趟将未排序部分的最大（或最小）元素“冒泡”到末尾
3. 重复 $n-1$ 趟，直到全部有序

伪代码如下：

for i = 0 to n-2:
    for j = 0 to n-2-i:
        if A[j] > A[j+1]:
            swap(A[j], A[j+1])

时间复杂度分析

• 最好情况：$O(n)$（已排序，优化后）
• 最坏/平均情况：$O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：稳定排序

练习题

练习 1

对数组 $A = [4, 3, 2, 1]$ 进行冒泡排序，写出每一趟排序后的结果。

参考答案

解题思路：每趟将最大元素“冒泡”到末尾。

详细步骤：

1. 初始：[4, 3, 2, 1]
2. 第 1 趟：[3, 2, 1, 4]
3. 第 2 趟：[2, 1, 3, 4]
4. 第 3 趟：[1, 2, 3, 4]

答案：如上，每一趟后最大元素归位。

练习 2

冒泡排序的时间复杂度和空间复杂度分别是多少？

参考答案

解题思路：考查复杂度和空间。

详细步骤：

1. 时间复杂度 $O(n^2)$
2. 空间复杂度 $O(1)$

答案：时间 $O(n^2)$，空间 $O(1)$。