Какой самый эффективный способ сортировать коллекцию предметов в ведра?

Question

У меня есть массив произвольных хэшей с элементом хеша целого числа (вызовите это «ID»). Я хочу отсортировать эти хэши в ряд ведер (постоянные над массивом), где каждое ведро является произвольным диапазоном «IDS» (например, 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));