C - 以相同的方式对两个数组进行排序

Question

所以,我有两个数组(指针实际上),让他们打电话a和b.我想先排序a,然后保存我所做的完全交换以获得排序的数组并将它们应用于我的向量b.这是我的意思的一个简短例子:

int *a, *b;
//appropriate mallocs
a[0] = 2; a[1] = 3; a[2] = 1;
b[0] = 4; b[1] = 2; b[2] = 3;
//sort a in decreasing order --> a==[3, 2, 1]
//sort b based on sorting of a --> b==[2, 4, 3]

如何在不编写自己的排序函数的情况下实现这一目标？

Answer 1

此示例执行原始问题所要求的内容,它以相同的方式对两个(或更多)数组进行排序,而不必将数组元素组合到一个公共结构中.

它使用一个指针数组,因此compare函数不需要知道它正在排序哪个数组,只需要知道要排序的元素的类型.可以修改它以根据其中一个数组对多个数组进行排序.

它创建一个指针数组到a[],使用qsort()根据对指针数组进行排序a[],然后使用排序指针重新排序两者a[]并b[]在适当位置(与排序指针恢复到它们的初始状态下的副作用).

重新排序时间复杂度为O(n),因为每个商店将元素放置在其排序位置.

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

int compare(const void *pp0, const void *pp1)
{
    int i0 = **(int **)pp0;
    int i1 = **(int **)pp1;
    if(i0 > i1)return -1;
    if(i0 < i1)return  1;
    return 0;
}

int main()
{
    int a[3] = {2, 3, 1};
    int b[3] = {4, 3, 2};
    int *pa[3];
    size_t i, j, k;
    int ta, 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 */
    qsort(pa, sizeof(a)/sizeof(a[0]), sizeof(pa[0]), compare);

    /* reorder a[] and b[] according to the array of pointers */
    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++)
        printf("%2d ", a[i]);
    printf("\n");

    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        printf("%2d ", b[i]);
    printf("\n");

    return 0;
}

Answer 2

更好的解决方案是将数据分组为结构数组，然后根据所需键（即a值）对数据进行排序：

struct my_data {
  int a;
  int b;
};

struct my_data data[100];

static int data_cmp(const void *a, const void *b)
{
  const struct my_data *da = a, *db = b;

  return da->a < db->a ? -1 : da->a > db->a;
}

qsort(data, sizeof data / sizeof *data, sizeof *data, data_cmp);

这用于qsort()排序，这通常是非常需要的。