algorithm - 将一组项目分类到存储桶中的最有效方法是什么？

Question

我有一个任意散列数组，散列元素是一个整数（称为“id”）。我想将这些哈希排序到多个桶中（数组上的常量），其中每个桶是任意范围的“id”（例如 1-10、15-20、20-30）。执行此操作的最佳排序策略是什么？没有嵌套循环可以吗？

Answer 1

如果桶的数量很少，那么使用嵌套循环可能会更好。散列的外部循环，桶的内部循环。 O(n*m).

如果哈希的数量和桶的数量很大，您可以：

hashes = sort(hashes)
buckets = sort(buckets) # sort by lower-bound of bucket
i = 0

foreach (hash in hashes) {
  while (buckets[i].lower_bound > hash) {
    i = i + 1
  }
  bucket[i].add(hash)
}

基本上循环通过哈希将它们添加到当前存储桶并在需要时前进到下一个存储桶。O(n*log(n) + m*log(m))

Answer 2

如果哈希质量好，它们将呈现均匀分布，因此您可以使用均匀分布的桶在一次通过中对集合进行分区。

如果您还希望在桶中对哈希进行排序，请在所有内容都在桶中之后使用正常的排序算法。然而，这将是一种不寻常的哈希使用。（如果您不尝试在存储桶中进行排序，那么“排序”这个词用词不当。您真正想要的是分区。）

Answer 3

您没有提到语言/平台，而是为了提高击键效率（C#）：

        var histogram = new[] { 0, 10, 15, 20, 30, 40 };
        var values = new[] { 12, 14, 5, 6, 7, 1, 34, 26, 17 };
        var bars = values.GroupBy(v => histogram.First(b => v < b));