我看到这个问题是一个编程面试书中的问题，这里我简化了一下这个问题。
假设你有一个长度为 n 的数组 A，同时你还有一个长度为 n 的置换数组 P。你的方法将返回一个数组，其中 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所需的正确元素进行交换，每次交换后，就会有一个更多的元素处于正确的位置，然后以循环方式按照每个位置操作（使用指向^的符号交换元素）：
[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)。
您可以通过以下方式存储哪些元素已经处于正确的位置：
将P中相应的条目设置为-1，这是无法恢复的：经过上述操作后，P将变为[-1，-1，2，-1，-1]，表示只有第二个元素可能不在正确的位置上，进一步的步骤将确保它位于正确的位置并终止算法；
将P中相应的条目设置为-n - 1：P变为[-5，-4，2，-1，-2]，可以轻松地在O(n)时间内进行恢复。
e-a 和 a-b，但为什么还要交换 a-d 呢？ - ahmet alp balkan[a，b，c，d] 和 [2 3 0 1]，在交换 a＆c 后，您将检查 P [2] == 0 == 0（其中a最初是） 并且在修复 b＆d 之前是否将终止？ 我想了解您如何处理这种情况以及排列已经正确。 因为这是一个非常简短的算法，似乎可以解决问题，但我不知道您如何处理这些情况。 您能否提供伪代码？ - ahmet alp balkanb），然后修复它。然而，由于一个位置只需要一次修复，所以它通常是O(n)。 - zw324P，这对我的情况是必要的，但代价较高。此外，这种方法不需要跟踪正确放置的元素。我知道之前的答案提供了O(N)解决方案，所以我想这只是为了娱乐！O(N)，最坏情况下为 O(N^2)，平均情况下为 O(NlogN)。对于大型数组 (N~10000 或更大)，平均情况基本上等于 O(N)。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，在第ith次迭代期间最多可以反弹次。最坏情况下（我认为！）每次外层的for循环迭代都会导致来自while循环的个额外赋值，因此我们将得到一个算术级数的形式，这将为复杂度增加一个N^2的因素！然而，运行这个算法的一系列N并平均计算while循环所需的“额外”赋值数（在每个N的多个排列上进行平均），强烈提示我平均情况下的时间复杂度是O(NlogN)。@RinRisson 迄今为止，他给出了唯一完全正确的答案！ 其他答案都需要额外的存储空间——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 permute(array, perm):
for i in range(len(array)):
elem, p = array[i], perm[i]
while( p != i ):
elem, array[p] = array[p], elem
elem = array[p]
p = perm[p]
return array
因此，在下一次迭代步骤中，您可以将所需元素放在数组的前面，同时处理大小为(n-1)的剩余数组。
排列数组需要相应地调整以反映数组的减小尺寸。也就是说，如果您放在前面的元素在位置“X”被找到，则需要在排列表中减少所有大于或等于X的索引。
以您的示例为例：
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)
该算法虽然不是最快的，但仍能避免额外的内存分配，同时保持元素的初始顺序跟踪。
e [ a b c d]，这基本上需要移动元素，这是 O(n) 的操作，而你又重复执行了 n 次，因此你的算法变成了 O(n^2)。 - ahmet alp balkan这是一个简单的C/C++代码示例，补充Ziyao Wei的答案。由于评论不允许代码，所以只能作为答案发布：
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）
int的负空间来存储附加信息。 因此，它确实分配了一个“O（n）”数组，只是隐式地分配了。 它显然不适用于对负整数进行置换。 - Jan Schultke通过检查索引来追踪我们已经交换的内容。
Java，O(N) 交换，O(1) 空间：
static void swap(char[] arr, int x, int y) {
char tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
public static void main(String[] args) {
int[] intArray = new int[]{4,2,3,0,1};
char[] charArray = new char[]{'A','B','C','D','E'};
for(int i=0; i<intArray.length; i++) {
int index_to_swap = intArray[i];
// Check index if it has already been swapped before
while (index_to_swap < i) {
// trace back the index
index_to_swap = intArray[index_to_swap];
}
swap(charArray, index_to_swap, i);
}
}
这里有一个更清晰的版本，它采用了一个接受索引的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];
}
}
我同意这里的许多解决方案，但以下是一个非常简短的代码片段，可以在排列循环中进行排列：
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]
apply_permutation(a, [1, 0, 3, 2]) 将会得到错误的答案。 - Quuxplusone
O(n)的空间，这不是常数。 - Patrick Kostjens