Базовая сортировка

предисловие

Запущена новая серия «Глядя на картинки, чтобы легко понять структуры данных и алгоритмы», в основном с использованием изображений для описания общих структур данных и алгоритмов, которые легко читать и понимать. В эту серию входят десятки куч, очередей, списков, деревьев, графов, сортировки и так далее.

сортировка по основанию

Алгоритм Radix Sort — это алгоритм несравнительной сортировки, который Герман Холлерит использовал в счетных машинах для перфокарт еще в 1887 году. Обычно он используется для сортировки целых чисел, но поскольку целые числа и определенные символы могут быть преобразованы друг в друга, его также можно использовать для сортировки строк. Проще говоря, алгоритм сортировки по основанию состоит в том, чтобы разделить целое число или строку на разные числа или символы, а затем сравнить их по числам или символам в соответствующих позициях.

стабильность

Сортировка по основанию стабильна, то есть она может гарантировать, что относительный порядок между элементами одного и того же значения непротиворечив до и после сортировки. Метод сортировки, основанный на количестве, в основном заключается в выполнении операции суммирования префиксов в массиве счетчиков, а также в дополнительном вспомогательном массиве и, наконец, в помещении всех элементов массива для сортировки во вспомогательный массив в цикле обратного порядка для достижения стабильности. эффект. Подход на основе сегментов обеспечивает стабильность за счет управления порядком в каждом сегменте.

временная сложность

Временная сложность для сортировки по основанию Ο (w (n + k)), где n — длина сортируемого массива; диапазоны ключа K — равные двоичные числа, например, десятичное число k = 10; w — сортируемый массив элементы максимальной длины слова, элементы максимальной длины слова, такие как358, длина слова равна 3.

Когда k определено, временная сложность фактически равна O(wn), но иногда необходимо учитывать длину слова w, которую нельзя просто рассматривать как константу. Если основание равно B (то есть основание B), а наибольший элемент сортируемого множества равен N, то w больше, чем log_B N наименьшее целое число. Следовательно, это не означает, что сортировка по основанию обязательно лучше, чем сортировка методом наилучшего сравнения (O(n * log n)). Фактический процесс также связан с конкретной ситуацией взятой базы и сортируемого множества.

Сортировать по

Поразрядная сортировка может использовать наиболее значащую цифру (MSD) и наименее значащую цифру (LSD) двумя способами, где метод сортировки LSD начинается с самого правого значения ключа, а метод сортировки MSD противоположен, начиная с самого левого из ключевое значение.

В процессе алгоритма для LSD после выделения значащей цифры необходимо выполнить слияние, а затем выделить следующую цифру, для MSD после выделения значащей цифры слияние не выполняется, и оно будет продолжаться для выполнения одной и той же старшей цифры Элементы продолжают распределяться до тех пор, пока не будет выполнена операция слияния, когда дальнейшее распределение невозможно.

Реализация на основе ведра

Метод на основе сегментов относится к использованию сегментов в качестве вспомогательного инструмента.В процессе циклически повторяется каждая значащая цифра для распределения элементов по соответствующим сегментам, тем самым реализуя сортировку по основанию.

Этапы операции поразрядной сортировки на основе ведра следующие:

Определите количество ведер, определяется количеством сумм, таких как количество трубок 10, представляют от 0 до 9, а структура в каждом ведре представляет собой очередь.
Шаги с 3 по 5 выполняются для каждого значащего бита, от младшего значащего бита до самого старшего значащего бита.
Пройдите массив для сортировки по порядку, назначив их в очередь соответствующего сегмента в соответствии с текущим допустимым битом.
Перейдите в порядке номеров корзин и соберите очереди в каждой корзине в исходный массив по порядку.
Выберите следующий допустимый бит и выполняйте шаги со 2 по 4, пока не будут обработаны все допустимые биты и результат не станет окончательным.

То же самое нужно выполнить операцию сортировки по основанию, основанную на методе ведра, на основе общих баллов предыдущих 8 учеников начальной школы. Всего 8 студентов, поэтому длина сортируемого массива равна 8. И поскольку используется десятичное число, диапазон индекса корзины составляет 0–9. Кроме того, для каждого сегмента создается очередь, здесь предполагается, что длина очереди равна 5, а длина может быть и длиной сортируемого массива, но на практике больше используются стратегии динамического расширения.