冒泡排序

定义与基本思想

冒泡排序（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])

代码实现

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]$ 进行冒泡排序，写出每一趟排序后的结果。

习题 2

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

上一章节插入排序介绍插入排序的基本思想、算法流程、复杂度分析及典型习题。

下一章节选择排序介绍选择排序的基本思想、算法流程、复杂度分析及典型习题。