难度：入门。题目原型为洛谷 U230342 冒泡排序模板。本题的考点是手写冒泡排序：把「相邻两两比较、大的往后换」这件事写成两层循环，是排序章节最基础的模板。

目标

完成本题后，你应该能够：

• 写对冒泡排序的两层循环：外层「第几趟」、内层「比较到哪为止」；
• 说明为什么每趟结束后当前未排序部分的最大值会「冒泡」到末尾；
• 独立默写冒泡排序模板，并正确输出排序结果。

前置知识

• 10.3 冒泡排序的基本思想：相邻元素两两比较，逆序就交换；
• 数组下标的循环边界。

题目

读入 n 和 n 个整数，用冒泡排序把它们从小到大排序后，按空格分隔输出。

输入格式

• 第一行一个整数 n；
• 第二行 n 个整数，表示待排序的数组 a。

输出格式

一行 n 个整数，从小到大排序后的结果，两两之间用一个空格分隔。

数据范围

项目	范围
数组长度 n	1 ≤ n ≤ 10⁴
元素值	−10⁹ ≤ a[i] ≤ 10⁹

样例

样例输入

5
3 1 4 1 5

样例输出

1 1 3 4 5

样例解释

序列 3 1 4 1 5 冒泡排序后为 1 1 3 4 5。注意两个 1 都要保留。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用等价的 pnpm 入口：

pnpm lab:run -- labs/chapter-10/exercise/E-10-10-bubble-sort-template
pnpm lab:score -- labs/chapter-10/exercise/E-10-10-bubble-sort-template

标准输出参与判题，调试信息请写入标准错误。

完成清单

• 样例输出与题目一致
• 升序、降序、含重复值、含负数四种情况都通过
• 能说出内层循环上界 n - 1 - i 的含义

思考题

1. 为什么内层循环的右边界可以写成 n - 1 - i 而不是每次都到 n - 1？去掉 - i 会出错吗？
2. 如果某趟没有发生任何交换，说明什么？如何利用这一点提前结束排序？

题解

点击查看题解

思路

冒泡排序共进行 n - 1 趟。第 i 趟（从 0 开始）把当前未排序部分 [0, n - 1 - i] 中的最大值，通过相邻交换逐步「冒泡」到位置 n - 1 - i：

• 内层循环 j 从 0 到 n - 2 - i，比较 a[j] 与 a[j + 1]；
• 若 a[j] > a[j + 1]，交换两者。

一趟结束后，末尾多一个已排好的元素，下一趟内层循环就少比较一次。

复杂度分析

• 时间复杂度：最坏 O(n²)；
• 空间复杂度：O(1) 额外空间（原地排序）。