@[iii111](/user/1083478) 时间方面还是正确性方面？
by OldDriverTree @ 2023-09-19 18:20:31
$n \leq 10^4$。
by CEFqwq @ 2023-09-19 18:36:59
选择排序也可以过
by zclcsp @ 2023-09-20 14:57:33
说起来可笑（任何排序加个计数就行）
by Zhaoyixuan666 @ 2023-10-29 18:50:48
@[iii111](/user/1083478)
### 关于冒泡排序最优性的证明 (?)
在看这个证明之前，我们先来了解一下逆序数的概念(若已经知道跳过这段即可)
#### 逆序对
首先，设 $a_1, a_2, ..., a_n$ 是 1, 2, ..., n 的一个排列。
逆序对的定义：$若存在 i, j, 1 \leqslant i \leqslant j, 使得a_i < a_j, 那么, 我们称 <a_i, a_j> 为一组逆序对$。
而逆序数即是该排列中逆序对的个数，记做 $\tau(a_1a_2...a_n)$ 。
举个例子，序列 ```1 4 2 3 5```
中，逆序对有 ```<4, 2> <4, 3>``` 两组，逆序数 $\tau(14235) = 2$。
#### 证明
(在证明部分，上文对 $a_i$ 的定义仍然沿用)
在这个问题中，我们交换了相邻的两个值 $a_m, a_{m + 1}$ ，而这次交换对于不是 $<a_m, a_{m + 1}>$ 或 $<a_{m + 1}, a_m>$ 的逆序对是毫无影响的。
因此， $a_m$ 和 $a_{m + 1}$ 的交换只可能造成两种结果：
$$\begin{cases}
\tau(a_1a_2...a_n) + 1, a_m < a_{m + 1} 时\\
\tau(a_1a_2...a_n) - 1, a_m > a_{m + 1} 时
\end{cases}$$
而最终目标 $\tau(12...n) = 0$，因此，最快的方式就是每次均使 $\tau(a_1a_2...a_n)$ 减少 1 。
观察冒泡排序的式子，发现它就只有在 $a_m > a_{m + 1}$ 时才会交换，也就是说，每次交换 $\tau(a_1a_2...a_n)$ 必然会减 1 ，这说明冒泡排序的交换次数即为正确答案。
by milk2715093695 @ 2023-11-14 18:11:42
@[iii111](/user/1083478) 你谷评测姬跑得快
by Special_Tony @ 2023-11-18 14:04:02
这题本质上就是冒泡排序
by Dark_Monarch @ 2024-01-20 17:43:52