C++交换/排序算法

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 中的数据，我需要使用 swap 函数将 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