问题描述
我用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;
}