Время выполнения сортировки Radix

Question

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

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

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

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

Спасибо.

Answer 1

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

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

Answer 2

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