Radix сортировки запустить время

Question

Если мы имеем некоторый м> 0 и необходимо предоставить алгоритм для сортировки п целых чисел в диапазоне от 0 до п^т -1 за время O (млн). Мое предложение:

Radix-Sort(A,t) // t is the digit length 
for i=0 to t 
    do Insertion-Sort A on digit i 

Мой аргумент, что выше будет работать в O (млн), потому что для каждой цифры т - Вносимые рода будет принимать O (N) времени, так как диапазон для каждого прогона мал.

Это правильное предложение? Каково должно быть требование пространства выше?

Спасибо.

Answer 1

Требование к пространству - это O (m + n), потому что вам нужны исходные числа и m ведра для размещения n элементов. Время выполнения - O (mn), которое может быть >> n, что является проблемой с сортировкой radix. Во всех случаях его O (mn), но проблема в том, что если m> n, вы получаете нечто большее, чем O (n^2). В зависимости от того, как это записано, память может также быть O (mn) в худшем случае, потому что вы создаете m копий набора из n чисел для сортировки.

Answer 2

Его лучше использовать Counting sort при сортировке дискретных чисел небольшого диапазона, следовательно, он гарантирует линейность поиска по размеру данных и их диапазону (сортировка вставки сортирует сортировку с O(n^2) наихудшая сложность корпуса , но если данные были отсортированы в противоположном направлении, малый диапазон, скорее всего, поможет вам с сортировкой вставки, потому что каждый элемент будет перемещен).

Сложность пространства при использовании сортировки подсчета будет O(n+k), где n - размер массива, а k - диапазон данных. Вы можете использовать тот же массив для сортировки и возврата результата, потому что вы сортируете примитивные данные.