Как использовать сортировку рассылки (radix sort и т. Д.) Для сортировки строк? - PullRequest
4 голосов
/ 09 марта 2012

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

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

Ответы [ 2 ]

4 голосов
/ 09 марта 2012

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

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

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

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

3 голосов
/ 10 марта 2012

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

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

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

...