思路与算法

按题目要求执行冒泡排序。每轮从左向右比较相邻两个数，如果左数小于右数，就交换；这样较小的数逐渐向右移动。完成一轮后，最小的剩余数已经位于未排序部分的末尾，下一轮可以少比较一项。

正确性说明

在一轮扫描中，每次相邻交换都把较小者移到右侧，所以扫描结束时，未排序前缀的最小值到达末尾。该值不大于前缀内任何其他值，固定在降序排列的正确位置。逐轮缩短前缀，最终所有位置满足从大到小，交换不改变元素集合及重复次数。

复杂度

比较次数为(n-1)+(n-2)+…+1，时间O(n²)；输入及逐行输出O(n)，已包含。数组空间O(n)，数组分配与初始化O(n)，交换只用常量额外空间。n≤20。

易错点

降序应在a[j]<a[j+1]时交换。重复值不需要删除，每个整数单独一行，不是空格连成一行。0及999都属于允许范围。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j + 1 < n - i; ++j)
            if (a[j] < a[j + 1])
                swap(a[j], a[j + 1]);
    for (int x : a)
        cout << x << '\n';
}