Я пытаюсь написать код C++ для сортировки по основанию для целых чисел. Посмотрев учебник в Интернете, я обнаружил, что мы должны поместить каждое целое число в нужное ведро, начиная с наименее значащей цифры. Мой вопрос: нужно ли мне 10 сегментов от 0 до 9 в обычном алгоритме для сортировки по основанию? Если я назначу эти сегменты как связанный список (например, *list1 ~~~ *list9), не покажется ли это немного странным?
Спасибо за ваше время. Это не домашнее задание, а просто из любопытства.
Я не думаю, что это вопрос C++ (хотя Radix Sort явно может быть реализован на C++), и, вероятно, он не имеет ничего общего со связанными списками, по крайней мере, не в том смысле, в каком вы об этом думаете: сортировка происходит на поцифровая база, где у вас есть эффективный доступ к корзинам для каждой цифры. Для этого список не подойдет, а вектор подойдет. Внутри каждого сегмента вы можете использовать список.
Что касается количества необходимых вам ведер, то ответ таков: зависит! Вы можете использовать любую целочисленную базу, которая больше 1, и вам потребуется соответствующее количество ведер. Поскольку компьютеры особенно хороши в вычислительной мощности 2, использование степени 2, вероятно, более эффективно, чем использование других оснований, таких как 10, хотя 10 также будет работать. Как ни странно, статья Википедии о сортировке по основанию использует основание 10 — вероятно, чтобы избежать путаницы с бесплатными выбор оснований.
List0поList9. Кроме того, это может быть один, чтобы сделать это. В чем именно заключается ваш вопрос? - person noMAD schedule 03.03.2012