双颜色荷兰国旗问题（正负数字排序）的平均交换次数求解咨询

嘿，咱们一步步拆解这个问题——你设定的前提（正负数量相等、数组随机排列）很清晰，先从算法逻辑入手，再算平均交换次数：

先明确算法逻辑 #

Algorithm(A[0…n-1]):
i ← 0
j ← n - 1
while i ≤ j:
if A[i] < 0:
i ← i + 1
else:
swap(A[i], A[j])
j ← j - 1

这个算法的核心是：左指针i从左往右扫，遇到负数就继续前进，遇到正数就和右指针j的元素交换，然后j左移。仔细观察会发现：每次交换都对应处理一个“错位”的正数——也就是本该在右半部分、却出现在左半部分的正数。

交换次数的本质 #

最终排序后，前n/2个位置应该全是负数，后n/2个全是正数。初始数组中，前n/2个位置里有多少个正数，就需要多少次交换——因为每个这样的正数都得被换到右边，而且每次交换刚好能完成一次“错位元素”的互换（哪怕偶尔遇到右半部分的正数，交换后i会继续处理当前位置，直到换到负数为止，但这类情况不会额外增加总交换次数，最终交换次数还是等于前半部分的正数总数）。

用指示变量算平均交换次数 #

我们用指示变量法来算期望（平均）交换次数，这是这类概率问题的常用技巧：

• 设m = n/2（因为正负数量相等，n肯定是偶数），前m个位置是最终的负数区域。
• 对前m个位置里的每个位置k（从0到m-1），定义一个指示变量X_k：如果这个位置初始是正数，X_k=1；否则X_k=0。
• 总交换次数X就是所有X_k的和——毕竟每个前半部分的正数都会触发一次交换。

根据期望的线性性质（不管变量独立与否，和的期望等于期望的和）：

E[X] = E[X₀] + E[X₁] + ... + E[X_{m-1}]

现在算单个E[X_k]：因为数组是随机排列的，每个位置出现正数的概率都是m/(2m) = 1/2（总共有m个正数，2m个位置），所以每个X_k的期望都是1/2。

总共有m个这样的变量，所以：

E[X] = m * 1/2 = m/2 = n/4

用小例子验证下 #

比如n=2（m=1）：

• 两种可能的排列：[-1, 1]（交换0次）、[1, -1]（交换1次）
• 平均交换次数：(0+1)/2 = 0.5，正好等于2/4，符合结论。

再比如n=4（m=2）：

• 所有6种符合条件的排列，交换次数分别是0、1、1、1、1、2，平均下来是6/6=1，也等于4/4，完全匹配。

最终结论 #

在你给定的前提（正负数量相等、数组随机排列）下，这个算法的平均交换次数是n/4，其中n是数组的总长度。

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