基于 C++ 中的多个事物进行排序

Sort based on multiple things in C++

提问by Johnny

struct Record
{
    char Surname[20];
    char Initial;
    unsigned short int Gender; //0 = male | 1 = female
    unsigned short int Age;
};
Record X[100];

How can I use Quicksort to sort the values into increasing age, with females before males and surnames in alphabetical order? I've got a:

如何使用 Quicksort 将值按年龄排序，女性在男性和姓氏之前按字母顺序排列？我有一个：

bool CompareData(const int& A, const int& B)
{
    return Records[A].Age < Records[B].Age; //this sorts by age atm
}

回答by peterchen

the general pattern is:

一般模式是：

bool CompareData(const T& a, const T& b) 
{ 
   if (a.PrimaryCondition < b.PrimaryCondition) return true;
   if (b.PrimaryCondition < a.PrimaryCondition) return false;

   // a=b for primary condition, go to secondary
   if (a.SecondaryCondition < b.SecondaryCondition) return true;
   if (b.SecondaryCondition < a.SecondaryCondition) return false;

   // ...

   return false;
} 

where <indicates the "less than" in the desired sort order, you might need to use custom comparison operators for that (e.g. strcmpfor strings,or reverse the <if you want to order descending) (thanks Harry for pointing this out)

where<表示所需排序顺序中的“小于”，您可能需要为此使用自定义比较运算符（例如，strcmp对于字符串，或者<如果您想降序排序，则将其反转）（感谢 Harry 指出这一点）

I've used <on all conditions, since that's sometimes the only comparison operation available, e.g. when you have to use an unknown data type's comparison predicate.

我<在所有条件下都使用过，因为有时这是唯一可用的比较操作，例如，当您必须使用未知数据类型的比较谓词时。

[edit] Note: the last line return falsehandles the case where aand bare considered equal for the comparator.

[编辑] 注意：最后一行return false处理比较器认为a和b相等的情况。

Imagine a.PrimaryCondition==b.PrimaryConditionand a.SecondaryCondition==b.SecondaryCondition- in this case, none of the previous conditions returns any value.

想象一下，a.PrimaryCondition==b.PrimaryCondition和a.SecondaryCondition==b.SecondaryCondition-在这种情况下，没有条件的已返回的任何值。

回答by Tyler McHenry

bool CompareData(const int& A, const int& B)
{
    return (Records[A].Age < Records[B].Age) ||
           ((Records[A].Age == Records[B].Age) && (Records[A].Gender > Records[B].Gender)) || 
           ((Records[A].Age == Records[B].Age) && (Records[A].Gender == Records[B].Gender) &&
              (strcmp(Records[A].Surname, Records[B].Surname) < 0));
}

This compares first by age and returns true if A should appear before B based on age.

这首先按年龄进行比较，如果 A 应根据年龄出现在 B 之前，则返回 true。

If ages are equal, it then compares by gender, and returns true if A should appear before B based on gender (A is female and B is male).

如果年龄相等，则按性别进行比较，如果 A 应根据性别出现在 B 之前（A 是女性，B 是男性），则返回 true。

If ages are equal and genders are equal, it then compares by surname (using strcmp, although if you had used std::stringinstead of a char array, you could have just used <), and returns true if A should appear before B alphabetically by surname.

如果年龄相等且性别相等，则它会按姓氏进行比较（使用strcmp，尽管如果您使用std::string的是字符数组而不是字符数组，您可以只使用<），如果 A 应按姓氏的字母顺序出现在 B 之前，则返回 true。

回答by jk.

the other option to an all singing all dancing comparator is to make sure your sort is a stable sort (quick sort isn't necessarily stable) and sort multiple times with different comparators each time.

全唱全舞比较器的另一个选择是确保您的排序是稳定的排序（快速排序不一定稳定），并且每次都使用不同的比较器进行多次排序。

e.g.

例如

bool CompareAge (const record& l, const record& r)
{
  return l.age < r.age;
}

bool CompareGender (const record& l, const record& r)
{
  return l.gender < r.gender;
}

std::stable_sort(X, X+100, &CompareGender);
std::stable_sort(X, X+100, &CompareAge);

this will be potentially slightly slower but allow you more flexibility with the order of sorts

这可能会稍微慢一些，但可以让您在排序顺序上有更大的灵活性

回答by MSalters

The simple C++ solution is

简单的 C++ 解决方案是

struct Record {
    std::string Surname;
    char Initial;
    unsigned short int Gender; //0 = male | 1 = female
    unsigned short int Age;

    operator<(Record const& rhs) const {
        return std::tie(Gender, Age, Surname) < std::tie(rhs.Gender, rhs.Age, rhs.Surname);
};

However, std::tiesorts directly on the field values. This means you can't use char[20]and males will sort first. A simple variation solves this:

但是，std::tie直接对字段值进行排序。这意味着您不能使用char[20]，男性将首先排序。一个简单的变体解决了这个问题：

struct Record {
    char Surname[20];
    char Initial;
    unsigned short int Gender; //0 = male | 1 = female
    unsigned short int Age;

    operator<(Record const& rhs) const {
        return std::make_tuple(~Gender, Age, std::string(Surname)) <
               std::make_tuple(~rhs.Gender, rhs.Age, std::string(rhs.Surname));
};

With make_tuplewe can pass expressions.

随着make_tuple我们可以通过表情。

回答by Archie

It's better to implement comparator like this:

最好像这样实现比较器：

bool CompareRecords(const Record& a, const Record& b)
{
    if (a.Age < b.Age)
        return true;
    else if (a.Age > b.Age)
        return false;

    if (a.Gender < b.Gender)
        return true;
    else if (a.Gender > b.Gender)
        return false;

    if (strcmp(a.Surname, b.Surname) < 0)
        return true;

    return false;
}

This allows you to easy use of std::sortalgorithm. Sorting itself will look like this:

这使您可以轻松使用std::sort算法。排序本身将如下所示：

std::sort(X, X + 100, &CompareRecords);

EDIT

编辑

You may even want to implement operator <for this structure -- in that case you can normally compare two objects of Recordstructure with operator <. And then you don't need to add the third parameter to std::sort. And well, with that and implemented operator ==you can make all possible comparizons. :)

您甚至可能想要operator <为这个结构实现——在这种情况下，您通常可以Record用 operator比较结构的两个对象<。然后您不需要将第三个参数添加到std::sort. 好吧，有了它并实施，operator ==您可以进行所有可能的比较。:)