在C语言中，有没有一种方法可以通过多个变量对结构体进行排序？

Question

我需要编写一个函数，对数组中的结构体进行排序。结构体如下：

#define MAX_USERNAME_LENGTH 16

typedef struct{
 char username[MAX_USERNAME_LENGTH];
 unsigned int rides;
 unsigned int rank;
} driver;

该程序从一个 .txt 文件中加载数据并填充数组。

driver driver_list[256]

我需要按照排名和乘车次数对driver_list进行排序。因此，如果我的文件包含以下内容：

//user rides rank
frank209 3 6
john76 7 6
harry99 2 2
bob77 5 2

输出必须显示：

john76 7 6
frank209 3 6
bob77 5 2
harry99 2 2

有一种方法可以做到这一点吗？我尝试过使用两个嵌套的for循环来进行选择排序，但是输出结果只能按照等级或者乘车次数其中一个排序。

感谢您的帮助。

- Salvatore Maruccio

---

在标准的C文档或谷歌上查找qsort。许多实现都提供了这个函数。 - Paul Ogilvie

简短回答：是的。通常的做法是使用更复杂的比较函数。你可以进行普通排序，但每次比较两条记录时，首先按主键比较，如果它们相等，则会回退并按次要键比较。 - Steve Summit

你只需要根据两个值进行比较来实现排序。首先比较等级，如果等级不同，则采取相应措施。如果等级相同，则比较乘车次数并采取相应措施。 - Gerhardh

Answer 1

使用标准函数qsort，该函数声明在头文件<stdlib.h>中，并编写一个自定义比较函数。

这就是您需要的内容。

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

#define MAX_USERNAME_LENGTH 10

typedef struct
{
    char username[MAX_USERNAME_LENGTH];
    unsigned int rides;
    unsigned int rank;
} driver;

int cmp( const void *left, const void *right )
{
    const driver *a = ( const driver *)left;
    const driver *b = ( const driver *)right;

    if ( b->rank < a->rank )
    {
        return -1;
    }
    else if ( a->rank < b->rank )
    {
        return 1;
    }
    else
    {
        return  (  a->rides < b->rides ) - ( b->rides < a->rides );
    }
}


int main(void) 
{
    enum { N = 4 };
    driver driver_list[N] =
    {
        { "frank209", 3, 6 }, 
        { "john76", 7, 6 }, 
        { "harry99", 2, 2 }, 
        { "bob77", 5, 2 }   
    };

    qsort( driver_list, N, sizeof( driver ), cmp );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%s, %u, %u\n", 
                driver_list[i].username, driver_list[i].rides, driver_list[i].rank );
    }

    return 0;
}

程序的输出为：

john76, 7, 6
frank209, 3, 6
bob77, 5, 2
harry99, 2, 2

- Vlad from Moscow

Answer 2

一个关键的概念是，一个记录“在前”意味着什么。不要认为这是排序算法的一个特性——如何构造排序算法使它按多个字段排序——而是记录之间关系的一个特性。你将只有一个常规的排序算法，但它的排序顺序标准使用记录的两个字段来确定哪个是“更早”的。如果一个记录排名更高，或者排名相同，则拥有更多车程的记录会先于其他记录。

一旦你知道了“在前”意味着什么，你就有了一个排序关系。然后任何排序方法都可以。你只需要使用选择的排序关系进行排序即可。

如果你正在使用 C 标准库中的 qsort 函数，你需要编写一个比较函数：

• 接受两个指向const void的指针，这是由于qsort接口所必需的。
• 将这些指针转换为指向您的结构体的指针。
• 如果第一个结构体的等级高于第二个，则返回负值（表示“更早”）。如果它的等级较低，则返回正值（表示“更晚”）。
• 否则，等级相等。如果第一个结构体有更多的乘车次数，则返回负值。如果它有更少的乘车次数，则返回正值。如果它们相同，则返回零。

如果您正在编写自己的排序程序，则仍然使用上述比较过程。

- Eric Postpischil