考虑一个数组。根据另一个给出元素新位置的数组来置换元素的好方法是什么（不先制作数组的副本）？
例如
int a[]={37,43,5,10}; //array to permute
int b[]={3,1,4,2}; //new position of each element
所以应该成为
{43,10,37,5}
我自然想到制作a的副本然后在新的位置重新分配它的元素。但有没有办法在不制作阵列副本的情况下（即更简单的方式）？
注意：如果可能，执行此操作的方法不应使用特定的C ++标头，而应仅使用<iostream>
最简单的答案是将a复制到b，在你去的时候摧毁b：
for (i = 0; i < B_SIZE; ++i):
b[i] = a[b[i] - 1];
然后，如果必须，只需将b复制回a：
for (i = 0; i < B_SIZE; ++i):
a[i] = b[i];
由于a和b都是int数组，因此你不会消耗任何多余的内存。你在a中以正确的值结束，而不使用比给你的更多的内存。这不是最大效率（虽然它是O（n）），但它是最简单的理解。
它可以在O（n）时间内用O（1）额外存储器完成，通过一次处理一个置换数组的周期。
注意：这种方法比这个特定设置需要的更复杂（a和b都是int数组），但它有一些好处：
a可以是字符串数组）。b中的原始值，即置换数组。考虑最初的例子：
int a[] = {37, 43, 5, 10}; // array to permute
int b[] = { 3, 1, 4, 2}; // new position of each element
数组b表示我们想要进行以下分配链：
a[1] <-- a[3] <-- a[4] <-- a[2] <-- a[1]。
问题是，在最后一次任务中，我们不再能够访问a[1]（它已被替换为a[3]）。
但是，起始元素的原始值可以保存在辅助变量中，这样我们就可以在关闭循环时使用它（保证当我们关闭循环时，我们将精确到达我们开始的元素 - 否则对于某些i！= j），某些元素可以多种方式到达，即我们有b [i] = b [j]）。
通常，置换可以包含多个循环。处理完一个循环后，我们需要从一个尚未更新的元素开始（即它不是到目前为止处理的循环的一部分）。
因此，我们需要知道到目前为止哪些元素未被处理。
一种可能的方法是临时修改置换矢量b，以便跟踪哪些元素被更新，例如，在更新b中的元素时，否定a中相应位置的值。这样做的好处是，最后，我们可以遍历b的所有元素并恢复初始值（通过再次否定所有元素）。
以下是先前想法的实现。
int main() {
int a[] = {11, 22, 33, 44};
int b[] = { 2, 1, 4, 3};
int aux, crtIdx, nxtIdx;
int n = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < n; i++) {
// check whether the i'th element
// was already processed
if (b[i] < 0) {
continue;
}
// start processing of a new cycle;
// backup the first value to aux
aux = a[i];
crtIdx = i;
nxtIdx = b[i] - 1;
// advance along the cycle until we reach
// again the first element
while (nxtIdx != i) {
a[crtIdx] = a[nxtIdx];
// use the b array to mark that the
// element at crtIdx was updated
b[crtIdx] = -b[crtIdx];
crtIdx = nxtIdx;
nxtIdx = b[nxtIdx] - 1;
}
// finalize the cycle using the aux variable
a[crtIdx] = aux;
b[crtIdx] = -b[crtIdx];
}
// restore the original values of b[i]
for (int i = 0; i < n; i++) {
b[i] = -b[i];
}
}
注意：虽然代码包含两个嵌套循环，但时间复杂度为O（n）。这可以通过考虑每个元素只更新一次的事实来看出（如果我们到达已经处理的元素，则外部循环立即继续）。
我将在此处显示算法执行的主要步骤，使用此示例：
a = {11, 22, 33, 44}
b = { 2, 1, 4, 3}
步骤1.我们查看第一个元素（请从代码中查看for上的外部i循环）。第一个元素不是已处理循环的一部分，因此我们开始处理新循环。我们通过在aux中存储此元素的初始值来实现。
a = {11, 22, 33, 44}
b = { 2, 1, 4, 3}
aux = 11
步骤2.我们沿着这个循环，更新元素，将它们标记为更新（通过否定b数组中的相应元素），直到我们再次到达第一个元素。
a = {22, 22, 33, 44}
b = {-2, 1, 4, 3}
aux = 11
步骤3.我们再次到达循环的第一个元素，并且需要其初始值以更新循环的最后一个元素。这是我们使用辅助变量的地方。以这种方式，第一个循环被完全处理。
a = {22, 11, 33, 44}
b = {-2, -1, 4, 3}
aux = 11
步骤4.我们继续外循环（for在i上）。我们看到第二个元素已经处理过了（因为b[1]是负数），因此我们不会在这里开始一个新的循环。我们继续，并在第三个元素（尚未处理）开始一个新的循环。
现在我们可以重复使用相同的aux变量来备份此循环的第一个元素（我们不再需要保留第一个循环中的值，因为该循环已完全解析）。
a = {22, 11, 33, 44}
b = {-2, -1, 4, 3}
aux = 33
步骤5.以与前面步骤中描述的类似方式执行第二周期的处理，结果如下：
a = {22, 11, 44, 33}
b = {-2, -1, -4, -3}
aux = 33
步骤6.继续i上的循环，并且没有找到未处理的元素。现在，我们知道所有元素都已处理，我们可以否定b中的每个元素以恢复原始值。
a = {22, 11, 44, 33}
b = { 2, 1, 4, 3}
如果要避免复制数组，通常意味着限制自己进行交换。
如果我们使用掉期来对b[]进行排序，并对a[]使用相同的掉期，那么a[]最终将根据b[]的值进行置换。
我将逐步介绍下面的算法。为简单起见，我开始在1处进行数组计数，尽管在C数组中计数从0开始。您必须在代码中进行调整。
a[]={37, 43, 5, 10} //array to permute
b[]={3, 1, 4, 2} //new position of each element
i = 1; b[i] = 3
swap(a[1], a[3]); a[] = {5, 43, 37, 10}
swap(b[1], b[3]); b[] = {4, 1, 3, 2}
i = 1; b[i] = 4
swap(a[1], a[4]); a[] = {10, 43, 37, 5}
swap(b[1], b[4]); b[] = {2, 1, 3, 4}
i = 1; b[i] = 2
swap(a[1], a[2]); a[] = {43, 10, 37, 5}
swap(b[1], b[2]); b[] = {1, 2, 3, 4}
i = 1; b[i] = 1
++i
i = 2; b[i] = 2
++i
i = 3; b[i] = 3
++i
i = 4; b[i] = 4
++i
i = 5; i > 4
DONE
请注意我们如何在那里通过b[]。考虑一下b[]={2, 1, 4, 3}的情况
a[] = {37, 43, 5, 10}
b[] = {2, 1, 4, 3}
i = 1; b[i] = 2
swap(a[1], a[2]); a[] = {43, 37, 5, 10}
swap(b[1], b[2]); b[] = {1, 2, 4, 3}
i = 1; b[i] = 1
++i
i = 2; b[i] = 2
++i
i = 3; b[i] = 4
swap(a[3], a[4]); a[] = {43, 37, 10, 5}
swap(b[3], b[4]); b[] = {1, 2, 3, 4}
i = 3; b[i] = 3
++i
i = 4; b[i] = 4
++i
i = 5; i > 4
DONE
每次交换时，数组中的一个元素最终位于正确的位置，这意味着我们最多执行N个交换。