c++ - 排序排列的算法

Question

我遇到了这个问题:

---

给定 {0,1,2,...,n-1} 的排列 P
(这里 n = P.length)

解释为什么下面的算法按递增顺序对排列进行排序，并给出最坏情况(伪代码)

PermutationSort(P)
    for i = 0 to P.length - 1
        while(P[i] != i)
            t = P[i]
            exchange P[i] with P[t]

(C++代码)

void PermutationSort(int P[], int len)
{
    for(int i = 0; i < len; i++)
        while(P[i] != i)
        {
            int tmp;
            tmp = P[i];
            P[i] = P[tmp];
            P[tmp] = tmp;
        }
}

---

我完全不知道为什么它对排列 P 进行排序。

我已经在这个问题上坐了一整天了，但我仍然不明白为什么它会对排列进行排序。

“将 P[i] 与 P[P[i]] 交换”的作用是什么？为什么我们最终会得到 P[i] = i 从而终止内部循环？

感谢任何提示或帮助。

Answer 1

首先，请注意，如果您从任意元素 k 开始，并重复应用置换P 以获得类似于 (k → P(k) → P(P(k)) → P(P(P(k))) → ...)，你会(因为总排列 P 中的元素数量是有限的，并且排列永远不会将两个输入映射到相同的输出)最终返回到 k。 cycle元素 (k →P(k) → P(P(k )) → ... → k) 称为 orbit k 在 P 下，并且排列的每个元素恰好属于一个这样的循环。

现在，让我们看看您的算法的内部循环对包含元素 i 的循环做了什么。

如果 P(i ) = i，即如果这个元素已经在它所属的位置，那么内层循环什么也不做外循环移动到下一个元素。但是，如果 P(i ) ≠ i，则内循环设置 t = P(i )，然后修改置换 P 以交换 P(i ) 和 P(t ).

交换后，P(t )的新值是P的旧值(i )，即 t。因此，元素 t 现在已正确排序，而 P(i ) 现在包含 P 的旧值(t ) = P(P(i ))，即循环中的(前)下一个元素.如果这是i，那么循环中就没有剩余的元素了，内循环结束；否则，包含 i 的循环缩减了一个元素，并重复内部循环。

因此，在内部循环的末尾，所有曾经与 i 属于同一循环的元素(包括 i 本身)都已移至它们的正确位置，因此从循环中删除，而其余的排列没有改变。

由于外层循环遍历排列中的每个元素，因此也保证至少访问每个循环一次。当然，我们正在修改内层循环中的排列，但这没关系，因为内层循环永远不会创建新的循环(不止一个元素)；它只能分解现有的。

因此，当原始排列中的每个循环第一次被外循环访问时，内循环排序并打散该循环；在对同一个原始循环的后续访问中，该循环已经排序，因此内部循环什么都不做。

这种观察还应该允许您限制内循环可以执行的次数，从而确定算法的时间复杂度。