Реализация сортировки ведра
Я должен реализовать сортировку ведра так, чтобы он сортировал массив с size = 100 со случайно сгенерированными числами от 0 до 100. Мои корзины следующие:
Bucket0: (0<=x<10)
Bucket1: (10<=x<20)
.
.
.
Bucket9: (90<=x<100)
Теперь я понимаю теорию, лежащую в основе сортировки сегментов, когда я вставляю элементы в каждый отдельный сегмент, но не понимаю, как на самом деле создавать сегменты. Должен ли я создать массив сказать B с ведрами, являющимися самими массивами? Или это более стандартный способ реализации сортировки с целыми числами?
Мне просто нужно подтолкнуть в правильном направлении, спасибо за любую помощь!
Решение
Да.
Вы должны объявить другой массив (мы можем сказать b) с длиной 101. Длина представляет и диапазон наших чисел.
Теперь вам нужно перебрать первый массив и для каждой ячейки, и когда вы найдете каждое число k (0 <= к <= 100), вы должны ++ b [k]. Что-то вроде: b[a[i]]++;
Теперь у нас есть массив b который представляет, сколько раз каждое число k появился в первом массиве. Мы можем переопределить первый массив:
for(int i = 0; i <= RANGE; i++)
for(int j = 0; j < b[i]; j++)
a[p++] = i;
В то время как в вашем случае, ДИАПАЗОН 100.
Сложность: O (n)
Обратите внимание, что мы можем реализовать это с одной переменной вместо использования массива, который делает то же самое, но каждый раз для другого числа.
Не много экономит, но немного экономит Сложность пространства.
Другие решения
Других решений пока нет …