Radix sort теоретически очень быстр, когда вы знаете, что ключи находятся в определенном ограниченном диапазоне, скажем, например, значений в диапазоне . Если вы просто конвертируете значения в базу что занимает время , выполните сортировку по основанию и затем преобразуйте обратно в исходную базу для общего алгоритма .
Тем не менее, я читал, что на практике сортировка по основанию обычно медленнее, чем, например, рандомизированная быстрая сортировка :
Для больших массивов сортировка по основанию имеет наименьшее количество команд, но из-за относительно низкой производительности кеша ее общая производительность хуже, чем у оптимизированных по памяти версий mergesort и quicksort.
Радикальная сортировка - это всего лишь хороший теоретический алгоритм, или она имеет практическое применение?
источник
vector
). Но я не знаю, так как я не читал газеты Ламарки.@ Роберт: Ваша ссылка довольно удивительна (на самом деле я не смог найти цитируемое предложение). Мой личный опыт - для случайного ввода, сортировка по основанию намного быстрее, чем STL
std::sort()
, который использует вариант быстрой сортировки. Раньше я делал алгоритм на 50% быстрее, заменяяstd::sort()
нестабильную сортировку по основанию. Я не уверен, что такое «оптимизированная для памяти версия» быстрой сортировки, но я сомневаюсь, что она может быть в два раза быстрее, чем версия STL.Этот пост оценил сортировку по основанию, а также несколько других алгоритмов сортировки. Вкратце, в этой оценке
std::sort()
для сортировки 50 миллионов целых чисел требуется 5,1 с, тогда как сортировка по месту / нестабильному основанию занимает 2,0 с. Стабильная сортировка по основанию должна быть еще быстрее.Radix sort также широко используется для стабильной сортировки строк. Иногда встречаются варианты радикальной сортировки для построения массивов суффиксов, BWT и т. Д.
источник
Radix sort также является естественным способом сортировки слов фиксированной длины по фиксированному алфавиту, например, в алгоритме Kärkkäinen & Sanders ( http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf )
источник