在C语言中，按照另一个数组元素的相对顺序对一个数组进行排序

Question

我希望按照第一个数组的顺序对第二个数组进行排序。例如：

first = {1,8,7,2,4}
second = {9,7,2,10,3}

我希望第一个值保持不变，而第二个值按照与第一个相同的相对顺序进行排序。也就是说，最小值位于索引0，第二小的值位于索引3，第三小的值位于索引4等等。

second = {2,10,9,3,7}

我已经尝试了一些下列问题的代码

#include <stdio.h>

typedef struct
{
    int num;
    int pos;
}ArrType;

ArrType arrA[5] = {{1,0},{8,1},{7,2},{2,3},{4,4}};
ArrType arrB[5] = {{9,0},{7,1},{2,2},{10,3},{3,4}};;

int cmparr(const void *a, const void *b)
{
    ArrType *tmpa, *tmpb;
    tmpa = (ArrType*) a;
    tmpb = (ArrType*) b;

    return(arrA[tmpa->pos].num - arrA[tmpb->pos].num);
}
int main(void)
{
    int i;
    qsort(arrB,5, sizeof(ArrType), cmparr);

    for (i=0; i<5; i++)
    {
        printf ("%d ",arrB[i].num);
    }
    return (0);
}

实际输出结果为

9 10 3 2 7

我愿意尝试不同的数据结构，但是arrB只能进行一次排序。

我看过一些C++、Javascript和其他语言的解决方案。但是在C语言中没有解决方法。

编辑 - 在最终程序中，这些数组将非常大。我正在寻找单个排序操作，即单个调用qsort。

- Ranon

---

实际输出与预期不符。cmparr函数或使用的数据结构中有问题。 - Ranon

@Socowi - 我已经指定了期望的输出second = {2,10,9,3,7}。 - Ranon

@Socowi 我认为更像是：您检查“first”的顺序，因此最低的位置在位置0，下一个位置在位置3等。然后，您将此顺序应用于“second”，因此您搜索最低值并将其放置在位置0，然后搜索下一个值并将其放置在位置3等。 - Yastanub

@Scheff 是的 - 在你删除它之后我想到了这一点 :D - Tibrogargan

@Ranon，你不会通过单个排序操作找到解决方案。因为你隐式地需要能够回答“数组中最大的元素是什么？”这个问题，所以你要么需要对它们进行排序，要么搜索它们——这在未排序的数组上是一个更昂贵的操作。 - Tibrogargan

Answer 1

你需要创建与所需排序匹配的元数据（即索引数组）。然后将该元数据应用于第二个数组。"最初的回答"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int first[] = {1,8,7,2,4};
int second[] = {9,7,2,10,3};

int compare(const void * a, const void * b);
int binary_search(int array[], int min, int max, int target);
void print_array(int * array, int c);

int main()
{
  int idx;
  int c = sizeof(first)/sizeof(int);
  int * sorted = NULL;
  int * indexes = NULL;
  int * result = NULL;

  if (NULL == (sorted = malloc(sizeof(first)))) {
      return -1;
  }
  memcpy(sorted, first, sizeof(first));

  if (NULL == (indexes = malloc(sizeof(first)))) {
      free(sorted);
      return -1;
  }
  memset(indexes, -1, sizeof(first));

  if (NULL == (result = malloc(sizeof(second)))) {
      free(sorted);
      free(indexes);
      return -1;
  }
  memset(result, -1, sizeof(second));

  // 1st: Sort the reference array
  qsort (sorted, c, sizeof(int), compare);

  // 2nd: Record the position of each sorted element in the original array (this is your meta-data)
  for (idx=0; idx<c; idx++) {
      indexes[idx] = binary_search(sorted, 0, c, first[idx]);
  }

  // 3rd sort the target array
  memcpy(sorted, second, sizeof(second));
  qsort (sorted, c, sizeof(int), compare);

  // 4th apply the stored positions to the sorted target array
  for (idx = 0; idx < c; idx++) {
      result[idx] = sorted[indexes[idx]];
  }
  print_array(result, c);

  free(result);
  free(indexes);
  free(sorted);
  return 0;
}

int compare(const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int binary_search(int array[], int min, int max, int target)
{
    int mid;
    while (min <= max)
    {
        mid = min + (max - min)/2;
        if (target > array[mid])
            min = mid + 1;
        else if (target < array[mid])
            max = mid - 1;
        else
            return mid;
    }
    return -1;
}

void print_array(int * array, int c)
{
    for(int i = 0; i < c; i++) {
        printf("%d ", array[i]);
    } 
    printf("\n");
}

最初的回答：

演示

。

- Tibrogargan

---

这个解决方案中有3个排序操作。由于数组的大小可能很大，我正在寻找一种单一的排序操作。 - Ranon

第三个在哪里？虽然这并不重要，但2比1大。 - Tibrogargan

Answer 2

这是我的方法，它使用qsort两次，arrC包含了结果。

#include <stdio.h>

typedef struct
{   
    int num;
    int pos;
}ArrType;

ArrType arrA[5] = {{1,0},{8,1},{7,2},{2,3},{4,4}};
int arrB[5] = {9,7,2,10,3};;
int arrC[5];
int cmpInt(const void *a, const void *b)
{   
        return(*a - *b);
}
int cmp(const void *a, const void *b)
{   
    ArrType *tmpa, *tmpb;
    tmpa = (ArrType*) a;
    tmpb = (ArrType*) b; 
        return(tmpa->num - tmpb->num);
}
int main(void)
{
    int i;
    qsort(arrA,5, sizeof(ArrType), cmp);
    qsort(arrB,5, sizeof(ArrType), cmpInt);
    for (i=0; i<5; i++)
    {   
        arrC[arrA[i].pos] = arrB[i];
    }   
    return (0);
}

- Sandy

---

这里有两个排序操作。能否只用一个排序操作完成？ - Ranon

@Ranon 我们需要找到已排序和给定顺序之间的映射，这将需要一个排序过程。另一个排序过程是为了让第二个数组排序，以便使用映射是一个线性操作。这是一个 NlogN 的解决方案，如果我们设法在单个排序操作中完成它，仍然会是 NlogN。 - Sandy

Answer 3

因为 C 语言没有 lambda 比较函数（可以用于根据 first[] 对索引数组进行排序），所以下面的代码使用 qsort() 将指针数组 ap[] 按照 first[] 的元素进行排序。使用指针可以消除将数组名作为比较函数参数的需要，进而允许比较函数与 qsort() 协同工作。表达式（ap[i]-first）将指针转换为索引。接下来，使用 qsort() 对 second[] 进行排序。然后，ap[] 作为排名集合，按照 O(n) 时间在原地重新排序 second[]。

解释按排名重新排序与按索引重新排序：

    dst[rank[i]] = src[i];              /* reorder by rank */
    dst[i] = src[index[i]];             /* reorder by index */

示例代码：

#include <memory.h>
#include <stdio.h>
#include <stdlib.h>

/* compare for ptr to integer */
int cmppi(const void *p0, const void *p1){
    return (*(int *)p0 - *(int *)p1);
}

/* compare for ptr to ptr to integer */
int cmpppi(const void *p0, const void *p1){
    return (**(int **)p0 - **(int **)p1);
}

int main()
{
int first[] =  {1, 8, 7, 2, 4};
int second[] = {9, 7, 2,10, 3};
int **ap;                               /* array of pointers */
int *tmpp;
int tmpi;
size_t i, j;

    /* allocate and generate array of pointers to first[] */
    ap = (int **)malloc(sizeof(first)/sizeof(first[0])*sizeof(int *));
    for(i = 0; i < sizeof(first)/sizeof(first[0]); i++)
        ap[i] = &first[i];
    /* sort ap  */
    qsort(ap, sizeof(first)/sizeof(first[0]), sizeof(int *), cmpppi);
    /* sort second */
    qsort(second, sizeof(second)/sizeof(second[0]), sizeof(int), cmppi);
    /* reorder ap and second in place using ap as rank (O(n) time) */
    for (i = 0; i < sizeof(second) / sizeof(second[0]); i++){
        while(i != (j = ap[i] - first)){
            tmpp = ap[i];               /* swap(ap[i], ap[j]) */
            ap[i] = ap[j];
            ap[j] = tmpp;
            tmpi = second[i];           /* swap(second[i], second[j] */
            second[i] = second[j];
            second[j] = tmpi;
        }
    }   
    /* display second[] */
    for (i = 0; i < sizeof(second) / sizeof(second[0]); i++)
        printf("%3d", second[i]);
    printf("\n");
    free(ap);
    return 0;
}

- rcgldr