Пример реализации на С++:
Сложность
|
Лучшее
|
Среднее
|
Худшее
|
Время
|
O(n log n)
|
O(n log n)
|
O(n log n) или O(n) (при одинаковых ключах)
|
Память
|
|
|
O(1)
|
Сортировка подсчётом / Counting sort
Сортировка подсчётом - это алгоритм, основанный на подсчёте повторяющихся элементов в массиве.
Общая идея алгоритма (простой вариант):
Есть массив A длиной n элементов, который нужно отсортировать. Создаётся вспомогательный массив C с индексами от 0 до k (максимальное значение в массиве A) и заполняется нулями.
Последовательно проходим по массиву A и записываем в C[i] количество чисел, равных i. Таким образом индексы в массиве C - это значения массива A, а значение в массиве C - это то, сколько раз это число повторяется в массиве A.
Проходим по массиву C и переносим значения в массив A.
Пример реализации на Kotlin:
fun countingSort(array: IntArray) {
if (array.isEmpty()) return
// вычисляем минимальное и максимальное значение в массиве
val min = array.min()!!
val max = array.max()!!
// создаём вспомогательный массив, все элементы которого == 0
val count = IntArray(max - min + 1)
// подсчитываем числа и записываем во вспомогательный массив
for (number in array) count[number - min]++
// переносим значения в первоначальный массив
var z = 0
for (i in min..max)
while (count[i - min] > 0) {
array[z++] = i
count[i - min]--
}
}
Достарыңызбен бөлісу: |
