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

Question

让是（k 是常数）A1,A2,...,An之间的实数。[0,2k]众所周知，对于任何一对Ai,AJthen |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 个存储桶。

希望这可以帮助！