Комментарии 6
Два перевода одной статьи 2016-го года появилось с разницей в 12 часов. Интересно!
Я вот тоже удивляюсь, полный перевод уже есть вот тут
https://habr.com/ru/post/597059/
Зачем спешно переводить-публиковать 30% того, что уже переведено - опубликовано?
Неужели вдруг соревнование - кто первый и лучше перевёл? :)))
Поразрядная сортировка - очень хорошая вещь, и я, когда познакомился с этим алгоритмом будучи студентом, тоже был им восхищён. Однако сложность алгоритма не чистая O(n), а O(nw), где n - число сортируемых ключей, а w - длина сортируемых ключей.
Длина же сортируемых ключей зависит от количества ключей - чем больше уникальных ключей, тем больше битов нужно для хранения ключа. И зависимость эта логарифмическая. Т.е. w ~ log n, и в принципе вылезает примерно то же самое O(n log n).
На практике особенности ключей сортировки во многих случаях позволяют, впрочем, этому алгоритму быть лучше других распространённых алгоритмов сортировки. Просто надо помнить, что сложность его вовсе не чистая O(n).
(Скопировал этот комментарий также в обсуждение альтернативного перевода этой статьи: https://habr.com/ru/post/597059/#comment_23855521)
продолжим менять местами первый элемент с другими элементами до тех пор, пока не найдётся элемент, который должен стоять на первом месте. А переходить ко второму элементу можно лишь тогда, когда мы найдём тот элемент, которому предназначено первое место.
Привет, O(n logn)!
Лол прикол.
Че-то мы пропустили второй перевод)
Как я написал алгоритм сортировки, который быстрее std::sort. Часть 1