Разница между сортировкой выбора с массивом и связанным списком?

TL; DR

Сортировка выбора вообще плохая. Сортировка слиянием в общем хороша, но может быть улучшена std::sort для контейнеров с произвольным доступом и функций-членов sort() для узловых контейнеров.

Выбор сортировки масштабируется квадратично

Рассмотрим следующую общую версию selection_sort

template<class ForwardIt, class Compare = std::less<typename std::iterator_traits<ForwardIt>::value_type>>
void selection_sort(ForwardIt first, ForwardIt last, Compare cmp = Compare())
{
for (auto it = first; it != last; ++it) {
auto const selection = std::min_element(it, last, cmp);
std::iter_swap(selection, it);
}
}

На обоих std::array а также std::list длины Nэто имеет O(N^2) сложность: внешний цикл обрабатывает все N элементы, и внутренний вызов std::min_element также имеет линейную сложность, что дает общее квадратичное масштабирование.

Однако, так как сортировка на основе сравнения может быть сделана так же дешево, как O(N log N), это как правило, недопустимое масштабирование для большого N, Как упомянуто @EJP, одна искупительная особенность сортировки выбора — то, что, хотя это делает O(N^2) Сравнения, это только делает O(N) обмен данными Однако для очень больших Nэто преимущество перед большинством O(N log N) алгоритмы сортировки, в конечном итоге будут перегружены O(N^2) стоимость сравнения.

Общий вид слияния на помощь?

Рассмотрим следующую общую версию merge_sort

template<class BiDirIt, class Compare = std::less<typename std::iterator_traits<BiDirIt>::value_type>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare())
{
auto const N = std::distance(first, last);
if (N < 2) return;
auto middle = first + N / 2;
merge_sort(first, middle, cmp);
merge_sort(middle, last, cmp);
std::inplace_merge(first, middle, last, cmp);
}

На обоих std::array а также std::list длины Nэто имеет O(N log N) сложность: глубина рекурсии O(log N) (так как интервал сокращается пополам каждый раз) и призыв к std::inplace_merge имеет линейную сложность, что дает в целом O(N log N) масштабирование.

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

Контейнеры произвольного доступа могут извлечь выгоду из гибридного алгоритма

Контейнеры с итераторами произвольного доступа могут быть дешевле отсортированы с использованием гибридных алгоритмов. std::sort() а также std::stable_sort функции из стандартной библиотеки обеспечивают такие гибридные алгоритмы O(N log N) сложность наихудшего случая. Как правило, они реализуются как IntroSort, который смешивает рекурсивную быструю сортировку с произвольным поворотом с сортировкой кучи и вставкой в ​​зависимости от размера различных рекурсивно отсортированных поддиапазонов.

Контейнеры на основе узлов могут извлечь выгоду из функции-члена sort()

Алгоритмы сортировки, основанные на сравнении, интенсивно используют копирование или обмен исходными данными на что указывают итераторы. Для обычных контейнеров обмен базовыми данными — лучшее, что вы можете сделать. Для узловых контейнеров, таких как std::list или же std::forward_listВы бы предпочли splice: только переставлять указатели узлов и избегать копирования потенциально больших объемов данных. Однако это требует знаний о связях между итераторами.

Это причина того, что std::list а также std::forward_list оба имеют функция-член sort(): у них одинаковые O(N log N) сложность наихудшего случая, но используйте преимущества контейнерного характера на основе узлов.