Я не уверен, почему бы вам когда-либо использовать сортировку LSD radix.MSD vs LSD radix sort
Преимущества MSD:
Одно из преимуществ сортировки LSD-ради по сортировке по методу MSD - это то, что сортировка LSD-radix является устойчивой сортировкой - если есть несколько элементов для сортировки с одним и тем же ключом, они будут в том же относительном порядке в сортированный вывод при запуске сортировки LSD radix, но не может, если вы используете сортировку radix MSD. Если вы сортируете пары ключ/значение, где ключ является строкой или целым числом, и вы хотите сохранить исходный относительный порядок, сортировка LSD-оснований предпочтительнее по сравнению с сортировкой по методу MSD.
Надеюсь, это поможет!
Почему MSD-редикс не является стабильным алгоритмом сортировки? Даже здесь мы используем метод подсчета (который является стабильным) для сортировки цифр, но с MSB вправо? – Zephyr
@Zephyr Некоторые реализации сортировки по методу MSD - особенно двоичная сортировка по методу MSD - используют нестабильную стратегию разбиения, как то, что делает quicksort. Вы можете сделать это стабильно, но это не требуется. Посмотрите «двоичный quicksort» для получения дополнительной информации об этом. – templatetypedef
Да, верно, что если мы будем использовать quicksort, это будет неустойчиво. Но можете ли вы сказать мне, почему мы не можем использовать сортировку для сортировки элементов, MSB которых одинаково внутри ведра? – Zephyr
@templatetypedef подытожил его красиво.
Сорт MSD radix полезен для сортировки ключей в lexicographic order.
Посмотрите на wikipedia для рабочих примеров и более подробную информацию.
Спасибо anon. Ну, лексикографический порядок для целых чисел - естественный порядок. Я не думаю, что есть разница в том, чего пытаются достичь два варианта сортировки radix. – user1377000
@ user1377000 да, в основном оба выполняют аналогично по целым числам и строкам, при условии, что они начинаются с того же направления. Обычно лексикографическое упорядочение выполняется слева направо, а сортировка по неубывающему порядку осуществляется справа налево. –
Самое большое преимущество сортировки LSD radix для меня - это скорость, потому что это алгоритм без ветвей. Он упрощает сортировку LSD radix для относительно коротких ключей фиксированной длины. Стабильность ЛСД также является приятной особенностью.
Рассмотрите возможность сортировки целых чисел в числовом порядке, а не в строках в лексикографическом порядке. Для более подробных ответов вы должны, вероятно, попробовать http://cstheory.stackexchange.com/ – beaker
@ beaker- cstheory.stackexchange.com для вопросов CS на уровне исследований. Я не думаю, что это было бы уместно. – templatetypedef
@templatetypedef Плохая работа по вырезанию и вставке, извините. Я отправился на http://cs.stackexchange.com/, который по какой-то причине не появляется в удобном списке внизу страницы. – beaker