基于年龄的人们首选排序

Question

假设我们有一百个对象'Person'的条目,其中有两个字段'Name','Age'.问题是根据人的"年龄"对条目进行排序.

我在接受采访时被问到这个问题.我回答说我们可以使用一个数组来存储对象并使用快速排序,这样可以避免使用额外的空间,但是面试官告诉记忆不是一个因素.

我的问题是决定使用哪种因素的因素是什么？

还有什么是存储它的首选方式？

在这种情况下,任何排序算法是否优于另一种排序算法,并且会导致更好的复杂性？

Answer 1

此Stackoverflow 链接可能对您有用。

上面的答案已经足够了，但我想从上面的链接添加更多信息。

我正在复制上面链接中答案的一些信息。

我们应该注意到，即使Object中的字段非常大（即长名称）你也不需要使用文件系统排序，你可以使用内存排序，因为

# elements * 8 ~= 762 MB (most modern systems have enough memory for that)
             ^
        key(age) + pointer to struct requires 8 bytes in 32 bits system

尽量减少磁盘访问非常重要 - 因为磁盘不是随机访问，而且磁盘访问比 RAM 访问慢得多。

现在，使用您的选择 - 并避免使用磁盘进行排序过程。

对于这种情况，一些可能性（在 RAM 上）是：

• 标准快速排序或合并排序（您已经想到过）
• 桶排序也可以应用于此处，因为范围限制为 [0,150]（其他人已在此处以计数排序的名称指定）
• 基数排序（出于同样的原因，基数排序将需要 ceil(log_2(150)) ~= 8 次迭代

我想指出内存方面，以防您可能遇到相同的问题，但可能需要考虑内存限制来回答它。事实上，你的限制甚至更少（10^6 与其他问题中的 10^8 相比）。

至于保存的问题——

最快的排序方法是分配 151 个链表/向量（让我们称它们为“桶”或其他任何名称，具体取决于您喜欢的语言），并根据每个人的年龄（所有人的年龄）将每个人的数据结构放入桶中介于 0 和 150 之间）：

bucket[person->age].add(person)

正如其他人指出的那样，桶排序将是您更好的选择。

事实上，桶排序的美妙之处在于，如果您必须对年龄范围（例如 10-50 岁）执行任何操作，您可以根据您的要求对桶大小进行分区（例如每个桶有不同的桶范围） 。

我再次重复一遍，我已从上面给出的链接中的答案中复制了信息，但我相信它们可能对您有用。