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