C++ swap/sort 算法

Question

鉴于以下情况：

Container A; //contains n data entries
vector<int> B; //indexes of A that need to be swapped
vector<int> C; // Where the entry needs to be moved to, a randomly sorted version of B
//B.size() <= A.size() - not all may be swapped
//C.size() = B.size()

swap(container &X, int i, int j); //moves X[i]->X[j] and X[j]->X[i]

这是我需要做的：

对于容器A中的数据，我需要使用交换函数将B中指定的每个索引移动到C中的相应索引。我无法在此过程中创建另一个容器。还有可能标记为排序的索引可能不会移动（B[i] = C[i]）。

例如：

A=[a, b, c, d, e, f, g, h, i, j];
B=[0, 1, 3, 6, 9]; //move these entries to....
C= [3, 6, 9, 0, 1]; //these entries

在运行之后，算法 A 将如下所示：

A=[g, j, c, a, e, f, b, h, i, d]

有没有人有好的解决办法？过去几天我一直在为此绞尽脑汁。

Answer 1

下面的交换序列给出了你想要的结果：

交换(0,3)
交换(0,9)
交换(0,1)
交换(0,6)

所以算法是：

Let x = B[0], y = C[0], odd = true
do length(A)-1 times:
    swap( x, y )
    if odd:
        set i such that B[i] = y
        y = C[i]
    else:
        set i such that C[i] = y
        y = B[i]
    odd = not odd

C++ swap/sort 算法

C++ swap/sort algorithm

sorting

swap