问题描述
假设我有一个向量：
0 1 2 3 4 5
[45,89,22,31,23,76]
和它的指标置换：
[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]
最多使用O（1）额外的空间？
Using at most O(1) additional space?
推荐答案
是的。从最左边的位置开始，我们把的元素的在正确的存在的位置的我用在那个位置我的（其他）放错位置的元素交换它。这是我们所需要的O（1）额外的空间。我们一直在交换元素对周围直到这个位置的元素是正确的。只有这样，我们进入下一个位置，做同样的事情。
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.
示例：
[5 3 2 1 0 4]初始状态
[5 3 2 1 0 4] initial state
[4 3 2 1 0 5]交换（5,4），5现在在正确的位置，但4仍然是错误的。
[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]互换（4,0），现在同时有4和0是在正确的位置，移动到下一个位置
[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]交换（3,1），现在1和3都在正确的位置，移动到下一个位置
[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]所有元素都在正确的位置，结束
[0 1 2 3 4 5] all elements are in the correct positions, end.
注意
由于每个交换操作所说的至少一个（两个）在正确的位置的元素，我们需要不大于N个这样的互换共
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.
这篇关于向量置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！