通过三次比较与交换,将三个整数从大到小排序输出。
OJ: roj
题目 ID: 5055
难度:入门
标签:排序分支结构
创建: 2026-10-09 01:03
更新: 2026-10-09 01:03
形式化题目
输入三个整数
数据范围:
题目未明确指定数据范围。经实测,三个整数的值域包含
正解
思路
本题要求将三个数从大到小排序。作为分支结构的经典练习题,我们可以通过两两比较并交换变量的值来实现:
假设三个变量分别为
- 首先比较
和 ,如果 ,则交换它们。此时一定有 。 - 接着比较
和 ,如果 ,则交换它们。由于上一步已保证 ,且本次交换后 ,因此 现在成为了三者中的最大值。 - 最后比较
和 ,如果 ,则交换它们。此时保证了 。
经过以上三次比较和交换,三个变量
代码
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-09 00:41
# update_at: 2026-10-09 00:41
import sys
def solve() -> None:
"""读入三个整数,三次比较交换排成降序,单空格分隔输出。"""
# 题面只说「按从大到小的顺序输出」,未指定实现手段(关键词/括号/标题三步判据全空),
# 故不调用内置 sorted,保留与 C++ 侧同阶的三次比较交换。
# 数据含 32 位极值(如三个 -2147483648):这里只做比较与赋值,未取反/取绝对值,无溢出风险。
data = iter(map(int, sys.stdin.buffer.read().split()))
a, b, c = next(data), next(data), next(data)
if a < b:
a, b = b, a # 先保证 a >= b
if a < c:
a, c = c, a # 再保证 a >= c,此时 a 已是三者最大
if b < c:
b, c = c, b # 最后保证 b >= c
print(a, b, c) # 单空格分隔、行末换行(实测 .out 无行尾空格)
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-09 00:41
* update_at: 2026-10-09 00:41
*/
// 一本通 5055《【例3.3】三个数》
// 题面只要求「按从大到小的顺序输出」,未指定实现手段,故用三次比较交换。
// 数据里含 32 位极值(problem1 三个 -2147483648、problem2 三个 2147483647),
// 实现全程只做比较与赋值,不做取反/取绝对值/求和,因此用 int 也不会溢出;
// 这里默认用 ll 存题目数据,彻底规避边界风险。
#include <iostream>
using namespace std;
typedef long long ll;
ll a, b, c; // 输入的三个整数
// 三次比较交换,把 a、b、c 排成降序 a >= b >= c。
void solve() {
if (a < b) { // 先保证 a >= b
ll temp = a;
a = b;
b = temp;
}
if (a < c) { // 再保证 a >= c,此时 a 已是三者最大
ll temp = a;
a = c;
c = temp;
}
if (b < c) { // 最后保证 b >= c
ll temp = b;
b = c;
c = temp;
}
// 单空格分隔、行末换行(实测 .out 无行尾空格)
cout << a << " " << b << " " << c << "\n";
}
int main() {
if (!(cin >> a >> b >> c)) return 0; // 无输入时静默退出
solve();
return 0;
}复杂度
- 时间复杂度:
。只进行了固定 3 次比较和至多 3 次交换操作,时间复杂度为常数级别。 - 空间复杂度:
。仅使用了常数个变量存储输入的值。
总结
- 算法与复杂度:采用三次比较与交换的方法,将三个变量排成降序后输出,各数间单空格分隔。算法的时间、空间复杂度均为
。 - 数据范围与极值:本题的数据中包含了 32 位有符号整型的极值,例如测试点
p1的输入是三个INT_MIN(-2147483648),p2的输入是三个INT_MAX(2147483647)。这些极值恰好落在 32 位带符号整型(如int)的取值范围内。 - UBSan 实证与
abs(INT_MIN)反证:- 由于算法全程只做比较与赋值,不涉及取反(如
-x)、取绝对值(如abs(x))或求和/差,因此纯int版实测跑全部 10 点 10/10 逐字节一致,且 UBSan 无任何报错(实现无 UB)。 - 若在实现中误用了
abs或对负极值取反,则会触发未定义行为。例如针对p1里的-2147483648,求其绝对值会报错:UBSan: runtime error: negation of -2147483648 cannot be represented in type 'int'。 - 为防患于未然,代码中采用
long long(ll) 来存储变量,这是项目的一般规范与稳妥选择,而不是为了修 bug。
- 由于算法全程只做比较与赋值,不涉及取反(如
- 算法选择:通过对题面内容的机械判定(关键词匹配、括号注释、题面前置说明),三步判据全部为空,这意味着题面并未硬性指定具体实现手段(如不能使用
std::sort等)。保留「三次比较交换」的做法更多是为了贴合教学上的风格,而非硬约束。 - 输出格式:各整数间采用单空格分隔,行尾无空格,末尾为单换行。
- 验证强度摘要:通过真实 10 个数据点及穷举小规模极值/反事实验证(如修改为升序验证),本实现通过验证。
- 跨语言语义一致性清单:
- 类型转换:无风险
- 溢出:本题数据虽达到 32 位整型极值,但在当前“仅比较赋值”且默认
ll接收的逻辑下无溢出;若盲目使用abs等函数处理INT_MIN会导致 UB 溢出。 - 整除/取模:无(不涉及)
- 浮点格式化:无(纯整数题)
- 排序稳定性 / 字典序:无风险(直接基于值判断,且不区分相等的键值对相对顺序)