在[0,2k]之间对一系列n个数进行排序,每对之间存在:| Ai-Aj |> = k/n

Question

让A1,A2,...,An介于实数[0,2k](k为常数).据了解,对于任何一对Ai,AJ随后|Ai-Aj|>=k/n,

描述在O(n)运行时最坏情况下对数字进行排序的算法.

我知道答案应该是桶式的.无法理解为什么,如果是这样,我如何选择正确数量的水桶？如何在|Ai-Aj|>=k/n实际上帮助？

Answer 1

条件| A _i - A _j | ≥k/ n表示如果将范围[0,2k]划分为2n个不同的桶(每个桶的大小为2k/2n = k/n),则每个范围中最多只能有一个数字(除非可能,否则数据位于存储桶的端点.)如果您更紧密地创建存储桶(例如,通过创建3n存储桶),则每个存储桶的大小小于k/n,因此最多只能包含一个数字.

然后,您可以使用存储桶排序算法对数字进行排序:

• 创建一个3n桶的数组,每个桶代表[(2k/3n)i,(2k/3n)(i + 1))的范围
• 对于每个号码:
  • 将该数字除以(2k/3n)以确定将其放入哪个桶中.
  • 将号码放在该桶中.
• 对于每个桶:
  • 如果该存储桶为非空,请将该存储桶中的数字写入结果数组.

第一步需要O(n)时间,因为您正在创建一个大小为3n的数组.下一步需要时间O(n),因为您每次访问每个O(n)数字并在每一步执行O(1)工作.最后一步还需要O(n)时间,因为你总共访问了3n个桶.

希望这可以帮助!