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