Алгоритм сортировки сегментов повысит производительность вашего приложения
Сортировка сегментов — это алгоритм сравнительной сортировки, который работает с элементами, разделяя их на разные сегменты, а затем сортируя эти сегменты по отдельности.
Он делает предположения о данных, таких как основание и сортировка по подсчету, потому что он делает предположения, а также может сортировать за время O (n).
Лучше всего работает, когда хешированные значения сортируемых элементов распределены равномерно, поэтому коллизий немного.
Значение в сегменте X должно быть больше значений в сегменте X-1 и меньше значений в сегменте X + 1.
Для этапов групповой сортировки:
1. Распределил предметы по корзинам на основе их хешированных значений (этап рассеяния),
2. Рассортируйте предметы в каждом ведре,
3. Объединить ведра — можно просто соединить их (фаза сбора).
Пример:
Мы хотим отсортировать этот массив, используя три этапа, о которых я упоминал выше:
Для своей временной сложности:
A- Не на месте, требуется создание другого массива в памяти.
B- Стабильность будет зависеть от алгоритма сортировки, используемого для сортировки сегментов, в идеале вам нужна стабильная сортировка.
C- Чтобы достичь O (n), он должен иметь только один элемент на ведро, потому что это быстро, когда количество элементов невелико.
В завершение делюсь примером реализации на Github: ее
