作业 15：冒泡排序¶

本页最后更新于，内容可能过时

从键盘读入 n 个整数，用冒泡排序把它们按从小到大的顺序排列后输出。

以下为 Python 版本的冒泡排序示例，算法的可行性与复杂性证明见页面底部。

def BUBBLE_SORT(A):
    n = len(A)
    for i in range(n - 1):
        swapped = False

        # 每轮把未排序部分的最大值 冒泡到末尾部分
        for j in range(n - 1 - i):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]
                swapped = True

        # 本轮没有发生交换, 说明已经有序
        if not swapped:
            break

示例 1¶

输入：

5
3 1 2 5 4

输出：

1 2 3 4 5

示例 2¶

输入：

4
-2 8 -2 0

输出：

-2 -2 0 8

提示¶

第一行一个整数 n，范围是 1 到 1000
第二行 n 个整数，用空格分隔
输出一行 n 个整数，从小到大排列，用空格分隔，行末换行
判题只看输出的序列，用别的方法排出同样的结果也算通过
除结果外不用输出其他内容

提交和评测¶

先自测，再提交

使用 IDE 写好代码，先在本机运行一遍样例
所有样例通过后，再把代码粘贴到这里进行提交
助教服务器的性能有限，建议先自测再提交
2 分钟最多交 5 次，如果提交太频繁会被拒绝，稍后再提交即可

你的学号：

编译未通过，报错信息如下：

冒泡排序的可行性与复杂性证明¶

def BUBBLE_SORT(A):
    n = len(A)
    for i in range(n - 1):
        swapped = False

        # 每轮把未排序部分的最大值 冒泡到末尾部分
        for j in range(n - 1 - i):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]
                swapped = True

        # 本轮没有发生交换, 说明已经有序
        if not swapped:
            break

可行性证明¶

循环不变量：在每次循环开始时，末尾部分的子数组 \(\{n-i,\cdots,n-1\}\) 是有序的（也就是数组末尾的 \(i\) 个数是有序的）
1. 起始：当\(i=0\)时，末尾含0个元素，子数组为空，结论成立
2. 递推：已知末尾\(i\)个元素有序，内层循环逐对比较相邻元素，其中的最大元素会一直后移
所以外层下标为\(i\)的循环结束时，\(A[n-1-i]\)成为当前循环的未排序部分的最大值
保证末尾\(i+1\)个元素有序
3. 结束：当\(i=n-1\)时，末尾\(n-1\)个元素都有序，剩下的第一个元素即是数组的最小值，因此整个数组有序

最好情况复杂度¶

最好情况：如果输入数组已有序
那么第一轮内层循环比较\(n-1\)次，没有发生交换，直接退出
因此比较次数 \(n-1=\Theta(n)\)

最坏情况复杂度¶

最坏情况：如果输入数组已反向有序
那么当外层下标为\(i\)时，未排序部分有\(n-i\)个元素
内层循环需要做\(n-1-i\)次相邻比较，每对都要交换
因此比较次数 \(\sum_{i=0}^{n-2}(n-1-i)=\frac{n(n-1)}{2}=\Theta(n^2)\)
交换次数与比较次数相同，也是\(\frac{n(n-1)}{2}\)

平均复杂度¶

随机变量 \(X_{ij}:=\{A[i]和A[j]是否逆序\}\)
输入为随机排列时，\(P(X_{ij}=1)=1/2\)
所以 \(E[X_{ij}]=1\cdot1/2+0\cdot1/2=1/2\)
总交换次数 \(X=\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}X_{ij}\)
\(E[X]=\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}E[X_{ij}]=\binom{n}{2}\cdot\frac{1}{2}=\frac{n(n-1)}{4}=\Theta(n^2)\)

没有交换时提前退出，这一条件通常在最后一轮才满足
因此除已有序的输入以外，比较次数为\(\sum_{i=0}^{n-2}(n-1-i)=\Theta(n^2)\)

冒泡排序是稳定排序¶

冒泡排序稳定：相邻比较用严格大于，相等时不交换
相等的两个元素不会跨过对方，相对次序保持不变
例如 \([2_a,2_b,1]\) 第一轮只交换\(2_b\)与1，得到 \([2_a,1,2_b]\)

判题环境

判题用的是服务器的 isolate 沙箱：

操作系统：Ubuntu-26.04
编译器：GCC 15.2.0
编译参数：-O2 -std=gnu23
每个测试点限时 1 秒
每个测试点限制内存 256 MB