基于另一个阵列的内容对C数组进行排序

我正在尝试对其元素为索引的数组A进行排序。这些索引涉及另一个数组B，其值将决定A的顺序。所以，我想排序A，这样B[ A[i] ]正在增加。基于另一个阵列的内容对C数组进行排序

例如：

 
A = [0, 1, 4, 5, 7] 
B = [5, 3, 8, 2, 2, 7, 1, 6, 3, 9]

排序A将

 
A' = [ 7, 4, 1, 0, 5 ]

这可能使用C内置的排序，还是我将不得不写我自己的实现？

编辑：这些数组是本地函数变量。

来源

2011-05-20 ajwood

会有可以让这个与qsort一起工作的丑陋的黑客，但我认为你最好写自己的版本.. – 2011-05-20 19:31:43

@Pavan我宁愿在沙漠中打僵尸，而不愿在生产中使用我自己的分拣程序。 – cnicutar 2011-05-20 19:34:05

这不是一个丑陋的黑客。只是有一个函数将数组值映射到排序顺序。在这种情况下，函数可以通过数组查找来实现，但这并不是一个不寻常的要求。 – 2011-05-20 19:43:57

如果你想使用qsort，待办事项，最好的办法是重新包装在索引和值B装入一个结构，然后根据一个新的数组构造一个比较器。例如：

typedef struct 
{ 
    int index_from_A; 
    int value_from_B; 
} index_value_wrapper; 

index_value_wrapper index_wrapper_array[5]; 

for (int i=0; i < 5; i++) 
{ 
    index_wrapper_array[i].index_from_A = A[i]; 
    index_wrapper_array[i].value_from_B = B[A[i]]; 
} 

int comparitor (const void* lhs, const void* rhs) 
{ 
    return (lhs.value_from_B - rhs.value_from_B); 
}

现在你可以运行结构阵列上qsort，并从那里，你可以提取你想要的原始阵列A正确的排序序列，而无需使用自定义排序功能。

来源

2011-05-20 19:44:56 Jason

我认为你可以使用qsort和一个自定义比较

int comparator(const void *x, const void *y) 
{ 
    return (b[*(int*)x] - b[*(int*)y]); 
}

来源

2011-05-20 19:32:09 cnicutar

有没有办法将数组引用传递给比较器？ – ajwood 2011-05-20 19:34:11

@ajwood我不确定我是否理解你的问题 – cnicutar 2011-05-20 19:34:53

Ajwood，如果你的意思是数组指数，no - 数组元素在排序过程中左右移动 – 2011-05-20 19:37:55

如果您有它可用，qsort_r提供了一种方法来做到这一点。您可以在其他参数中给它上下文信息。该上下文被传递给比较函数。您可以访问该附加信息以提取所需的排序信息。

微软编译器有一个类似的：qsort_s

来源

2011-05-20 19:34:49

我使用的是Ubuntu，它似乎不在身边...... – ajwood 2011-05-20 19:47:38

使用您的规则作为比较功能，快速排序（只要B比较长）：

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

int A[] = {0, 1, 4, 5, 7}; 
int B[]= {5, 3, 8, 2, 2, 7, 1, 6, 3, 9}; 

int my_cmp(const void *a_, const void *b_,void *arg_) 
{ 
    const int *a = a_, *b = b_; 

    if(B[*a] == B[*b]) 
     return 0; 
    else if (B[*a] < B[*b]) 
     return -1; 
    else 
     return 1; 

} 

int main(int argc,char *arga[]) 
{ 
    int i; 

    qsort(A,sizeof A/sizeof A[0] ,sizeof A[0],my_cmp); 

    puts("Sorted A"); 
    for(i = 0 ; i < sizeof A/sizeof A[0]; i++) { 
     printf("A[%d] : %d B[A[%d]] : %d\n",i,A[i],i,B[A[i]]); 
    } 

    return 0; 
}

这给：

$ ./a.out 
Sorted A 
A[0] : 4 B[A[0]] : 2 
A[1] : 1 B[A[1]] : 3 
A[2] : 0 B[A[2]] : 5 
A[3] : 7 B[A[3]] : 6 
A[4] : 5 B[A[4]] : 7

在很多平台上可用的也是qsort_r（在linux上，您将必须使用#define _GNU_SOURCE包括<stdlib.h>才能使用它。 g，你会将比较功能改为例如

int my_cmp(const void *a_, const void *b_,void *arg_) 
{ 
    const int *a = a_, *b = b_, *arg = arg_; 

    if(arg[*a] == arg[*b]) 
     return 0; 
    else if (arg[*a] < arg[*b]) 
     return -1; 
    else 
     return 1; 

}

并调用qsort_r像

qsort_r(A,sizeof A/sizeof A[0] ,sizeof A[0],my_cmp,B);

来源

2011-05-20 19:44:25 nos

如果A和B本地为main，则不起作用。 – 2011-05-20 19:47:52

只要它不是多线程，就可以很好地工作。如果它不是单线程的，并且参考数据（B）不是静态的，那么它将不起作用。 – 2011-05-20 19:48:42

@Paul qsort是C语言中唯一的标准排序功能，它的工作原理就是这样，否则你必须自己推出，或者使用非标准的东西，比如qsort_r--增加了一个例子。除非你在多线程环境中，否则A和B很可能是本地的。你只需要在调用qsort – nos 2011-05-20 19:55:11

创建struct { int a_value; int b_value}类型的另一个数组C，将每个元素初始化为a的每个索引的值，并从b查找值。排序，遍历排序后的C，将a_values复制回A中。

Viola。不，那是一把大提琴。瞧！

来源

2011-05-20 19:47:15

基于另一个阵列的内容对C数组进行排序

回答

相关问题