Почему нет библиотеки сортировки ведра (или есть?)

cobaltblue спросил: 28 марта 2018 в 03:31 в: algorithm

Я изучал алгоритм и просто наткнулся на эту сортировку. Хотя его можно использовать только в нескольких случаях, он выглядит слишком эффективным, чтобы не реализовываться в стандартной библиотеке, поскольку он может сортировать список в O (n) времени. поэтому мой вопрос заключается в том, почему не существует библиотеки, поддерживающей сортировку в виде ведра, или любой другой алгоритм сортировки, подобный сортировке, такой как сортировка по методу radix на большинстве языков? Я проверил библиотеку java, python и c ++, но не похоже, что он поддерживает любой алгоритм сортировки, отличный от алгоритмов сортировки, основанный на сравнении.
Хотя для реализации такого алгоритма требуется, чтобы список имел целое число в определенном диапазоне, Казалось бы, невозможно реализовать такой метод. Java, например, может иметь интерфейс, подобный Comparator (), который возвращает целое число в заданном диапазоне, которое будет использоваться в качестве индекса для сортировки. Итак, в чем причина, почему алгоритмы сортировки O (n) не используются? Или есть библиотека, которая фактически использует сортировку ковша, которую я только что пропустил? Извините, если это был глупый вопрос, я просто подумал, что должна быть причина, которая делает неиспользуемый алгоритм O (n).


1 ответ

Есть решение
David Eisenstat ответил: 28 марта 2018 в 02:08

В Java есть статический метод Arrays.sort, который в принципе может быть реализован как радикальная сортировка для перегрузок, принимающих целочисленные типы (https://docs.oracle.com/javase/10/docs/api /java/util/Arrays.html#sort (INT [])). Они решили реализовать с быстрой сортировкой. Обоснование не дается, но я представляю, что 1. Для сортировки по Radix требуется дополнительная память, а быстрой сортировки нет 2. Разница между n log n и n сводится к тому, что быстрая сортировка имеет хорошую локальность кэша, а по сортировке по радиусу - меньше.