Radix Sort By Binary

Question

Я хочу знать, эффективнее ли использовать сортировку Radix с целыми значениями или преобразовывать значения в двоичный, а затем сортировать их.

Может кто-нибудь объяснить мне про и сортировку значений сортировки с использованием сортировки Radix с двоичными числами вместо того, чтобы просто использовать целые числа?

Например, я хочу отсортировать 5 значений. (170, 2, 19, 40, 100)

Используя сортировку radix, как бы Pro и Con могли использовать свои двоичные представления? (010101010, 0010, 010011, 0101000, 01100100)

Answer 1

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

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

Я не совсем уверен, что это означает, что с точки зрения Big О.

Answer 2

Radix сортировки все о сортировке двоичных чисел. К счастью для нас, целые числа также являются двоичными числами (среди - самые двоичные числа).

Другим преимуществом использования двоичной формы является то, что мы можем группировать 10 бит вместо 8 бит, если хотим. Например, для чисел от 0 до 1000000 для группировки/сортировки можно использовать 2 x 10 бит.

Проверьте this на интересное чтение и this для крутой анимации.