在C++中根据另一个数组的成员对数组进行排序

Question

我的问题是下面这个（这只是一个简单的例子来展示问题）：

我有：

I have:

int* array1;
double* array2. 

array1=new int[10];
array2=new double[10];
array1=filledWithIntegers(random);
array2=filledWithDoubles(random);

//我想根据array2的值对array1进行排序。我尝试使用stdlib中的qsort函数。 qsort(array1,6,sizeof(int),compare);

关键是如何编写compare函数以便按照array2的顺序对array1进行排序。

不能使用stdlib中的数据结构，必须直接在数组指针中完成。

谢谢。

- Pau

Answer 1

不要对array1中的整数进行排序，而是使用array2[index]来比较元素的索引，并根据从排序中获得的置换重新排列array1。

这里有一个快速演示：

#include <stdio.h>
#include <stdlib.h>

int array1[] = {1, 7, 3, 9, 5};
double array2[] = {1.1, 7.7, 3.3, 9.9, 5.5};

int compare (const void * a, const void * b) {
    double diff = array2[*(int*)a] - array2[*(int*)b];
    return  (0 < diff) - (diff < 0);
}

int main(void) {
    int perm[5], i;
    int res[5];
    for (i = 0 ; i != 5 ; i++) {
        perm[i] = i;
    }
    qsort (perm, 5, sizeof(int), compare);
    for (i = 0 ; i != 5 ; i++) {
        res[i] = array1[perm[i]];
    }
    for (i = 0 ; i != 5 ; i++) {
        printf("%d\n", res[i]);
    }
    return 0;
}

- Sergey Kalinichenko

---

几乎了。当较小值时，compare 应该返回 -1（而不是 0）。 - user2k5

@user2k5 你说得对 - 我已经改变了函数，使用了来自这个答案的符号技巧。 - Sergey Kalinichenko

不需要额外的排列数组，只需计算a和b在array1中的位置。比较器已经必须知道array2了。 - Christian Rau

感谢您的回答@dasblinkenlight，您的解决方案对我的问题非常有效。 - Pau

Answer 2

是的。您需要将这两个数组组合成一对数组，然后定义比较函数。

比较函数可以是：

bool compare(const pair<int,double>& t1, const pair<int,double>& t2){
    return (t1.second < t2.second);
}

- guinny

---

谢谢你的回答。我忘了告诉你，这不是使用std库类型的可能性，只能尝试保留数据格式来对数组指针值进行排序。 - Pau

你可以使用结构体自己定义地图，是吗？ - guinny

你是不是想用 pair 而不是 map？ - Christian Rau

感谢您抽出时间回答，我已经通过之前的回复得到了解决方案。 - Pau

Answer 3

好的，您只需要使用元素的位置来索引另一个数组，并在比较函数中进行比较（标准保证比较函数的指针参数始终指向要排序的数组）：

int compare(const void *a, const void *b)
{
    unsigned int i = (const int*)a - array1;
    unsigned int j = (const int*)b - array1;
    if(array2[i] < array2[j])
        return -1;
    if(array2[i] > array2[j])
        return 1;
    return 0;
}

缺点在于比较函数必须明确知道具体的数组，因为它不能获取任何其他参数。

无论如何，我会质疑对qsort的使用，因为您的问题标记为C ++。虽然std::sort有相同的问题，但是您可以通过使用封装相关数组的比较函数符来实现更多的通用性和抽象性。

- Christian Rau

---

感谢您抽出时间回答，我在之前的问题中得到了解决方案。 - Pau

我无法理解你代码中的前两行：你是如何从另一个数组的指针中减去array1“它是指针”的？！ - ahmed allam

减去两个指针可以得到它们所指向的元素之间的距离。只要两个指针都指向同一个数组，这就是完全符合标准的行为。而特定的对qsort的调用又保证了a和b都指向array1。因此，所有这些操作都是计算a和b在array1内部所指向的索引，然后用这些索引来索引array2。 - Christian Rau