冒泡排序

定义与基本思想

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

冒泡排序

点击“执行一步”观察算法状态变化。

算法描述

从头到尾依次比较相邻元素，若顺序错误则交换
每一趟将未排序部分的最大（或最小）元素“冒泡”到末尾
重复 $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])

代码实现

void BubbleSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;             // 本趟是否发生交换
        for (int j = 0; j < n - 1 - i; j++) {
            if (A[j] > A[j + 1]) {
                int tmp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = tmp;
                flag = true;
            }
        }
        if (!flag) break;              // 本趟无交换，说明已有序
    }
}

优化说明

标志位 flag 记录本趟是否有交换：若某一趟没有任何交换，说明序列已经有序，可以提前结束。这使最好情况（已有序）只需一趟，比较 n-1 次，达到 $O(n)$ 。

时间复杂度分析

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

习题

习题 1

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

参考答案

冒泡排序排序过程相邻比较

解题思路：

本题考查冒泡排序的执行过程。核心思想是每一趟通过相邻元素两两比较，把本趟未排序区间中的最大元素“冒泡”到该区间的末尾；随着趟数增加，未排序区间逐步缩小。

详细步骤：

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

最终答案：

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

习题 2

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

参考答案

冒泡排序时间复杂度空间复杂度

解题思路：

本题考查冒泡排序的复杂度分析。冒泡排序对 $n$ 个元素最多进行 $n-1$ 趟扫描，每趟要做 $O(n)$ 次相邻比较，故平均与最坏时间复杂度都是 $O(n^2)$ ；整个过程只在原数组内做交换，不需要额外辅助空间。

详细步骤：

时间复杂度 $O(n^2)$ ：每趟最多 $O(n)$ 次相邻比较，共需 $n-1$ 趟。
空间复杂度 $O(1)$ ：排序只在原数组内交换元素，不需要与 $n$ 同规模的辅助数组。
对比参考：堆排序的时间复杂度为 $O(n \log n)$ 、空间为 $O(1)$ ；归并排序的时间复杂度为 $O(n \log n)$ 、空间为 $O(n)$ ，均可由本课程其他习题的结论直接对照。