P4301 赛马游戏（【入门】）

解题思路

三匹马跑完 100 米用的秒数不同，时间越短跑得越快。题目要我们把三个秒数从小到大排好，依次对应快马、中马、慢马。

三个数排序有个简单的办法，就像排队时不停地"比一比、换一换"：

1. 先比较第一个数和第二个数，如果第一个大就交换，让第一个变得比较小；
2. 再比较第一个数和第三个数，如果第一个大就交换，这样第一个数就成了最小的；
3. 最后比较第二个数和第三个数，如果第二个大就交换，这样三个数就从小到大排好了。

这其实是最简单的冒泡排序思想：每次把"大的数"往后"冒"。

拿样例 12 7 9 来说：先比 12 和 7，交换变成 7 12 9；再比 7 和 9，不用换；最后比 12 和 9，交换变成 7 9 12，输出 7 9 12。

边界情况：如果三个数本来就排好了（比如 1 2 3），三次比较都不需要交换，照样正确；如果有相同的数（比如 5 5 3），交换后变成 3 5 5，也能正确输出。

参考代码

// 三个数从小到大排序，对应快马、中马、慢马的时间
#include <iostream>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    // 冒泡式两两比较交换，最终让 a<=b<=c
    if (a > b) { int t = a; a = b; b = t; }
    if (a > c) { int t = a; a = c; c = t; }
    if (b > c) { int t = b; b = c; c = t; }
    cout << a << " " << b << " " << c << endl;
    return 0;
}

复杂度分析

无论三个数多大，都只做固定的 3 次两两比较，所以时间复杂度是 $O(1)$。只用了三个整数变量和交换用的临时变量，额外空间复杂度也是 $O(1)$。