根據另一個陣列中定義的排序順序對陣列​​進行排序

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;