algorithm - 向量的排列

Question

假设我有一个向量：

 0  1  2  3  4  5
[45,89,22,31,23,76]

及其索引的排列：

[5,3,2,1,0,4]

有没有一种有效的方法可以根据排列得到：

[76,31,22,89,45,23]

最多使用 O(1) 额外空间？

Answer 1

是的。从最左边的位置开始，我们通过将元素与该位置 i 处的（其他）错位元素交换，将元素放置在其正确的位置i。这是我们需要 O(1) 额外空间的地方。我们不断交换元素对，直到该位置的元素正确为止。只有这样我们才能进入下一个位置并做同样的事情。

例子：

[5 3 2 1 0 4] 初始状态

[4 3 2 1 0 5] 交换 (5,4)，现在 5 位置正确，但 4 仍然错误

[0 3 2 1 4 5] 交换了 (4,0)，现在 4 和 0 都在正确的位置，移动到下一个位置

[0 1 2 3 4 5] 交换 (3,1)，现在 1 和 3 都在正确的位置，移动到下一个位置

[0 1 2 3 4 5] 所有元素都在正确的位置，结束。

注意：

由于每个交换操作都会将至少一个（两个）元素放在正确的位置，因此我们总共需要不超过 N 个这样的交换。

Answer 2

Zach 的解决方案非常好。

不过，我想知道为什么需要排序。如果您有索引的排列，请将这些值用作指向旧数组的指针。

这可以消除首先对数组进行排序的需要。这不是可以在所有情况下使用的解决方案，但在大多数情况下都可以正常工作。

例如：

a = [45,89,22,31,23,76];
b = [5,3,2,1,0,4]

现在，如果您想遍历 a 中的值，可以执行以下操作（伪代码）：

for i=0 to 4
{
    process(a[i]);
}

如果要以新顺序遍历值，请执行以下操作：

for i=0 to 4
{
    process(a[b[i]]);
}

如前所述，这种解决方案在许多情况下可能就足够了，但在其他一些情况下可能就不够了。对于其他情况，您可以使用 Zach 的解决方案。但是对于可以使用此解决方案的情况，它会更好，因为根本不需要排序。