Radix Сортировка Плавающих Данных - PullRequest
3 голосов
/ 15 января 2011

Как с помощью radix сортирует данные с плавающей точкой? например, 12.4, 45.13 и т. д. будет ли он сначала читать правую часть десятичной запятой, или сначала левую часть десятичной запятой? сначала читается самым правым первым?

Ответы [ 3 ]

2 голосов
/ 15 января 2011

См. Эту страницу обсуждения этого.

http://codercorner.com/RadixSortRevisited.htm

В основном компьютеры хранят плавающую точку в определенном формате.Они не записывают это как 45.13.В результате, думать об этом таким образом не будет связано с тем, как он на самом деле работает.

Игнорируя это, сортировка Radix должна сначала рассмотреть наиболее значимую часть.В числе с плавающей запятой, что это самые левые цифры.По сути, мы должны дополнить все числа одинаковым количеством цифр перед десятичной точкой.Затем мы читали цифры слева направо.

1 голос
/ 15 января 2011

Радикальная сортировка работает с двоичным представлением числа и сортирует объекты, как если бы они были большим двоичным целым числом.

Для вещественных целых чисел и строк двоичное представление вполне соответствует порядку сортировки, который мысклонны ожидать, и поэтому сортировка по основанию является интересной, хотя и несколько необычной, альтернативой.

Оказывается, что пока плавающее число пересекается в правильном направлении, сортировка по основанию может работать хорошо, за исключением того, что она будет обрабатыватьзнаковый бит в обратном направлении.

Во внутреннем двоичном представлении значения FP имеют знаковый бит, около 10 битов показателя степени, а затем примерно 20 или 50 битов являются «дробью» или мантиссой.

S E E E E E E E E M M M M M M M M M M M M M M M . . .

Показатель степени смещен, поэтому малые значения действительно являются самыми отрицательными показателями, поэтому он сортируется правильно, как и мантисса.

Пока все числа либо положительные, либо отрицательные, или если бит знака сначала инвертируется, а сканирование выполняется слева направо, то я думаю, что сортировка по осям будет работать с числами FP.

0 голосов
/ 25 июля 2011

Лучший код для двойной сортировки по основанию, который я знаю, находится здесь: https://bitbucket.org/ais/usort/src/474cc2a19224/usort/f8_sort.c

...