存儲使用的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} 

總之，我想跟蹤原始索引。我用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

需要由每個片的信息存儲在一個結構，以對數的，例如進行排序：

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

Answer 2

這是一個常見的需求。一個可能的辦法是更換整數與陣列和陣列2元結構：

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 3

你問題與qsort無關，而僅僅是程序設計。

「在這個數組中，每個索引代表一個玩家」是問題所在。即使您想要更改數組索引，您也發明了數組索引和內容之間的奇怪依賴關係。

而不是int的數組，充滿神祕的「幻數」，使用一個有意義的數據結構數組。

這可能例如是這樣的：

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

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

現在，您可以根據自己的喜好快速排序該表。

請注意，出於性能原因，最好是聲明一個指向結構體的指針數組，然後qsort該數組。這種方式少得多的數據混洗。