向量的排列
假设我有一个向量：
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) 额外空间？
suppose I have a vector:
0 1 2 3 4 5
[45,89,22,31,23,76]
And a permutation of its indices:
[5,3,2,1,0,4]
Is there an efficient way to resort it according to the permutation thus obtaining:
[76,31,22,89,45,23]
Using at most O(1) additional space?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的。 从最左边的位置开始，我们将元素放在正确的位置 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 次这样的交换。
Yes. Starting from the leftmost position, we put the element there in its correct position i by swapping it with the (other) misplaced element at that position i. This is where we need the O(1) additional space. We keep swapping pairs of elements around until the element in this position is correct. Only then do we proceed to the next position and do the same thing.
Example:
[5 3 2 1 0 4] initial state
[4 3 2 1 0 5] swapped (5,4), 5 is now in the correct position, but 4 is still wrong
[0 3 2 1 4 5] swapped (4,0), now both 4 and 0 are in the correct positions, move on to next position
[0 1 2 3 4 5] swapped (3,1), now 1 and 3 are both in the correct positions, move on to next position
[0 1 2 3 4 5] all elements are in the correct positions, end.
Note:
Since each swap operation puts at least one (of the two) elements in the correct position, we need no more than N such swaps altogether.
扎克的解决方案非常好。
不过，我想知道为什么需要排序。 如果您有索引的排列，请使用这些值作为指向旧数组的指针。
这可以消除首先对数组进行排序的需要。 这不是一个适用于所有情况的解决方案，但它在大多数情况下都能正常工作。
例如：
现在，如果您想遍历 a 中的值，您可以执行类似的操作（伪代码）：
如果您想按新顺序循环遍历值，请执行以下操作：
如前所述早些时候，该解决方案在许多情况下可能足够，但在其他一些情况下可能不够。 对于其他情况，您可以使用 Zach 的解决方案。但是对于可以使用此解决方案的情况，它更好，因为根本不需要排序。
Zach's solution is very good.
Still, I was wondering why there is any need to sort. If you have the permutation of the indices, use the values as a pointer to the old array.
This may eliminate the need to sort the array in the first place. This is not a solution that can be used in all cases, but it will work fine in most cases.
For example:
Now if you want to lop through the values in a, you can do something like (pseudo-code):
If you want to loop through the values in the new order, do:
As mentioned earlier, this soluion may be sufficient in many cases, but may not in some other cases. For other cases you can use the solution by Zach.But for the cases where this solution can be used, it is better because no sorting is needed at all.