根据在位的另一个数组对一个数组进行排序

我用C++(使用C++11标准)编写代码，我有两个大的内置类型数组，我想根据第一个数组对第二个数组进行排序。 下面是一个例子：

A = {1, 5, 4, 3, 6, 2};
B = {1, 2, 3, 4, 5, 6};

排序后：

A = {1, 2, 3, 4, 5, 6};
B = {1, 6, 4, 3, 2, 5};

就好像每个元素B[i]都附加到元素A[i]，您只需对数组A进行排序。因此B中的元素根据A中的相应元素移动。我知道这个问题已经问了一遍又一遍，但我遇到的唯一解决方案是使用pair<type 1, type 2>。但考虑到数组很大，为成对数组和复制数组来回分配内存需要相当长的时间。 但我相信排序可以就地完成，即只使用O(1)内存。事实上，如果Std：：Sort允许交换服装，那就好了。因为我认为这是排序算法使用的唯一一个超越比较器的东西。

A = vector<double>(1e6);  // some random numbers
B = vector<double>(1e6);  // some random numbers
Comp comp(&A,&B);
Swap swap(&A,&B);
costume_sort(A,B,comp,swap);   // some sort function that can take costume swap and compare

class Comp {
   vector<double> *A;
   vector<double> *B;
   Comp(vector<double> *A, vector<double> *B) : A(A),B(B) {};

   bool compareTo(size_t i, size_t j) { return A->at(i) < A->at(j); };
};


class Swap {
   vector<double> *A;
   vector<double> *B;
   Swap(vector<double> *A, vector<double> *B) : A(A),B(B) {};

   void swapFnc(size_t i, size_t j) { swap(A->at(i), A->at(j));swap(B->at(i), B->at(j)); };
};

STL或其他库中有没有可以做到这一点的函数？这是我在这里试图解释的想法的一种伪代码。显然，这并不准确，但我希望它清楚我的意思。

---

解决方案

根据指向a[]的已排序指针数组对a[]和b[]重新排序的示例。因为使用了指针数组，所以比较函数只需要知道要比较的元素的类型。在位重排序的时间复杂度为O(N)，每个商店在其排序的位置放置一个值。请注意，指针数组在重新排序期间将恢复到其原始状态(&；a[0]...&；a[n-1])。

bool compare(const int *p0, const int *p1)
{
    return *p0 < *p1;
}

int main()
{
int a[8] = {7,5,0,6,4,2,3,1};
char b[8] = {'h','f','a','g','e','c','d','b'};
int *pa[8];
size_t i, j, k;
int ta;
char tb;
    // create array of pointers to a[]
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        pa[i] = &a[i];
    // sort array of pointers to a[]
    std::sort(pa, pa+sizeof(a)/sizeof(a[0]), compare);
    // reorder a[] and b[] according to the array of pointers to a[]
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++){
        if(i != pa[i]-a){
            ta = a[i];
            tb = b[i];
            k = i;
            while(i != (j = pa[k]-a)){
                a[k] = a[j];
                b[k] = b[j];
                pa[k] = &a[k];
                k = j;
            }
            a[k] = ta;
            b[k] = tb;
            pa[k] = &a[k];
        }
    }
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        std::cout << a[i] << ' ';
    std::cout << std::endl;
    for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
        std::cout << b[i] << ' ';
    std::cout << std::endl;
    return 0;
}