我看到这个问题是编程面试书，在这里我简化了问题。
假设你有一个长度为A的数组n，你也有一个长度为P的排列数组n。您的方法将返回一个数组，其中A的元素将出现在P中指定索引的顺序中。
快速示例：您的方法需要A = [a, b, c, d, e]和P = [4, 3, 2, 0, 1]。那么它将返回[e, d, c, a, b]。您只能使用常量空间（即您不能分配另一个数组，这需要O(n)空间）。
想法？
有一个简单的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, -1, 2, -1, -1]，这表示只有第二个可能不在正确的位置，并且进一步的步骤将确保它在正确的位置并终止算法;-n - 1：P变为[-5, -4, 2, -1, -2]，可以在O（n）中简单地恢复。又一个不必要的答案！这个明确地保留了排列数组P，这对我的情况是必要的，但牺牲了成本。此外，这不需要跟踪正确放置的元素。我知道之前的答案提供了O(N)解决方案，所以我想这个只是为了娱乐！
我们得到最好的案例复杂性O(N)，最坏情况O(N^2)和平均情况O(NlogN)。对于大型阵列（N~10000或更大），平均情况基本上是O(N)。
这是Java中的核心算法（我的意思是伪代码*咳嗽咳嗽*）
int ind=0;
float temp=0;
for(int i=0; i<(n-1); i++){
// get next index
ind = P[i];
while(ind<i)
ind = P[ind];
// swap elements in array
temp = A[i];
A[i] = A[ind];
A[ind] = temp;
}
以下是运行算法的示例（类似于以前的答案）：
设A = [a，b，c，d，e]
和P = [2,4,3,0,1]
然后预期= [c，e，d，a，b]
i=0: [a, b, c, d, e] // (ind=P[0]=2)>=0 no while loop, swap A[0]<->A[2]
^ ^
i=1: [c, b, a, d, e] // (ind=P[1]=4)>=1 no while loop, swap A[1]<->A[4]
^ ^
i=2: [c, e, a, d, b] // (ind=P[2]=3)>=2 no while loop, swap A[2]<->A[3]
^ ^
i=3a: [c, e, d, a, b] // (ind=P[3]=0)<3 uh-oh! enter while loop...
^
i=3b: [c, e, d, a, b] // loop iteration: ind<-P[0]. now have (ind=2)<3
? ^
i=3c: [c, e, d, a, b] // loop iteration: ind<-P[2]. now have (ind=3)>=3
? ^
i=3d: [c, e, d, a, b] // good index found. Swap A[3]<->A[3]
^
done.
对于任何指数while，该算法可以在该j<i循环中反弹，在i迭代期间最多为ith次。在最坏的情况下（我认为！）外部for循环的每次迭代都会导致来自i循环的while额外赋值，所以我们有一个算术系列事情正在进行，这将为复杂性添加N^2因子！运行这个N范围并平均while循环所需的“额外”赋值的数量（平均每个N的许多排列，即），强烈暗示我的平均情况是O(NlogN)。
谢谢！
只是一个简单的例子C / C ++代码添加到自要为的答案。评论中不允许使用代码，所以作为答案，抱歉：
for (int i = 0; i < count; ++i)
{
// Skip to the next non-processed item
if (destinations[i] < 0)
continue;
int currentPosition = i;
// destinations[X] = Y means "an item on position Y should be at position X"
// So we should move an item that is now at position X somewhere
// else - swap it with item on position Y. Then we have a right
// item on position X, but the original X-item now on position Y,
// maybe should be occupied by someone else (an item Z). So we
// check destinations[Y] = Z and move the X-item further until we got
// destinations[?] = X which mean that on position ? should be an item
// from position X - which is exactly the X-item we've been kicking
// around all this time. Loop closed.
//
// Each permutation has one or more such loops, they obvisouly
// don't intersect, so we may mark each processed position as such
// and once the loop is over go further down by an array from
// position X searching for a non-marked item to start a new loop.
while (destinations[currentPosition] != i)
{
const int target = destinations[currentPosition];
std::swap(items[currentPosition], items[target]);
destinations[currentPosition] = -1 - target;
currentPosition = target;
}
// Mark last current position as swapped before moving on
destinations[currentPosition] = -1 - destinations[currentPosition];
}
for (int i = 0; i < count; ++i)
destinations[i] = -1 - destinations[i];
（对于C - 用其他东西替换std :: swap）
因此，您可以将所需元素放在数组的前面，同时在下一个迭代步骤中处理大小（n-1）的剩余数组。
需要相应地调整置换阵列以反映阵列的尺寸减小。也就是说，如果放置在前面的元素位于“X”位置，则需要在置换表中将所有大于或等于X的索引减1。
就你的例子而言：
array permutation -> adjusted permutation
A = {[a b c d e]} [4 3 2 0 1]
A1 = { e [a b c d]} [3 2 0 1] -> [3 2 0 1] (decrease all indexes >= 4)
A2 = { e d [a b c]} [2 0 1] -> [2 0 1] (decrease all indexes >= 3)
A3 = { e d c [a b]} [0 1] -> [0 1] (decrease all indexes >= 2)
A4 = { e d c a [b]} [1] -> [0] (decrease all indexes >= 0)
另一个例子：
A0 = {[a b c d e]} [0 2 4 3 1]
A1 = { a [b c d e]} [2 4 3 1] -> [1 3 2 0] (decrease all indexes >= 0)
A2 = { a c [b d e]} [3 2 0] -> [2 1 0] (decrease all indexes >= 2)
A3 = { a c e [b d]} [1 0] -> [1 0] (decrease all indexes >= 2)
A4 = { a c e d [b]} [0] -> [0] (decrease all indexes >= 1)
该算法尽管不是最快的，但是在保持跟踪元素的初始顺序的同时避免了额外的内存分配。
这里有一个更清晰的版本，它接受一个接受索引的swapElements函数，例如std::swap(Item[cycle], Item[P[cycle]])$本质上它贯穿所有元素并且如果它们还没有被访问则遵循循环。我们也可以将循环中的第一个元素与上面的其他元素进行比较，而不是第二次检查!visited[P[cycle]]。
bool visited[n] = {0};
for (int i = 0; i < n; i++) {
int cycle = i;
while(! visited[cycle] && ! visited[P[cycle]]) {
swapElements(cycle,P[cycle]);
visited[cycle]=true;
cycle = P[cycle];
}
}
@RinRisson has given the only completely correct answer so far!每个其他答案都需要额外的存储空间 - O（n）堆栈空间，或者假设排列P方便地存储在O（n）未使用但可变的符号位附近，或者其他什么。
这是RinRisson用C ++编写的正确答案。这通过了我抛出的每一个测试，包括对0到11长度的每个可能排列的详尽测试。
请注意，您甚至不需要实现排列;我们可以将它视为完全黑盒功能OldIndex -> NewIndex：
template<class RandomIt, class F>
void permute(RandomIt first, RandomIt last, const F& p)
{
using IndexType = std::decay_t<decltype(p(0))>;
IndexType n = last - first;
for (IndexType i = 0; i + 1 < n; ++i) {
IndexType ind = p(i);
while (ind < i) {
ind = p(ind);
}
using std::swap;
swap(*(first + i), *(first + ind));
}
}
或者在顶部打一个更多的STL-ish接口：
template<class RandomIt, class ForwardIt>
void permute(RandomIt first, RandomIt last, ForwardIt pfirst, ForwardIt plast)
{
assert(std::distance(first, last) == std::distance(pfirst, plast));
permute(first, last, [&](auto i) { return *std::next(pfirst, i); });
}
我同意这里的许多解决方案，但下面是一个非常短的代码片段，在整个排列周期中置换：
def _swap(a, i, j):
a[i], a[j] = a[j], a[i]
def apply_permutation(a, p):
idx = 0
while p[idx] != 0:
_swap(a, idx, p[idx])
idx = p[idx]
所以下面的代码片段
a = list(range(4))
p = [1, 3, 2, 0]
apply_permutation(a, p)
print(a)
输出[2,4,3,1]