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

更好的解决方案是，把数据转换成结构的阵列，然后进行排序，基于期望的键（即，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()进行排序，其通常是高度可取的。

Answer 2

这不能按要求解决，排序功能不公开它们执行的交换。

但是，看起来结果可以用一个结构来实现。

struct combined { 
    int a_; 
    int b_; 
}; 

凡qsort功能测试a_元素，而且排序b_数据。 同样，这需要一个比较函数

int compare(const void * l, const void * r) 
{ 
    struct combined * _l= (struct combined *)l; 
    struct combined * _r= (struct combined *)r; 
    if(_l->a_ > _r->a_) return -1; // reverse sort 
    if(_l->a_ < _r->a_) return 1; 
    return 0; 
} 

终于

struct combined array[] = { {2,4}, {3,2}, {1,3} }; 
qsort(array, 3, sizeof(struct combined), compare); 

array => { {3,2}, {2,4}, {1,3} }; 

Answer 3

// i am going to submit the idea not the code. 

    int *a,*b; 
    int *ord; // an array that holds indexes (sorting orders) 

//... 

    a[ord[0]] = 2; a[ord[1]] = 3; a[ord[2]] = 1; 
    b[ord[0]] = 4; b[ord[1]] = 2; b[ord[2]] = 3; 

//... 
//now you have just to sort the indexes array ord 

Answer 4

这个例子做什么要求原来的问题，它按两个（或多个）阵列以同样的方式，而不必将数组元素组合成一个通用结构。

它使用一个指针数组，所以比较函数不需要知道它正在排序哪个数组，只需要排序元素的类型。可以修改它以根据其中一个数组对多个数组进行排序。

它创建指针数组以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; 
}