【例5.6】冒泡排序

GitHub跳转原题关系图返回列表

通过双重循环实现冒泡排序算法,将数组元素按从大到小排列。

OJ: roj

题目 ID: 5041

难度:入门

标签:排序冒泡排序

创建: 2026-10-08 23:17

更新: 2026-10-08 23:17

形式化题目

给定一个长度为 nn(1≤n≤201 \le n \le 20)的序列,序列中的每个元素均为小于 10001000 的非负整数。 要求使用冒泡排序算法将序列按从大到小的顺序进行排序。 最后将排序后的序列输出,每个整数占一行。

正解

思路

这道题目是一道经典的排序题。题目中明确要求了使用冒泡排序,因此我们需要显式地实现冒泡排序算法,而不能直接调用语言内置的排序函数(如 C++ 的 std::sort 或 Python 的 sorted() 及其它内部封装的 .sort())。

冒泡排序的核心思想是:比较相邻的元素。如果第一个比第二个小(因为我们要降序排列,所以需要大的在前),就交换他们两个。 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最小的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

具体到降序排列,即对于相邻的 a[j] 和 a[j+1],如果 a[j] < a[j+1],则交换这两个元素。由于对于相同的元素不需要交换(不满足 < 的条件),因此该排序过程是稳定的。不过由于输入中相等的数字不可区分,所以在输出表现上没有区别,稳定性对答案没有影响。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 22:55
# update_at: 2026-10-08 22:55

import sys


def bubble_sort(a: list[int]) -> None:
    """冒泡排序(降序),原地修改:题面显式要求冒泡,故不调用语言内置排序。"""
    n = len(a)
    for i in range(n - 1):          # 外层控制趟数
        for j in range(n - 1 - i):  # 每趟结束,末尾 i 个数已就位,内层范围收缩
            if a[j] < a[j + 1]:     # 降序:前一个数比后一个小就交换
                a[j], a[j + 1] = a[j + 1], a[j]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, 0)
    if n == 0:
        return

    a = [next(data) for _ in range(n)]

    bubble_sort(a)

    sys.stdout.write("\n".join(map(str, a)) + "\n")  # 题面要求每个数占一行


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 22:55
 * update_at: 2026-10-08 22:55
 */
#include <iostream>

using namespace std;

typedef long long ll;

const ll MAXN = 25; // 题面 n <= 20,多开几个留余量

ll n;         // 待排序数的个数,题面给定 1 <= n <= 20
ll a[MAXN];   // a[0..n-1] 存放输入的非负整数

// 冒泡排序(降序):题面显式要求「冒泡排序」,因此不调用 std::sort
void bubble_sort() {
    for (ll i = 0; i < n - 1; i++) {        // 外层控制趟数
        for (ll j = 0; j < n - 1 - i; j++) { // 每趟结束,末尾 i 个数已就位,内层范围收缩
            if (a[j] < a[j + 1]) {           // 降序:前一个数比后一个小就交换
                ll temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

void solve() {
    if (!(cin >> n)) return;

    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }

    bubble_sort();

    for (ll i = 0; i < n; i++) {
        cout << a[i] << "\n"; // 题面要求每个数占一行
    }
}

int main() {
    solve();
    return 0;
}

复杂度

  • 时间复杂度:O(n2)O(n^2)。冒泡排序包含两层循环,外层循环执行 n−1n-1 次,内层循环最多执行 n−1n-1 次,总的比较和交换次数在最坏情况下为 n(n−1)2\frac{n(n-1)}{2},因此时间复杂度为 O(n2)O(n^2)。本题中 n≤20n \le 20,最多只需计算数百次,能够极快地通过。
  • 空间复杂度:O(n)O(n)。需要一个长度为 nn 的数组来存储输入的数字进行排序,在 C++ 和 Python 中占用的额外空间复杂度均为 O(n)O(n)。

总结

  • 严格遵守题意:本题在题面末尾和标题中均显式要求「冒泡排序」,这是硬约束,代码必须是显式冒泡,不得用 std::sort 或 sorted()。
  • 判据的教训(假阴性):按常规的判据利用正则表达式 (利用|循环|递归|不使用|请用|for 循环|while|必须用) 在题面中命中数为 0,容易被判断为「不限制解法」。但标题和末尾括号的「(冒泡排序)」明示了解法,所以存在假阴性,有疑问时必须以题面真实措辞与标题为准做人工判断。
  • 闸门盲区(实测):本题验证中如果用 std::sort(a, a + n, greater<ll>()) 代替冒泡排序,在 10 个测试点下输出逐字节 100% 相同,输出比对类闸门无法发现「偷用库排序」。本题只能靠结构性验证来区分算法。
  • 用计数当算法指纹(结构性验证):
    • 比较次数 = n(n−1)/2n(n-1)/2:精确吻合测试点(如 0, 1, 10, 6, 55, 120, 190...),并在 200 组随机数据中 0 异常,证明程序没有提前退出且内层收缩正确。
    • 交换次数 ≡\equiv 逆序对数:在所有测试点均精确相等,说明每次只交换相邻逆序对,从而排除了选择排序或查表法。
    • V5 反向比较扰动:将 < 颠倒后,样例输出变为完全相反的升序排列。
    • 少跑一趟扰动:让外层少跑一次后,未排好序,输出产生变化,判据「前两位逆序   ⟺  \iff 输出变化」在 300 组随机数据上 300/300 命中。
  • 边界条件:
    • n=1n=1:如测试点 problem1.in,直接不执行循环返回。
    • 全相等点:数据中包含 problem9.in(全 0)与 problem10.in(全 999)这样的完全相等的数据。程序中相等元素不发生交换,结果正确且状态不变。
  • 稳定性:冒泡排序是稳定的,相等不交换;但由于本题中相等的数值本身不可区分,因此稳定性对最终答案无影响。
  • 输出格式:经 od -c 核实,每个数字单独占一行,末尾有单独的 \n,无多余的行尾空格或 \r。
  • 验证强度摘要:
    • 异源验证 (V6):使用 sorted(reverse=True) 生成真值,穷举 340 组(n≤4n \le 4且值 ∈[0,3]\in [0,3])+ 300 组随机数据 + 9 组边界(含 n=1n=1/n=20n=20/全 0/全 999/全 5/严格递增/严格递减/0 与 999),合计 649 组数据,0 分歧。
    • V2 字面量非硬编码:源码中去注释后的常数字面量(如 {0, 1, 25} / {0, 1})均不包含答案值。