I can't believe it can sort!

eEfiuys · 2025-04-28 16:42:27 · 算法·理论

I can't believe it can sort！

对长度为 n 的排列 a 执行如下操作：

int cnt=0;
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++)
        if(a[i]>a[j])swap(a[i],a[j]),cnt++;
}

1. 证明：执行后 a 递减。

2. 设 a 在所有长度为 n 的排列中均匀随机，求交换次数的期望，即 E(cnt)。

1. 证明：

归纳可证，第一重循环执行完前 i 层后，a_i=1 且 a_1,a_2,\dots,a_i 递减。

2. 解：

设前缀 \min 序列为 b_1,b_2,\dots,b_k,1。

第一层（即第一重循环 i=1 时）操作为将 b 向右循环移位，变为 1,b_1,b_2,\dots,b_k，交换次数期望为 E(k)=H_n-1（H_n=\sum_{i=1}^{n}\frac{1}{i}）。

对 i 的操作即为从前往后枚举 a_j<a_i 并交换 a_i,a_j。因为 a_1,a_2,\dots a_{i-1} 降序，所以交换后不影响大小关系；又因为操作完 j<i 后，a_i=1，所以不会有 j>i 的操作。故操作次数为全局顺序对个数。

设 a' 为第一层操作后得到的排列。设 x 为 a 的顺序对个数，y 为 a' 的顺序对个数，z 为 y-x。则 E(y)=E(x+z)=E(x)+E(z)。

显然 E(x)=\frac{n(n-1)}{4}。

先对一个特定排列求 z 的值。设 c 为 a 删掉 b 和 1 得到的序列，p_i 为 i 在 a 中的位置。

对于 b 内部，顺序对增加了 k 个。

对于 c 内部，顺序对个数不变。

对于 b 和 c 之间，如果 p_{c_i}>p_1 则 c_i 构成的顺序对数不变；否则，设 p_{b_j}<p_{c_i}<p_{b_{j+1}}，由于 c_i 不是前缀最大值，故 c_i>b_j，在第一层操作后，有且仅有 b_j 移动到了 c_i 后面使得顺序对数减 1，以及 1 移动到了 c_i 前面使得顺序对数加 1，总变化量依然是 0。

综上所述，z=k。

所以 E(cnt)=E(k+x+z)=E(k)+E(x)+E(z)=\frac{n(n-1)}{4}+2H_n-2。