荷兰国旗的平均交换次数

Question

我只想知道如何获得荷兰国旗两种颜色的平均交换次数。排序正数和负数而不是颜色。我假设负数等于正数并且数组的数字是随机配置的，我不确定我的假设是否正确。

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

谢谢。

Answer 1

如果正负分布均匀，则第一个元素为正的概率为1/2。第一次迭代后，数组缩短了一个元素，子数组的分布仍然是均匀的（移动一个元素是中性操作）。

在子数组为空之前正好有 n 次迭代，因此平均交换次数为 n/2。更准确地说，交换次数遵循参数为 1/2、n 的二项式定律（这是伯努利方案）。