Почему java не использует радикальную сортировку примитивов?

java.util.Arrays.sort(/* int[], char[], short[], byte[], boolean[] */) реализован в виде «настроенной быстрой сортировки», а не радикальной сортировки.

Некоторое время назад я сравнивал скорость, и с чем-то вроде n> 10000 сортировка по основанию всегда была быстрее. Почему?

Я бы предположил, что:

• Array.sort реализован как быстрая сортировка, потому что быстрая сортировка может привести к сортировке всего за приемлемое время с учетом компаратора.
• Сортировка списка из 10000 записей не так распространена. Доступ к структуре данных из 10000 или более элементов довольно распространен. Если вам нужно поддерживать порядок, сбалансированное дерево поиска часто является лучшим способом, чем сортировка всего массива каждый раз, когда вам нужен наименьший элемент.
• Сортировка примитивов не так распространена, несмотря на то, что университет может преподавать.

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

Back2dos сказал все это, я просто попытаюсь прояснить вопрос, который я считаю наиболее важным:

Radix sort может сортировать только действительные значения примитивов, которые содержатся в массиве, на основе их шаблонов двоичных цифр. В реальных сценариях разработки программного обеспечения этот случай встречается практически никогда . Чаще всего мы делаем сортировку массивов более сложных (не примитивных) структур данных, и иногда мы сортируем массивы индексов по другим объектам.

Теперь массив индексов для других объектов на самом деле является массивом примитивов, но порядок сортировки обеспечивается интерфейсом компаратора (и / или делегатом в C #), который сравнивает не индексы, а объекты, проиндексированные индексами. Таким образом, порядок сортировки не имеет абсолютно никакого отношения к порядку значений примитивов, и поэтому радикальная сортировка абсолютно бесполезна для этого сценария.

Пример:

У нас есть массив строк: [0] = "Mike", [1] = "Albert", [2] = "Zoro". Затем мы объявляем массив индексов для этих строк: [0] = 0, [1] = 1, [2] = 2. Затем мы сортируем массив индексов, передавая ему компаратор, который сравнивает не сами индексы, а фактические строки, на которые ссылаются эти индексы. После сортировки результирующий массив индексов будет выглядеть так: [0] = 1, [1] = 0, [2] = 2. Как вы можете видеть, этот порядок сортировки не имеет ничего общего с двоичными шаблонами значений, содержащихся в массиве, и, тем не менее, перебирая этот массив индексов и выбирая каждую соответствующую строку, мы посещаем строки в отсортированном порядке.