Radix Sort в C ++

Question

Я пытаюсь написать код C ++, чтобы выполнить радикальную сортировку для целых чисел.Посмотрев учебник в Интернете, я обнаружил, что мы должны поместить каждое целое число в нужное место, начиная с наименее значимой цифры.Мой вопрос: мне нужно 10 блоков от 0 до 9 в обычном алгоритме для сортировки по основанию?Если я назначу эти группы в виде связанного списка (например, * list1 ~~~ * list9), это будет немного странно?

Спасибо за ваше времяЭто не домашняя работа, а просто из любопытства.

Answer 1

Я не думаю, что это вопрос C ++ (хотя Radix Sort явно может быть реализован в C ++), и он, вероятно, не имеет ничего общего со связанными списками, по крайней мере, не так, как вы думаете об этом:сортировка происходит на основе цифр, где у вас есть эффективный доступ к корзинам для каждой цифры.Для этого список не будет работать слишком хорошо, но вектор будет работать.Внутри каждого сегмента вы можете использовать список.

Что касается нужного вам количества сегментов, ответ таков: это зависит!Вы можете использовать любое целое основание, которое больше 1, и вам потребуется соответствующее количество ведер.Поскольку компьютеры особенно хороши в вычислительных мощностях 2, использование степени 2, вероятно, более эффективно, чем использование других баз, таких как 10, хотя 10 также будет работать.Как ни странно, в статье Википедии о Radix Sort используется база 10. Вероятно, чтобы избежать слишком большого замешательства по поводу свободного выбора баз.