При сортировке по распределению элементы распределяются и перераспределяются по классам, пока массив не будет отсортирован.
В самом общем случае это происходит примерно по той же схеме.
Элементы разбросаны по классам по какому-либо признаку.
Если это не приводит к упорядочению массива, то характеристики принадлежности к классам уточняются и элементы снова раскидываются по уточненным классам.
И так происходит до тех пор, пока массив не станет упорядоченным.
При сортировке по распределению почти всегда отсутствует сравнение элементов друг с другом и их обмены.
Главное – принадлежит ли элемент определенному классу или нет; его сравнение с другими элементами редко имеет значение.
Эти сортировки обычно имеют линейную временную сложность (а не логарифмическую сложность, как в случае эффективных сортировок обмена, слияния, выбора или вставки).
Также алгоритмы этого класса почти всегда требуют много дополнительной памяти, поскольку элементы, сгруппированные по классам, нужно где-то хранить.
Сортировки распределения хороши для упорядочивания целых чисел и строк.
С их помощью обычно неудобно сортировать действительные числа.
Сортировки по распределению также отлично подходят для сортировки массивов, состоящих из повторяющихся чисел: чем больше повторений, тем меньше требуется различных классов.
Рассмотрим алгоритм, наиболее наглядно демонстрирующий указанные выше свойства.
Данная статья написана при поддержке EDISON. Мнение клиента: 10 преимуществ программистов от EDISON Это интересно и полезно знать: завтрак программиста
Сортировка ведром :: Сортировка ведром
Другие названия — сортировка корзиной, сортировка блоками, сортировка карманами.Раскидываем числа по корзинам, затем в каждой корзине раскидываем их по более мелким корзинам и так до тех пор, пока на каком-то уровне в корзине не останутся только одинаковые элементы.
Тогда из таких корзин самого нижнего уровня легко восстановить массив в упорядоченное состояние.
Поясним на конкретном примере.
Допустим, у нас есть неупорядоченный массив.
Мы знаем, что этот массив содержит числа от 1 до 8. 
Разделим эти числа на 2 группы: в одну группу входят числа от 1 до 4, во вторую — от 5 до 8. Затем числа из первой корзины распределим на две корзины: в одной — числа 1 и 2, а в другой — числа 1 и 2. остальные 3 и 4. Эти корзины также распределяем по корзинам, в которых уже есть числа одинакового размера.
Мы применяем аналогичную рекурсию к большой корзине, содержащей числа от 5 до 8. Затем из маленьких корзинок, каждая из которых содержит одинаковые числа, мы возвращаем элементы в основной массив в порядке старшинства.
Сортировка сегментами в этой форме не особенно применима на практике, но она демонстрирует, как в целом работают все сортировки распределения.
Сортировка Таноса :: Сортировка Таноса
Иногда мне присылают авторские сорта и это как раз такой случай.Автор Андрей Данилин назвал это «Русской сортировкой пополам», а я назвал это сортировкой Таноса.
Или, если формально исходить из используемых методов, можно назвать это среднеарифметической сортировкой по корзине.
Вычисляется среднее арифметическое элементов массива, а затем все элементы делятся на 2 группы.
Одна группа содержит элементы меньше (или равные) среднего арифметического, вторая группа содержит элементы больше среднего арифметического.
Затем к обеим группам рекурсивно применяются одни и те же действия — и так до победного конца.
При чем здесь безумный титан? Если это случайный массив, то по большому счету элемент при сравнении со средним арифметическим имеет вероятность 50/50, что он попадет в одну из двух групп.
Кстати, в Интернете я наткнулся на еще один шуточный алгоритм с таким же названием.
Если массив не отсортирован, то щелкаем Перчатку Бесконечности и отправляем в небытие случайно выбранную половину элементов массива.
Если выжившие образуют стройный ряд, то их великую миссию можно считать выполненной.
Если еще нет, то можно сделать еще несколько кликов.
Однако вернемся к нашим сортировкам по распределению.
Всех их можно разделить всего на две группы – сортировка по подсчету И поразрядные сортировки .
Ну а если хотите, то тоже можно выделить подсчет сортов , то есть те, которые можно отнести к обоим.
Существуют и гибридные алгоритмы (это те, которые используют методы разных классов, например, сортировка Тима — нечто среднее между сортировкой слиянием и сортировкой вставками, интроспективная сортировка — быстрая сортировка, переходящая в пирамидальную сортировку и т. д.), включая сортировку распределением, однако , гибриды - это отдельный раздел.
Подробнее о них позже.
Сортировка ведром и сортировка среднего арифметического Таноса являются счетными сортировками.
Сортировка по подсчету
Основная идея заключается в том, что мы подсчитываем, сколько чисел содержится в каждом классе.
Сортировка подсчетом :: Сортировка подсчетом
Мы подсчитываем, сколько раз определенное число встречается в массиве.Зная эти величины, мы быстро формируем уже упорядоченный массив.
Чтобы выполнить эту сортировку, вам нужно знать минимум и максимум в массиве.
Затем генерируются ключи для вспомогательного массива, в котором мы записываем, что и сколько раз произошло.
Код Python:
Теги: #python #Алгоритмы #Визуализация данных #Идеальный код #edisonsoftware #edisonsoftware #edisonsoftware #Сортировкиdef CountingSort(array, mn, mx):
-
Доменное Имя Переоценено И Переоценено
19 Oct, 24 -
Контрастная И Прочная Маркерная Доска.
19 Oct, 24
