Можно представить такую сортировку, которая отработает за 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