向量的排列

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

扎克的解决方案非常好。

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

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

例如：

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 的解决方案。但是对于可以使用此解决方案的情况，它更好，因为根本不需要排序。