Может кто-нибудь объяснить мне radix-sort?

Question

Я пытаюсь реализовать radix-sort в javascript. Тем не менее, я не знаю, как сделать radix-sort! У меня есть этот псевдокод (от Введение в алгоритмы):

RADIX-SORT(A, d) 
    for i = 1 to d 
     use a stable sort to sort array A on digit i 

однако, когда он говорит A on digit i, в чем смысл этого?

Answer 1

В сортировке Radix элементы сортируются в соответствии с i^-й цифрой. Он начинает сортировку массива A, просматривая цифру 1, затем 2, ... до цифры d.

Например: А = {423, 241, 732}

Итерация 1 (я = 1): А = {24 , 73 , 42 }

Итерация 2 (я = 2): А = {4 3,7 2,2 1}

Итерация 3 (я = 3): А = { 41, 23, 32} --sorted **

Это занимает линейное время для сортировки массива из n элементов (в зависимости от стабильной сортировки, используемой внутри). Это сортировка по времени O (n + d), где d - количество цифр в элементе.

И мы могли бы использовать любой стабильный сорт (сортировка сортировки или любое другое) для сортировки элементов.