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

Question

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

我如何使用Quicksort将值排序为年龄增长,男性和姓氏之前的女性按字母顺序排列？我有一个:

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

Answer 1

一般模式是:

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 <表示所需排序顺序中的"小于",您可能需要使用自定义比较运算符(例如,strcmp对于字符串,或者<如果您想要降序则反转)(感谢Harry指出这一点)

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

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

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

Answer 2

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

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

如果年龄相等,则按性别进行比较,如果A应基于性别出现在B之前,则返回true(A为女性,B为男性).

如果年龄相等且性别相等,则按姓氏进行比较(使用strcmp,尽管如果您使用过std::string而不是char数组,则可能刚刚使用过<),如果A应按字母顺序出现在B之前,则返回true.

Answer 3

所有唱歌所有跳舞比较器的另一个选择是确保你的排序是稳定的排序(快速排序不一定稳定)并且每次使用不同的比较器进行多次排序.

例如

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

这可能会稍微慢一些,但允许您按顺序排列更灵活

Answer 4

简单的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);
};

但是,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));
};

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

Answer 5

最好像这样实现比较器:

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

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

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

编辑

您甚至可能想要实现operator <此结构 - 在这种情况下,您通常可以将两个Record结构对象与运算符进行比较<.然后你不需要添加第三个参数std::sort.好吧,有了这个并实施,operator ==你可以做所有可能的比较.:)