Как использовать сортировку распределения (сортировку по основанию и т.д.) для сортировки строк?

Question

Я знаю, как использовать сортировку по основанию для сортировки целых чисел.

Но как использовать его для сортировки строк?или числа с плавающей запятой?

Answer 1

Сортировка по основанию или любая другая сортировка распределения может использоваться для сортировки чисел с плавающей запятой, если вы игнорируете некоторые их особенности, такие как бесконечность, значения без числа и два разных представления нуля. IEEE 754-2008 числа с плавающей запятой имеют двоичное представление, совместимое в порядке сортировки с целыми числами.Итак, если вы исключите не-числа и переосмыслите float или double как int32 или int64, вы можете напрямую применить к ним любой вид распределения. Редактировать: Числа с отрицательной плавающей запятой нуждаются в особом обращении (как указал Эшелли), поскольку порядок их сортировки противоположен порядку сортировки целых чисел.

Со строками это сложнее из-за их переменной длины.Может использоваться другой вид сортировки распределения (bucket sort), который часто используется для строк.Для индексации сегментов используются несколько начальных символов строки, затем для сортировки строк внутри сегментов используется любая сравнительная сортировка.

Если все строки имеют почти одинаковую длину и/или используется какой-либо метод для усиления различий между строками (как описано в главе 6 "БЫСТРО:Быстрый поиск по дереву с учетом архитектуры на современных центральных и графических процессорах"), тогда также можно использовать сортировку по основанию:разделите строку на группы символов (или, лучше, на группы битов) одинаковой длины, переинтерпретируйте эти группы как целые числа и продолжайте, как если бы это была сортировка по основанию для целых чисел.

Редактировать: Все виды сортировки по распределению гарантированно будут корректно работать только для строк ASCII.Другие строковые кодировки могут требовать другого порядка сортировки или могут зависеть от параметра "collate" языкового стандарта.

Answer 2

Да, это возможно.

см. см. Radix Сортировка, сортировка поплавка данных для поплавков.Он использует тот факт, что поплавки отказываются к целочисленным типам, сравниваются правильно (после исправления негативов).См. Эта статья для деталей

Для строк вы можете решить проблему с переменной длиной, выполнив сортировку MSD RADIX и обеспечение того, чтобы вы остановились, когда вы столкнулись с нулями.См. Сортировка Radix Реализована в C ++ для строки .