根据另一个阵列中定义的排序顺序对阵列​​进行排序

Question

我有一个数组定义另一个数组的排序顺序。例如，要对由char * data[] = {"c", "b", "a"};组成的数组进行排序，sort_order数组将为{2, 1, 0} - 对数组进行排序时，第一个元素应为"c"（即data[sort_order[0]]）。 （这背景是我有两个我想排序的数组，但第二个数组应该使用与第一个数组相同的排序顺序，所以基本上我使用第一个数组的值排序{0, 1, 2}，那么我会使用这种排序顺序来排序两个数组的实际值。）

显而易见的解决方案是创建数组的副本（new_data），然后为每个元素指定正确的值，如排序顺序：

​​

但是，这需要复制数组。有没有一种方法可以交换原始数组的元素，而不必复制数组呢？

编辑："possible duplicate"确实使用另一个数组，这正是我想要避免的。

Answer 1

重新排序，通过旋转“周期”对A []和I []进行排序。每个商店都在适当的位置放置一个值，因此时间复杂度为O（n）。

// reorder A in place according to sorted indices in I 
    // tA is temp value for A 
    for(i = 0; i < n; i++){ 
     if(i != I[i]){ 
      tA = A[i]; 
      k = i; 
      while(i != (j = I[k])){ 
       A[k] = A[j]; 
       I[k] = k; 
       k = j; 
      } 
      A[k] = tA; 
      I[k] = k; 
     } 
    } 

我刚才注意到您使用的是C.在C++中，你可以使用lambda比较功能来比较的A []，基于指数的成员，我[]。对于C，可以使用指针数组P []而不是索引数组I []。

/* create array of pointers to A[] */ 
    for(i = 0; i < n; i++) 
     P[i] = &A[i]; 
    /* sort array of pointers, compare is custom compare function */ 
    qsort(P, n, sizeof(P[0]), compare); 
    /* reorder A[] according to the array of pointers */ 
    for(i = 0; i < n; i++){ 
     if(i != P[i]-a){ 
      tA = A[i]; 
      k = i; 
      while(i != (j = P[k]-a)){ 
       A[k] = A[j]; 
       P[k] = &A[k]; 
       k = j; 
      } 
      A[k] = tA; 
      P[k] = &A[k]; 
     } 
    } 

如果A []包含整数，则示例自定义比较qsort（）。由于qsort（）将指向P []的指针作为参数传递给compare（），并且由于P []是一个指针数组，因此传递给compare（）的参数是指向指针的指针。

int compare(const void *pp0, const void *pp1) 
{ 
    return((**(int **)pp0) - (**(int **)pp1)); 
} 

如果目标是要排序的第二阵列B []，基于排序A []，然后添加线条像：

 /* ... just after tA = A[i] */ 
     tB = B[i]; 
      /* ... just after A[k] = A[j] */ 
      B[k] = B[j]; 
     /* ... just after A[k] = tA */ 
     B[k] = tB;