Работает ли сортировка radix с числами, имеющими разное количество цифр?

Я знаю, что сортировка по радиксу работает путем сравнения цифр чисел. Мой вопрос таков: предположим, что у нас есть разные числа с разным количеством цифр. Работает ли здесь radix sort? Мы можем просто предположить, что, например, если мы сравниваем два числа, одно с 3 цифрами и одно с 6 цифрами, первые 3 цифры меньшего числа равны 0. Но как насчет реализации? Как мы можем заставить программу предположить, что если не хватает цифр, то эти цифры равны нулю?

Спасибо ты.

2 3
sorting algorithm radix-sort

2 ответа:

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

Эти 3 числа 

9912
 999
 123

Можно преобразовать в 

9912
0999
0123

И отсортированы с помощью регулярной сортировки по радиксу, либо их можно отсортировать как 2 независимые группы: 

9912

И 

 999
 123

Последнее даст вам (предполагая порядок возрастания) 

 123
 999
И первое остается тем же самым. Затем вы объединяете сортировка групп (от коротких чисел к длинным): 
 123
 999
9912

Вот и все.

2

Если у вас есть число в целочисленной переменной, то вы можете извлечь цифры следующим образом (n = 0, 1, 2, ...): 

digit = (number / radix ^ n) % radix
1