1. Обзор
Алгоритмы сортировки общего назначения, такие как сортировка слиянием , не делают предположений о входных данных, поэтому они не могут превзойти O (n log n)
в худшем случае. Сортировка подсчетом, напротив, имеет предположение о входных данных, что делает его алгоритмом линейной сортировки по времени.
В этом уроке мы познакомимся с механикой сортировки подсчетом, а затем реализуем ее на Java.
2. Сортировка подсчетом
Сортировка подсчетом, в отличие от большинства классических алгоритмов сортировки, не сортирует входные данные путем сравнения элементов. Вместо этого предполагается, что входными элементами являются n
целых чисел в диапазоне [0, k
] . Когда k = O(n),
сортировка подсчетом будет выполняться за время O(n)
.