Как правило все сортировки сравнивают элементы между собой, однако это не обязательно. Расскажу о двух, которые используются в алгоритмах и в частности в последних JDK при сортировках при определенных сценариях.
Cортировка подсчётом (Counting Sort)
Лучше всего сортировка подсчётом работает при таких условиях:
- массив данных большой
- значения лежат в известном нам диапазоне (например, это диапазон работы какого-то датчика, массивы элементов short, char, byte ... количество магазинов сети)
Принцип следующий - определяется дополнительный массив для подсчета вхождений элементов размером равному диапазону значений. Например, 1млн размер исходного массива из элементов в диапазоне [1, 200] (или пример тип данных short) - длина массива подсчета таким образом будет 200. Проходим по исходному массиву и в соответствующей значению ячейке массива подсчета увеличиваем значение на 1. Т.е. ведется подсчет количества вхождений значения в массив данных. После цикла во вспомогательном массиве подсчета у нас хранятся данные, сколько раз встречается каждый элемент. Далее формируем отсортированный массив, записывая подряд столько раз сколько их частота в массиве подсчета значений. Также возможно сразу дополнительное применение данных для аналитики.
Сортировка не является стабильной, т.е. не сохраняет порядок одинаковых элементов.
Сложность этой сортировки линейная O(n) и она применяется при сортировке в JDK. Например, массива short[] - очень быстро!
Есть еще поразрядная сортировка без сравнения элементов - Radix sort.
Поразрядная сортировка (Radix Sort)
Radix Sort - это линейный алгоритм сортировки, который сортирует элементы по разрядам. Данные сначала группируются по наименьшему разряду, затем по следующему, и так далее, пока не будут учтены все разряды. Важен порядок сбора групп. Накапливать при каждом проходе сведения о группах можно разными способами — например в списках, в деревьях, в массивах, выписывая в них либо сами элементы, либо их индексы.
Порязрядная сортировка эффективна для больших массивов случайных чисел и имеет линейную сложность.
Пример кода на Java
Многократно сортируя элементы по значащим цифрам, от наименее значимых к наиболее значимым, Radix Sort добивается окончательного порядка сортировки. Сложность алгоритма составляет O(d * (n + b)), где d - количество цифр, n - количество элементов, а b - основание используемой системы счисления.
В практических реализациях радиксная сортировка часто оказывается быстрее других алгоритмов сортировки на основе сравнения, таких как quicksort или merge sort, для больших наборов данных, особенно если ключи содержат много цифр.
Для примера из жизни можно привезти то, как большинство людей сортируют колоду игральных карт, раскладывая их на стопки с одинаковыми номиналами, а затем складывая их по порядку и раскладывая на стопки одинаковой масти.
Простой пример как эффективно можно применить RadixSort, это сортировка дат представленных в виде числа подходом по младшему разряду (LSD -Least Significant Digit Radix Sort).
Поскольку целые числа могут использоваться для представления строк (путем хэширования строк в целые числа), то радиксную сортировку можно применять не только с целыми числами, но и с другими типами данных. Существует два основных подхода:
- LSD (Least Significant Digit) Radix Sort: выравнивает записи чисел в сторону менее значащих цифр (по правой стороне, в сторону единиц)
Параметры: O(nk), где n - количество элементов, k - максимальная длина числа.
Свойства: Стабильная, эффективная для чисел с фиксированной длиной. - MSD (Most Significant Digit) Radix Sort: выравнивает в сторону более значащих цифр (по левой стороне, со стороны более значащих разрядов) - строки, числа разной длины. Свойства: зависит от реализации, но часто менее эффективна для коротких данных. Нестабильная, эффективная для сортировки строк, чисел переменной длины.