Выбор правильного «ковша» для ковша Сортировка

Question

Я собираюсь выполнить сортировку в ковше, я принимаю параметр int, и я хотел вставить его в «ковш» узла, который вмещает до 8 ints. Как только int находится в массиве в узле, я буду выполнять упорядоченный поиск, чтобы они были в порядке возрастания. Мой вопрос в том, как выбрать правильный «ведро» узла для вставки этих значений int? Я вообще думаю, что для сортировки в Bucket вам дается количество ведер, но я не уверен, что делать в моем случае.

я что-то вдоль линий мышления: (чтобы увидеть, если мой Bucket полон)

if(array[max] != 0) 
{ 
    array[size] = element; 
    size++; 
} 
else 
{ 
    int[] newArray = new int[max]; 
    newArray[newSize] = element; 
    newSize; 

} 

Но тогда я буду иметь, чтобы, если другого заявления на срок до 5000 вставлено значения. Любая идея, как выбрать правильное «ведро»?

Answer 1

В сортировке ковша каждому ковшу выделяется поддиапазон возможных значений ключа, часто основанный на значении бит высокого порядка ключа. Каждый входной элемент помещается в ведро для поддиапазона, в котором он падает. Каждый из ковшей сортируется отдельно, а затем конкатенируется, чтобы получить отсортированный результат. См. Bucket Sort для визуализации.

Каждое ведро должно быть сконструировано таким образом, чтобы оно содержало максимально возможное количество элементов, которые могли бы отображаться на нем. Вы ничего не можете сделать, чтобы завершить сортировку, если ведро «полно». Если у вас 1000 ведер, и каждый ковш должен содержать не более 8 элементов, ваши ключи ввода должны быть ограничены 8000 элементами поддиапазона целых чисел.

У вас должно быть простое арифметическое выражение на основе значения ключа, которое дает номер ведра для этого ключа. Например, если сортировка элементов из [0,7999] с использованием 1000 ведер, вы можете разделить ключ на 8 и округлить до целого. Часто количество ведер - это мощность в два, а номер ведра для ключа - это всего лишь соответствующее количество бит высокого порядка от ключа.