难度：基础。题目原型为洛谷 U236091（私题，题面自定）。本题的考点是在冒泡排序过程中统计交换次数：排序的中间过程本身携带信息，把每次相邻交换累计起来就是答案。

目标

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

• 在冒泡排序的交换处插入计数器，统计总交换次数；
• 说明升序数组交换 0 次、降序数组交换 n(n-1)/2 次的原因；
• 理解「交换次数」与序列「逆序程度」之间的联系。

前置知识

• 10.3 冒泡排序的两层循环与相邻交换；
• 相邻交换计数只需在 swap 发生时累加。

题目

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

输入格式

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

输出格式

一行一个整数，表示冒泡排序过程中相邻交换的总次数。

数据范围

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

样例

样例输入

5
3 1 4 1 5

样例输出

3

样例解释

序列 3 1 4 1 5 冒泡排序共发生 3 次相邻交换：3↔1、4↔1（前一个 1）、3↔1（交换后 3 与 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-11-bubble-sort-basic
pnpm lab:score -- labs/chapter-10/exercise/E-10-11-bubble-sort-basic

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

完成清单

• 样例输出与题目一致
• 升序（0 次）、降序（最多 n(n-1)/2 次）、含重复值三种情况都通过
• 能说出为什么降序数组交换次数正好是 n(n-1)/2

思考题

1. 冒泡排序的交换次数等于序列中「逆序对」的个数吗？为什么？
2. 如果某趟一趟下来一次交换都没有发生，交换次数还会计入吗？能否借此提前结束循环？

题解

点击查看题解

思路

冒泡排序的每一次相邻交换，本质上消除了一个「相邻逆序」。因此只需在 swap(a[j], a[j+1]) 发生时让计数器 cnt 加一即可：

• 升序数组没有任何相邻逆序，cnt = 0；
• 降序数组任意两元素都逆序，交换次数为 n(n-1)/2。

外层跑 n - 1 趟、内层比较到 n - 1 - i 的普通冒泡模板就能保证排序完成，同时累计交换次数。

复杂度分析

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