Подтвердить что ты не робот

В чем разница между сортировкой ведра и сортировкой radix?

Сортировка и сортировка ковша - близкие родственники; сортировка ковша идет от MSD до LSD, а сортировка по методу radix может идти в обоих направлениях (LSD или MSD). Как работают оба алгоритма, и в частности, как они отличаются?

4b9b3361

ОТВЕТЫ

Ответ 1

Начальный проход как RadixSort, так и BucketSort точно такой же. Элементы помещаются в buckets (или bins) инкрементных диапазонов (например, 0-10, 11-20,... 90-100), в зависимости от количества цифр наибольшего числа.

В следующем проходе, однако, BucketSort упорядочивает эти "ведра" и добавляет их в один массив. Тем не менее, RadixSort добавляет ведра без дальнейшей сортировки и "re-buckets" на основе второй цифры (десяти) номеров. Следовательно, BucketSort более эффективен для массивов "Плотный", в то время как RadixSort отлично справляется с разреженными (ну, не точно разреженными, но разнесенными) массивами.

Ответ 2

Сортировка ковша и сортировка Radix подобны алгоритмам сортировки сестер, поскольку они не являются сортировками сортировки, и общая идея аналогична. Кроме того, оба они немного абстрактны в реализации.

Radix Sort:

  • Radix означает base (двоичный, восьмеричный, десятичный и т.д.). Поэтому эта сортировка предназначена для чисел (также используемых для строк). Это работает, когда каждый элемент E подобен e k... e 2 e 1 e 0, где e i находится в некотором диапазоне. (обычно 0 на базу, как 0-9 в десятичной или 0-255 в ASCII-символах)

  • Затем он использует k проходов стабильного алгоритма суб-сортировки (он должен быть стабильным, иначе сортировка Radix не будет работать) для сортировки чисел. Этот алгоритм сортировки сортировки обычно относится к сортировке сортировки или сортировке по Bucket, но не может быть самой сортировкой Radix.

  • Вы можете начать с самой значащей цифры или наименьшей значащей цифры, потому что она перемещает каждое число в каждом проходе (от k до 0 или от 0 до k)

  • Это стабильный алгоритм сортировки.

Сорт корзины:

  • Он разделяет массив на меньшие группы или ведра и сортирует их по отдельности, используя алгоритм подсериализации или рекурсивный вызов для себя, а затем объединяет результат. Например, сортировка игроков путем добавления в ведра их команды, затем сортировка их по номерам трикотажа или что-то вроде сортировки чисел от 1-30 до 3 ведер 1-10, 11-20, 21-30.

  • шаг объединения тривиален (в отличие от сортировки слияния). просто скопируйте элементы каждого ведра обратно в исходный массив или присоединитесь к голове каждого ведра с хвостом предыдущего ведра (в случае связанных списков).

  • Radix/base может быть типом/экземпляром группы/ведра при сортировке чисел. Поэтому вы можете подумать о MSD radix как модифицированном экземпляре сортировки ведра

  • Сортировка веток не на месте, а стабильный алгоритм сортировки. Тем не менее, некоторые варианты сортировки ведра могут быть нестабильными (если вы используете алгоритм неполной сортировки, который нестабилен)