Начните с подсчета и сортировки
Сортировка подсчетом — это алгоритм сортировки, который не основан на сравнении элементов, а преобразует элементы сортируемого массива в значение индекса подсчитываемого массива, тем самым косвенно делая сортируемый массив последовательным.
Реализация сортировки подсчетом обычно имеет две формы: сортировка на основе вспомогательного массива и сортировка на основе ведра.
на основе вспомогательного массива
Весь процесс содержит три массива: массив A для сортировки, массив B для подсчета и массив C для вывода.
Проще говоря, это создание массива счетчиков B путем подсчета гистограммы распределения различных значений элементов в массиве A для сортировки, а затем вычисление суммы префиксов массива счетчиков B (этот шаг можно рассматривать как вычисление значения каждого элемента в массиве A для сортировки, информация о положении), и, наконец, присвоить соответствующие элементы выходному массиву C через цикл в обратном порядке, и выходной массив C является окончательным результатом сортировки.
Сортировать по сегментам
На самом деле сортировка ведрами используется для поддержания стабильности, потому что элементы в каждом ведре сортируются в структуре очереди, которая может поддерживать порядок элементов.
Основные шаги:
- Создает указанное количество сегментов на основе разницы между максимальным значением ключа элемента и наименьшим значением ключа и создает очередь в каждом сегменте.
- Пройдите массив для сортировки по порядку и поместите их в очередь соответствующего сегмента.
- Перейдите в порядке номеров корзин и выведите очереди в каждой корзине обратно в исходный массив по порядку.
Недостаточная сортировка подсчета
Видно, что длина вспомогательного массива и количество сегментов определяются максимальным и минимальным значениями.Если разница между ними велика, а массив для сортировки мал, это приведет к большому количеству отходов. вспомогательных массивов или сегментов.
сортировка по основанию
Сортировка по основанию улучшает сортировку подсчетом.Проще говоря, алгоритм сортировки по основанию делит целые числа или строки на разные числа или символы, а затем сравнивает их в соответствии с числами или символами в соответствующих позициях, так что количество вспомогательных массивов или сегментов может быть Уменьшите значение до меньшего и получите окончательный результат сортировки после нескольких циклов сортировки.
Например, для сравнения десятичных значений ниже требуется только 10 сегментов, но необходимо убедиться, что каждый сегмент может соответствовать всем элементам.
Первый этап: поместите элементы в соответствующие корзины для однозначного числа.
Второй этап: поместите элементы в соответствующие корзины для десятизначного числа.
Третий этап: поместить элементы в соответствующие корзины для разряда сотен.
Наконец, отсортированные результаты получаются путем вывода в порядке сегментов.
сортировка ведром
Сортировка сегментов — один из способов улучшить сортировку подсчетом.Основная идея состоит в том, чтобы распределить массив для сортировки по нескольким сегментам, а затем сортировать каждый сегмент по отдельности.Для сортировки в сегментах можно использовать различные алгоритмы, такие как сортировка вставками или Быстрая сортировка — это метод «разделяй и властвуй». После того, как каждое ведро отсортировано, упорядоченная последовательность в каждом ведре окончательно вынимается по очереди, то есть получается полный результат сортировки.
Максимальный и минимальный элементы массива для сортировки равны 19 и 1 соответственно, тогда общий интервал диапазона может быть определен как [0,19].Предполагая, что используются 4 сегмента, интервалы сегментов равны[0,4][5,9][10,14][15,19]. Видно, что количество бакетов можно контролировать в небольшом диапазоне, а емкость бакетов можно динамически расширять.
Поместите элементы в соответствующее ведро в соответствии со значением.
Выведите элементы по порядку в соответствии с порядком ведра, чтобы получить отсортированный результат.
Суммировать
- Сортировку по основанию и сортировку ведра можно рассматривать как обобщенные версии сортировки подсчетом, использующие определенные меры для оптимизации процесса сортировки.
- При сортировке ведрами, когда количество ведер принимает максимальное значение (max-min+1), она становится сортировкой подсчетом, поэтому при сортировке подсчетом это особый случай сортировки ведра.
- Сортировку по основанию можно рассматривать как многораундовую сортировку ведра.Сортировка по основанию основана на значащем бите, и каждый значащий бит подвергается одному раунду сортировки ведра.
- Когда в качестве основания используется максимальное значение, сортировка по основанию вырождается в сортировку по счету.
------------- Рекомендуем прочитать ------------
Зачем писать «Анализ проектирования ядра Tomcat»
2018 Алгоритмы структуры сводных данных
Сборник статей по машинному обучению за 2018 г.
Сводка статей о глубине Java за 2018 г.
Резюме по обработке естественного языка за 2018 г.
Резюме глубокого обучения за 2018 г.
Сводка статей об исходном коде JDK за 2018 г.
Обзор Java Concurrency Core за 2018 г.
Поговори со мной, задай мне вопросы:
Добро пожаловать, чтобы следовать: