c - 有效地对结构数组进行排序

Question

我正在使用qsort对结构数组进行排序，并且我正在寻找一种更有效的方法来通过对数组进行部分排序来提取前三个最高分数。我的结构如下所示:

typedef struct {
    double score;
    int player_num;
} player_t;

我已经分配了一个像这样的结构数组:

player_t *players = malloc(SIZE * sizeof(player_t));

我对这个结构体数组进行排序的方法是首先对分数进行排序，如果分数相同，则按玩家编号进行排序。

我的代码与 qsort 类似:

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

#define SIZE 6
#define MAX 3

int scorecmp(const void *a, const void *b);
int ComparePlayerScore( const void* ap , const void* bp );
int CompareInt( const int a , const int b );

typedef struct {
    double score;
    int player_num;
} player_t;

int
main(int argc, char *argv[]) {
    int i;

    int player_numbers[] = {1, 2, 3, 4, 5, 6};
    double scores[] = {0.765, 0.454, 0.454, 0.345, 0.643, 0.532};

    player_t *players = malloc(SIZE * sizeof(player_t));

    for (i = 0; i < SIZE; i++) {
        players[i].score = scores[i];
        players[i].player_num = player_numbers[i];
    }

    qsort(players, SIZE, sizeof(*players), ComparePlayerScore);

    for (i = 0; i < MAX; i++) {
        printf("Player %d: Score: %.3f\n", players[i].player_num, players[i].score);
    }

    free(players);

    return 0;
}

int ComparePlayerScore( const void* ap , const void* bp ) {
    const player_t* const a = ap;
    const player_t* const b = bp;

    if( a->score == b->score ){
        return CompareInt( a->player_num , b->player_num );
    }
    else if( a->score > b->score ) {
        return -1;
    }
    else {
        return 1;
    }
}

int CompareInt( const int a , const int b ) {
    if( a < b ){
        return -1;
    }
    else if( a > b ){
        return 1;
    }

    return 0;
}

我只是在寻找另一种方法来做到这一点，但是一种更有效的方法来提取前 3 名的分数以及各自的玩家编号。就像我可以提取数组的前三个元素而不必每次都先对整个数组进行排序的方法一样。

Answer 1

这是我的奉献。由于您有 #define MAX 来确定您想要找到多少个最高分，因此我已经考虑过这一点。

程序对数据进行单次传递，并对每条记录的最顶层进行一次传递。我使用了固定数组，您必须适应您的需求。

#include <stdio.h>

#define SIZE 6
#define MAX 3

typedef struct {
    double score;
    int player_num;
} player_t;

int main(int argc, char *argv[])
{
    player_t players[SIZE] = {{2.0, 2}, {4.0, 5}, {1.0, 4}, {1.0, 1}, {5.0, 3}, {4.0, 6}};
    int order[MAX+1] = {0};
    int found = 1;
    int i, j;
    int bigger;

    for(i = 1; i < SIZE; i++) {
        bigger = 0;
        for(j = 0; j < found; j++) {
            if(players[i].score > players[ order[j] ].score) {
                bigger = 1;
                break;
            }
            else if(players[i].score == players[ order[j] ].score && 
                    players[i].player_num < players[ order[j] ].player_num) {
                bigger = 1;
                break;
            }
        }
        if(bigger) {
            memmove(order + j + 1, order + j, (found - j) * sizeof order[0]);
            order[j] = i;
            if(found < MAX) {
                found++;
            }
        }
    }

    for(i = 0; i < found; i++) {
        printf("%d %f\n", players[ order[i] ].player_num, players[ order[i] ].score); 
    }
    return 0;
}

程序输出:

3 5.000000
5 4.000000
6 4.000000