如何推导给定单趟冒泡算法的平均交换次数公式？

算法行为回顾 #

你提供的算法是对数组进行一次从左到右的相邻元素遍历：依次比较每对相邻元素a[i-1]和a[i]，若逆序则交换，最终将数组的最大元素移至末尾。我们需要推导该算法在随机排列的n元素数组上的平均交换次数。

推导过程 #

1. 定义指示变量 #

对每个遍历位置i（1 ≤ i ≤ n-1），定义指示变量X_i：

• X_i = 1：处理第i对相邻元素（a[i-1]和a[i]）时发生交换
• X_i = 0：未发生交换

总交换次数X = X_1 + X_2 + ... + X_{n-1}，根据线性期望性质，平均交换次数为E[X] = E[X_1] + E[X_2] + ... + E[X_{n-1}]。

2. 计算单个指示变量的期望E[X_i] #

观察算法执行过程：

• 处理第i对之前，仅遍历了前i-1对元素，不会触及位置i的元素，因此a[i]始终是原数组的第i个元素。
• 处理前i-1对的过程，等价于对前i个元素执行一次相同的遍历，最终会将前i个元素中的最大元素移至位置i-1。

交换发生的条件是：前i个元素的最大元素 > 原数组的a[i]。在随机排列中，前i+1个元素里每个元素成为最大值的概率均等，因此a[i]是前i+1个元素最大值的概率为1/(i+1)。

由此可得：

E[X_i] = P(前i个元素的最大元素 > a[i]) = 1 - 1/(i+1) = i/(i+1)

3. 计算总期望 #

将所有E[X_i]求和：

E[X] = Σ（i=1到n-1）i/(i+1)

将i/(i+1)改写为1 - 1/(i+1)，拆分求和项：

E[X] = Σ（i=1到n-1）1 - Σ（i=1到n-1）1/(i+1)

第一个求和项结果为n-1；第二个求和项等价于Σ（k=2到n）1/k，即调和数H_n - 1（H_n为第n个调和数，H_n = 1 + 1/2 + 1/3 + ... + 1/n）。

代入后化简：

E[X] = (n-1) - (H_n - 1) = n - H_n

最终结论 #

该算法的平均交换次数公式为：

平均交换次数 = n - H_n

其中H_n是第n个调和数，H_n = Σ（k=1到n）1/k。

内容的提问来源于stack exchange，提问作者Isak Midtvedt