你怎么做双层排序？ [英] How do you do a double layered sort?

问题描述

我需要先按文档名称排序一堆元素，然后按文档内部人员的年龄排序。



sort（vec.begin（） ，vec.end（），ltNames）;



或者我可以将名称更改为此吗？ documentname + age然后只使用ltNames？



我会得到



agedpeople67

agedpeople68

agedpeople99

youngpeople1

youngpeople2

youngpeople3



会起作用吗？

I need to sort a bunch of elements first by document name and then by the age of the people inside the document.

sort(vec.begin(), vec.end(), ltNames);

or can i change name into this? documentname+age and then just use ltNames?

I would get

agedpeople67
agedpeople68
agedpeople99
youngpeople1
youngpeople2
youngpeople3

would that work?

推荐答案

你看过基数排序一词了吗？这是按字母顺序排序的基础，听起来你需要有两种 - 一种用于字母，一种用于数字。



优势对于基数排序是一个好的算法保持从前一种排序的排序 - 在你的情况下，当你按年龄排序时，必须保持按字母顺序排序。



Rosetta Code 中有一个很好看的C ++实现，您应该可以修改它。



您正在考虑的实现可能会因大量值而失败。例如，如果您有一个年龄为1,2,10,20的老年人列表，您的列表可能如下所示：



agedpeople1

agedpeople10

agedpeople2

agedpeople20



这是我所理解的正确顺序。

Have you looked under the term "Radix sort"? This is the basis behind alphabetical sorting, and it sounds like you need to just have two sorts--one for alphabetical, then one for numeric.

The advantage of going for a Radix sort is that a good algorithm maintains the sort from the previous sort--in your case, the alphabetized sort must be maintained when you go with the age sort.

There is a nice looking C++ implementation here at Rosetta Code that you should be able to modify.

The implementation you are thinking of will probably fail for a good number of values. For example, if you have an agedpeople listing with ages of 1,2,10,20, your list will probably look like this:

agedpeople1
agedpeople10
agedpeople2
agedpeople20

which is not the correct order from what I understand.

人们不仅想要对对象的单个属性进行排序，而且要对多个属性进行排序是很常见的。这甚至可以在单个排序运行中完成。诀窍是使用适当的比较函数。



比较函数告诉排序算法，一个元素是在特定的其他元素之前还是之后。在你的情况下，这意味着你应该实现一个比较功能，排名



aaa1 aaa2

aaa1 aaa10
$ b在aaa10之前$ b aaa2

...

aaa99在bbb1之前



等等。要实现这样的比较功能，您应该将两个键放入一个结构中（而不是将它们连接成一个字符串）。例如：

It is quite common that one want to sort not only by a single, but multiple properties of an object. This can even be done in a single sorting run. The trick is to use an appropriate compare function.

The compare function tells the sorting algorithm, whether one element comes before or after a particular other element. In your case that means that you should implement a compare function that ranks

aaa1 before aaa2
aaa1 before aaa10
aaa2 before aaa10
...
aaa99 before bbb1

and so forth. To implement such a compare function you should put your two keys into a structure (instead of concattenating them to a string). For example:

struct SortKey
{
   string docName;
   int    age;
};

然后创建排序键的向量，例如：

Then create a vector of your sort keys, something like:

    vector<sortkey> keys;
</sortkey>

最后你需要比较功能，它看起来像：

And finally you need the compare function, which would look like:

bool MyCompFunction (const SortKey& a, const SortKey& b)
{
    return a.docName < b.docName || a.docName == b.docName && a.age < b.age;
}

换句话说：如果其docName小于b，或者docNames相等且a的年龄较小，则元素a出现在b之前比b更好。



现在你可以在你的向量上调用sort并指定你自己的比较函数：

In other words: Element a comes before b if either its docName is smaller than b's, or if the docNames are equal and the a's age is smaller than b's.

Now you can call sort on your vector and by specifying your own compare function:

sort (keys.begin(), keys.end(), MyCompFunction);

这篇关于你怎么做双层排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！