有一个简单的O（n ^ 2）算法，但是您可以在O（n）中执行此操作。例如：

A = [a，b，c，d，e]

P = [4，3，2，0，1]

我们可以将每个元素交换A为所需的正确元素P，每次交换之后，在正确的位置将再有一个元素，并针对每个位置以循环方式进行此操作（以^s
指向的交换元素）：

[a, b, c, d, e] <- P[0] = 4 != 0 (where a initially was), swap 0 (where a is) with 4
 ^           ^
[e, b, c, d, a] <- P[4] = 1 != 0 (where a initially was), swap 4 (where a is) with 1
    ^        ^
[e, a, c, d, b] <- P[1] = 3 != 0 (where a initially was), swap 1 (where a is) with 3
    ^     ^
[e, d, c, a, b] <- P[3] = 0 == 0 (where a initially was), finish step

经过一圈后，我们在数组中找到了下一个不在正确位置的元素，然后再次执行此操作。因此，最终您将获得所需的结果，并且由于每个位置都被触摸了恒定的时间（对于每个位置，最多执行一次操作（交换）），因此时间为O（n）。

您可以通过以下方式存储正确位置的信息：

1. 将P中的对应条目设置为-1，这是不可恢复的：完成上述操作后，P将变为[-1, -1, 2, -1, -1]，这表示只有第二个可能不在正确的位置，并且下一步将确保它在正确的位置定位并终止算法；

2. 将P中的相应条目设置为-n - 1：P变为[-5, -4, 2, -1, -2]，可以在O（n）中轻松恢复。