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

I'm trying to sort an array A whose elements are indexes. The indexes refer to another array B whose value will determine the order of A. So, I would like to sort A such that B[ A[i] ] is increasing.

我正在尝试对其元素为索引的数组A进行排序。索引引用另一个数组B，其值将决定A的顺序。因此，我想对A进行排序，使得B [A [i]]正在增加。

For example:

例如：

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

Sorted A would be

排序A将是

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

Is this possible with C's built-in sort, or am I going to have to write my own implementation?

这可能与C的内置排序，或者我将不得不编写自己的实现？

EDIT: These arrays are local function variables.

编辑：这些数组是局部函数变量。

5 个解决方案

#1

If you want to use qsort, the best thing to-do would be to re-wrap the indexes in A and the values in B into a struct, and then make a comparator based on a new array that struct. For instance:

如果你想使用qsort，最好的办法是将A中的索引和B中的值重新包装成一个struct，然后根据一个新的struct数组创建一个比较器。例如：

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);
}

Now you can run qsort on the struct array and from there you can extract the proper sorted sequence you desired for the original array A without having to use a custom sorting function.

现在，您可以在struct数组上运行qsort，从那里您可以提取原始数组A所需的正确排序顺序，而无需使用自定义排序功能。

#2

If you have it available, qsort_r provides a way to do this. You can give it context information in an additional parameter. That context is passed to the comparison function. You can access that additional information to extract the desired sorting information.

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

The Microsoft compiler has a similar one: qsort_s

Microsoft编译器有一个类似的：qsort_s

#3

I think you can use qsort and a custom comparator

我想你可以使用qsort和自定义比较器

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

#4

Use your rule as the comparison function to qsort (as long as B is longer than A):

使用您的规则作为qsort的比较函数（只要B长于A）：

#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;
}

This gives:

这给出了：

$ ./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

Available on many platforms is also qsort_r(on linux you'll have to #define _GNU_SOURCE before including <stdlib.h> to use it. Using that, you'd change the comparison function to e.g.

在许多平台上都可以使用qsort_r（在linux上你必须先#define _GNU_SOURCE才能包含来使用它。使用它，你可以将比较功能更改为例如。

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;

}

And call qsort_r like

并调用qsort_r之类的

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

#5

Create another array C of type struct { int a_value; int b_value}, initialise each element to the values of each index of a and the value looked up from b. Sort that, traverse the sorted C copying the a_values back into A.

创建另一个类型为struct {int a_value; int b_value}，将每个元素初始化为a的每个索引的值和从b查找的值。对其进行排序，遍历已排序的C，将a_values复制回A.

Viola. No, that's a large violin. Voila!

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

#1