排序排列的算法

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 进行排序。

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

"exchange P[i] with P[P[i]]" 做了什么以及为什么我们最终会得到 P[i] = i 然后终止内部循环？

感谢任何提示或帮助。

Answer 1

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

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

If P(i ) = i，即如果这个元素已经在它属于，然后内循环什么也不做，外循环移动到下一个元素。然而，如果 P(i ) ≠ i，则内循环设置 t = P(i )，然后修改排列P交换P(i ) 和 P(t ).

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

因此，在内部循环的末尾，与 i 属于同一循环的所有元素（包括 i 本身）已经被移动到正确的位置，因此从循环中移除，而其余的排列没有改变。

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

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

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

排序排列的算法

Algorithm that sorts a permutation

c++

sorting

algorithm

permutation