tgoop.com/the_algorithms/4568
Create:
Last Update:
Last Update:
Голубиная сортировка
Алгоритм сортировки, который подходит для сортировки списков элементов, в которых количество элементов и количество возможных значений ключа примерно одинаковы.
Работа алгоритма:
Шаг 1: Найдите минимальное (min) и максимальное (max) значения в массиве. Также найдите range
как «max-мin+1
».
Шаг 2: Создайте массив изначально пустых «ячеек» того же размера, что и диапазон.
Шаг 3: Посетите каждый элемент массива, а затем поместите каждый элемент в свою ячейку. Элемент arr[i]
помещается в ячейку с индексом arr[i] – min
.
Шаг 4: Запустите цикл по всему массиву ячеек по порядку и поместите элементы из непустых ячеек обратно в исходный массив.
Сложность: O(n+range)
BY Алгоритмы и структуры данных

Share with your friend now:
tgoop.com/the_algorithms/4568