Есть ли в C++ Algorithm/Boost Lib сортировка по основанию?

Я хочу сортировать целые числа, и я знаю, что сортировка по основанию должна быть отличной для этого. Любая реализация библиотеки для такого рода?


c++ sorting algorithm radix-sort
person AyBayBay    schedule 21.01.2014    source источник
comment
В теме здесь упоминается, что кто-то написал один, но он ожидает рассмотрения. Однако я не знаю, сделал ли он это в Boost.   -  person Yuushi    schedule 21.01.2014
comment
@AyBayBay Я думаю, что Джереми В. Мерфи правильно ответил на вопрос. Не могли бы вы принять его ответ или объяснить, почему это неприемлемо?   -  person Jonathan Mee    schedule 02.12.2014
comment
@Yuushi Кажется, это было принято в 1.58   -  person sehe    schedule 19.04.2015
comment
Не в Boost или стандартной библиотеке, но вам может понравиться ska_sort, который представляет собой точно настроенную гибридную систему счисления. сортировка с поддержкой проекций: при необходимости вы можете написать ska_sort(vec.begin(), vec.end(), [](const auto& value) { return value.foo; }); тоже sort в определенном поле foo.   -  person Morwenn    schedule 01.10.2017

Ответы (2)


arrow_upward
2
arrow_downward

Зависит от того, насколько строго вы определяете сортировку по основанию, поскольку Boost 1.58.0 включает сортировку по спреду, представляющий собой гибридный алгоритм сортировки, эвристически сочетающий в себе групповую и сравнительную сортировку.

Для сортировки целых чисел и без требований к эффективности Θ(n) в наихудшем случае Spreadsort должен удовлетворить вас.

В качестве аргумента вы также можете взглянуть на мою реализацию сортировки по основанию LSD , что довольно неэффективно с памятью, но иногда быстрее, чем Spreadsort. Вам нужна только ветка radix_sort, но я связался с веткой speed_test, потому что у нее есть файл readme.

person Jeremy W. Murphy    schedule 06.05.2014

arrow_upward
2
arrow_downward

Более актуальным ответом будет Да, так как в версии 1.58 это так:

У него есть что-то известное как SpreadSort, и он «волшебным образом» обнаружит оптимизированные пути для таких типов, как std::string, или чисел с плавающей запятой, которые можно рассматривать как массивы байтов.

person sehe    schedule 19.04.2015
comment
Оптимизирует ли он что-то вроде сравнения в структурной операции‹(T&const a, T&const b){return a.x‹b.x}? Если нет, есть ли какая-нибудь библиотека для этого? - person l4m2; 30.09.2017
comment
@ l4m2 это не автоматически, но да, вы можете убедить его сделать это. - person Marc Glisse; 30.09.2017
comment
@ l4m2 Я был не в себе, но кто-то уже добрался до этого: chat.stackoverflow.com/transcript/message/ 39400351#39400351 Большое спасибо @ Морвенн, некоронованному королю cppsort - person sehe; 30.09.2017
comment
Вот целочисленная адаптация того же coliru.stacked-crooked.com/a/740fe1a67521d5cb @l4m2 - person sehe; 01.10.2017