C++ swap/sort 算法

C++ swap/sort algorithm

鉴于以下情况:

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]

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

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

  • 交换(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