Radix Sort

Можно представить такую сортировку, которая отработает за O(n), если у нас на вход идут положительные числа, например, 0..100. Нам нужно всего лишь считать количество входных чисел:
++arr[number];
Где number - это наше число, а arr - хранилище для подсчета.
Таким образом на выходе мы получаем массив отсортированных чисел:

arr[0] = 1; // число 0 встречается 1 раз
arr[1] = 0; // число 1 встречается 0 раз
arr[2] = 5; // число 2 встречается 5 раз
...

Таким образом мы получаем результат такой сортировки:

022222...

Это сортировка подсчетом.

А теперь представим, что у нас числа 0..10000. Массив мы уже не заведем на 10к элементов, мы можем завести разряды, т.е. массив на 10 элементов:

arr = new int[10];

А принцип будет примерно таким же, как и выше, но теперь мы раскладываем числа по разрядам.
Допустим, у нас такие числа:

456 542 123 89 543

Первое что нам нужно сделать - это понять максимальный разряд (его можно передавать в метод сортировки, а можно получать из входных чисел). У нас он будет равен 3.

Ну и сам процесс сортировки:
1. Берем первый разряд и по нему раскладываем числа:

arr[2] = 542
arr[3] = 123 543
arr[6] = 456
arr[9] = 89

2. Теперь у получившихся чисел (542 123 543 456 89) мы берем следующий разряд:

arr[2] = 123
arr[4] = 542 543
arr[5] = 456
arr[8] = 89

3. И последний разряд (123 542 543 456 89) - у 89 мы дописываем 0:

arr[0] = 089
arr[1] = 123
arr[4] = 456
arr[5] = 542 543

Это довольно интересный алгоритм, сложность которого O(n), на практике, наверное, один из самых быстрых, если речь идет о сортировке положительных чисел.

Стоит заметить, что я рассмотрел только LSD (от младшего разряда к старшему) вариант сортировки, существует еще MSD (тоже наркота какая-то) или от старшего разряда к младшему.

#sorting #algorithms