按年龄对一组人进行排序的最快方法是什么？

Question

有一系列结构

struct
{
string name;
string 2nd_name;
int age; // 0 to 150
}

最大数组的长度为10 ^ 8.

我知道我可以使用mergesort/quicksort和所有其他众所周知的算法,但是我想知道是否可以添加其他可以加快排序的东西.

Answer 1

人们的年龄与排序的任意整数有所不同:它具有非常少的可能的不同值(所有人的年龄在0到150之间).所以最快的排序方法是分配151个链表(让我们称之为桶),并根据他/她的年龄将每个人的数据结构放入桶中:

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