3

有一系列结构

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

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

我知道我可以使用合并排序/快速排序和所有其他众所周知的算法，但是我想知道是否可以添加其他可以加快排序的东西。

4

2 回答 2

6

人们的年龄与用于排序的任意整数有些不同：它具有极少数可能的不同值（所有人的年龄都在 0 到 150 之间）。所以最快的排序方法是分配151个链表（我们称它们为桶）并根据每个人的年龄将每个人的数据结构放入桶中：

bucket[person->age].add(person)
于 2012-10-28T14:34:13.997 回答
4

首先，请注意，即使结构非常大（即长名称），您也不需要使用文件系统排序，您可以使用内存排序，因为

# 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 次迭代
于 2012-10-28T14:34:30.530 回答