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

Сортировка по основанию работает, помещая числа в 1 из 10 «сегментов». Есть 10 «сегментов», потому что есть 10 возможных цифр (0–9). Для реализации вы начинаете с проверки последней цифры каждого числа и помещаете ее в соответствующее ведро. Затем сгладьте массив и повторите со следующей цифрой с конца. Снова сгладьте и продолжайте повторять, пока не будут покрыты все цифры. Это приводит к отсортированной структуре данных. Я пропущу подробное объяснение здесь, так как есть действительно хорошие видео, показывающие, как это работает. Я просто скажу, что это умно.

Это, вероятно, констатирует очевидное, но это работает только со структурами данных, состоящими из чисел.

Рекурсивная реализация

  1. Создайте numContainer, чтобы каждое число можно было поместить в соответствующее ему ведро.
  2. Измененная переменная предназначена для отслеживания завершения процесса сортировки.
  3. Внутри нашего цикла нам нужно получить цифру. Помните, что мы должны начать с последней цифры и двигаться к первой цифре. Если эта цифра окажется неопределенной (индекс доступа меньше 0) или число отрицательное, просто поместите ее в первое ведро (индекс 0). В противном случае поместите его в соответствующее ведро (первая итерация: 593, поместите в numContainer[3]).
  4. Если измененная переменная истинна, мы знаем, что столкнулись с допустимой цифрой. Сгладьте массив numContainer, увеличьте индекс и используйте рекурсию для завершения сортировки. В противном случае, если измененная переменная ложна, мы не видим никаких допустимых цифр. Вернуть сглаженный и отсортированный массив.

Я чувствую, что это краткое решение, легко читаемое и работающее с положительными целыми числами.

Итеративное внедрение

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

Я также чувствую, что итеративную версию легко читать и следовать логике. Это немного более длинное решение, но имеет лучшую космическую сложность.

Временная сложность составляет O(nlogn), что столь же быстро, как и эффективные алгоритмы сортировки сравнением. Последнее, что мне нужно сделать, это добавить некоторую логику для обработки отрицательных целых чисел.