Да вроде можно даже проще (по крайней мере красивше). Считать старшим "разрядом" порядок числа, а младшими - значащие цифры нормализованной мантиссы....
Везде пишут, что поразрядная сортировка эффективна на целочисленных ключах. Однако, понятно, что любой ключ можно представить как множество "разрядов". Известны ли попытки применения ее к нецелочисленным ключам? Хотя бы к float и string? Интуитивно кажется, что при правильном "разбиении ключа на разряды", результаты должны быть очень неплохими.
Интересная статья. Я вот никогда не понимал, почему стандартные либы для Джавы (и даже С/С++) не имеют реализации поразрядной сортировки (radix sort), которая имеет (уникальную) линейную сложность и на не очень длинных ключах легко бьет все остальные методы.
Да вроде можно даже проще (по крайней мере красивше). Считать старшим "разрядом" порядок числа, а младшими - значащие цифры нормализованной мантиссы....
Везде пишут, что поразрядная сортировка эффективна на целочисленных ключах. Однако, понятно, что любой ключ можно представить как множество "разрядов". Известны ли попытки применения ее к нецелочисленным ключам? Хотя бы к float и string? Интуитивно кажется, что при правильном "разбиении ключа на разряды", результаты должны быть очень неплохими.
Интересная статья. Я вот никогда не понимал, почему стандартные либы для Джавы (и даже С/С++) не имеют реализации поразрядной сортировки (radix sort), которая имеет (уникальную) линейную сложность и на не очень длинных ключах легко бьет все остальные методы.