难度：基础。题目原型为 AOJ ALDS1_2_A Bubble Sort。本题的考点是冒泡排序 + 交换计数：既要把排序后的数组完整输出，又要在排序过程中累计相邻交换次数。

目标

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

• 按题目要求的格式，先输出排序后的数组、再输出交换次数；
• 在冒泡排序过程中同步累计相邻交换次数；
• 正确使用 std::swap 完成相邻元素的交换。

前置知识

• 10.3 冒泡排序的两层循环与相邻交换；
• 数组的遍历与空格分隔输出。

题目

读入 n 和 n 个整数，用冒泡排序把它们从小到大排序。输出排序后的数组（一行），再输出冒泡排序过程中相邻交换的总次数（一行）。

输入格式

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

输出格式

• 第一行 n 个整数，排序后的数组，两两之间用一个空格分隔；
• 第二行一个整数，表示交换次数。

数据范围

项目	范围
数组长度 n	1 ≤ n ≤ 100
元素值	0 ≤ a[i] ≤ 100

样例

样例输入

5
5 3 2 4 1

样例输出

1 2 3 4 5
8

样例解释

序列 5 3 2 4 1 冒泡排序后为 1 2 3 4 5，过程中共发生 8 次相邻交换。

如何验证

先安装 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-12-bubble-sort-count
pnpm lab:score -- labs/chapter-10/exercise/E-10-12-bubble-sort-count

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

完成清单

• 样例输出与题目一致（数组行 + 次数行）
• 升序（0 次）、降序（最多 n(n-1)/2 次）、含重复值三种情况都通过
• 输出顺序正确：先数组、后交换次数

思考题

1. 如果只输出交换次数、不排序，是否还有更快的办法得到答案？
2. std::swap 与手写三变量交换相比，好处是什么？

题解

点击查看题解

思路

本题是冒泡排序的经典模板题，唯一要注意的是输出顺序：

1. 先在 swap 发生时累计 cnt，完成排序；
2. 先按空格分隔输出排序后的数组；
3. 再输出一行 cnt。

相邻交换计数只在 a[j] > a[j + 1] 成立时累加。

复杂度分析

• 时间复杂度：最坏 O(n²)；
• 空间复杂度：O(1) 额外空间。