使用qsort存储排序后的原始索引

Question

假设我有以下数组：

int A[5]={2,3,5,4,1};

在这个数组中，每个索引代表一个玩家。例如：

A[0]=player 0
A[1]=player 1
.....

我想按降序对数组进行排序，如下所示：

A[5]={5,4,3,2,1};

我还想跟踪玩家的前一个索引，这样我就可以像这样编写排序数组：

{player 2, player 4, player 1, player 0,player 4} 

一言以蔽之，我想跟踪原始的索引。我已经用C语言编写了一个程序，使用qsort将元素按降序排列。

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

int A[] = {2,3,5,4,1};

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

int main ()
{
  int n;
  qsort (A, 5, sizeof(int), compare);
  for (n=0; n<5; n++)
  printf ("%d ",A[n]);
  return 0;
}

是否也可以使用此qsort来跟踪原始索引？

Answer 1

这是一个常见的需求。一种可能的方法是将int数组替换为包含2个元素的and数组结构：

struct PlayerScore {
    int playerId;
    int score;
}

你的代码可能会变成：

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

int A[] = {2,3,5,4,1};
#define N sizeof(A)/sizeof(A[0])

struct PlayerScore {
    int playerId;
    int score;
};
int compare (const void * a, const void * b)
{
    return ( (*(struct PlayerScore*)b).score - (*(struct PlayerScore*)a).score );
}

int main ()
{
  int n;
  struct PlayerScore ps[N];
  for(n=0;n<N; n++) {
      ps[n].playerId = n;
      ps[n].score = A[n];
  }
  qsort (ps, 5, sizeof(struct PlayerScore), compare);
  for (n=0; n<N; n++)
      printf ("%d (%d) ",ps[n].score, ps[n].playerId);
  return 0;
}

你最终会得到：

5 (2) 4 (3) 3 (1) 2 (0) 1 (4)

Answer 2

你的问题与qsort无关，而仅仅是程序设计。

“在这个数组中，每个索引代表一个玩家”就是问题所在。

用有意义的数据组成一个结构数组，而不是用神秘的“魔术数字”填充int数组。

例如，它可能是这样的：

typedef struct
{
  // whatever makes sense to store here, names, stats etc      
} player_t;

player_t players [] = 
{
  {0, ...},
  {1, ...},
};

现在，您可以根据您喜欢的任何内容对该表进行Q排序。

请注意，出于性能原因，最好先声明一个指向结构的指针数组，然后对该数组进行qsort。通过这种方式，qsort的数据混洗要少得多。

Answer 3

您需要对数字对进行排序，例如，通过将每条信息存储在一个结构中：

struct player {
  int data;
  int index;
};

struct player A[] = {{2,0}, {3,1}, {5,2}, {4,3}, {1,4}};

int compare (const void * a, const void * b)
{
   return ( ((struct player*)b)->data - ((struct player*)a)->data );
}

int main ()
{
  int n;
  qsort (A, 5, sizeof(struct player), compare);
  for (n=0; n<5; n++)
  printf ("data=%d, index=%d\n", A[n].data, A[n].index);
  return 0;
}