В эти выходные я провел немало времени, читая о различных алгоритмах сортировки. Это было очень интересное чтение, и оно помогло мне больше задуматься о том, что именно влечет за собой сортировка. О сортировке Radix я раньше не слышал, даже мимоходом. Это казалось вполне разумным методом сортировки, поэтому я более подробно изучил его, чтобы попытаться выяснить, почему он ускользнул от моего внимания.
Существует два всеобъемлющих подхода к сортировке по основанию:
Наименее значащая цифра
В этой реализации вы должны начать с сортировки чисел по 10 различным корзинам на основе цифры единиц. В противном случае вы сохраняете исходный порядок чисел, что сокращает количество ненужных операций и делает сортировку стабильной. После завершения этого шага вы сортируете аналогичным образом по цифре десятков и продолжаете эти операции до тех пор, пока не отсортируете по старшей значащей цифре.
Вы можете оптимизировать эту сортировку, заранее разделив список чисел по их длине, а затем выполнив сортировку по основанию для каждого списка отдельно. Это устраняет необходимость обрабатывать весь список, даже если нужно отсортировать только самые длинные числа. С этими оптимизациями поразрядная сортировка будет выполняться за время O(nk), где n — количество элементов, а k — средняя длина. Поскольку вам не нужно сравнивать элементы, сортировка по основанию может быть быстрее в некоторых конкретных приложениях.
Самая значащая цифра
Естественно, вы также можете начать с другого конца со старшей цифры. Процесс аналогичен: вы сортируете объекты по корзинам на основе старшей или крайней левой цифры, а затем рекурсивно сортируете, пока не получите окончательный список. Этот вид чаще используется со строками; вы можете представить себе это как поиск в словаре нужного слова, начиная с первой буквы и сужая на основе каждой последующей буквы, пока слово не будет найдено.
Плюсы и минусы
Сортировка по основанию может быть довольно быстрой, но обычно она полезна только в определенных ситуациях. Они более ограничены, чем другие типы сортов; они лучше всего работают с объектами одинакового размера, и если у вас есть объекты длиннее, чем размер массива, тогда у вас может быть время выполнения хуже, чем O (n²). Они также действительно хорошо работают только для определенных типов объектов, в основном для чисел разных видов и строк. Они довольно ситуативны, но если у вас есть большой список чисел и вы хорошо представляете, как они ограничены, то стоит рассмотреть сортировку по основанию.
