基於另一個陣列的內容對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數組進行排序

回答

相關問題