algorithm - 荷兰国旗的平均互换次数

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（这是一个伯努利方案）。