Основная проблема с текущим рейтингом ответа заключается в том, что вызов std::distance делает итерацию квадратичной в худшем случае.Последовательность без уникальных ключей приведет к худшему поведению случая, что особенно прискорбно, поскольку именно в этом случае 3-стороннее разбиение предназначено для ускорения.
Это реализует 3-стороннее разбиение Bentley-McIlroy оптимальным образом.для использования с двунаправленными итераторами:
template <typename Bi1, typename Bi2>
Bi2 swap_ranges_backward(Bi1 first1, Bi1 last1, Bi2 last2)
{
typedef typename std::reverse_iterator<Bi1> ri1;
typedef typename std::reverse_iterator<Bi2> ri2;
return std::swap_ranges(ri1(last1), ri1(first1), ri2(last2)).base();
}
template <typename Bi, typename Cmp>
std::pair<Bi, Bi>
partition3(Bi first, Bi last,
typename std::iterator_traits<Bi>::value_type pivot, Cmp comp)
{
Bi l_head = first;
Bi l_tail = first;
Bi r_head = last;
Bi r_tail = last;
while ( true )
{
// guarded to avoid overruns.
//
// @note this is necessary since ordered comparisons are
// unavailable for bi-directional iterator types.
while ( true )
if (l_tail == r_head)
goto fixup_final;
else if (comp(*l_tail, pivot))
++l_tail;
else
break;
--r_head;
while ( true )
if (l_tail == r_head)
goto fixup_right;
else if (comp(pivot, *r_head))
--r_head;
else
break;
std::iter_swap(l_tail, r_head);
// compact equal to sequence front/back.
if (!comp(*l_tail, pivot))
std::iter_swap(l_tail, l_head++);
if (!comp(pivot, *r_head))
std::iter_swap(r_head, --r_tail);
++l_tail;
}
fixup_right:
// loop exited before chance to eval.
if (!comp(pivot, *r_head))
++r_head;
fixup_final:
// swap equal to partition point.
if ((l_tail - l_head) <= (l_head - first))
l_tail = std::swap_ranges(l_head, l_tail, first);
else
l_tail = swap_ranges_backward(first, l_head, l_tail);
if ((r_tail - r_head) <= (last - r_tail))
r_head = swap_ranges_backward(r_head, r_tail, last);
else
r_head = std::swap_ranges(r_tail, last, r_head);
// equal range in values equal to pivot.
return std::pair<Bi, Bi>(l_tail, r_head);
}
Примечание: Это было проверено с использованием пакета проверки Bentley.Приятным побочным эффектом охраняемого аванса является то, что эта функция безопасна для общего назначения (без ограничений на pivot или длину последовательности).
Пример использования,
template<typename Bi, typename Cmp>
void qsort_bi(Bi first, Bi last, Cmp comp)
{
auto nmemb = std::distance(first, last);
if (nmemb <= 1)
return;
Bi pivot = first;
std::advance(pivot, std::rand() % nmemb);
std::pair<Bi, Bi> equal = partition3(first, last, *pivot, comp);
qsort_bi(first, equal.first, comp);
qsort_bi(equal.second, last, comp);
}
template<typename Bi>
void qsort_bi(Bi first, Bi last)
{
typedef typename std::iterator_traits<Bi>::value_type value_type;
qsort_bi(first, last, std::less<value_type>());
}
Хотяприведенная выше сортировка может работать, она иллюстрирует точку, которую уже дал другой ответ, то есть двунаправленные итераторы и быстрая сортировка плохо подходят.
Без возможности выбора приличного центра в постоянное время производительностьхит делает быструю сортировку худшим выбором.Кроме того, двунаправленные итераторы являются слишком общими для оптимальной сортировки в связанных списках, потому что они не могут воспользоваться преимуществами списка, такими как вставка с постоянным временем и объединение.Наконец, еще одна более тонкая (возможно, спорная) проблема заключается в том, что пользователи ожидают, что сортировки в связанных списках будут стабильными.
Моя рекомендация?Восходящая итеративная сортировка, используемая sgi STL.Это доказано, стабильно, просто и быстро (гарантировано n * log (n)).К сожалению, у этого алгоритма нет уникального имени, и мне не удалось найти ссылку на реализацию в отдельности, поэтому он повторяется здесь.
Это очень удобный алгоритм, он работает в некотором родеаналог бинарного счетчика (с непустыми списками, равными единице).Счетчик содержит списки размеров 2 ^ index (то есть 1,2,4,8 ...).При добавлении каждого элемента (бита) может быть инициирован перенос, который будет каскадно добавляться в списки более высокого порядка (двоичное сложение).
template <typename Tp>
void msort_list(std::list<Tp>& in)
{
std::list<Tp> carry;
std::list<Tp> counter[64];
int fill = 1;
while (!in.empty()) {
carry.splice(carry.begin(), in, in.begin());
int i = 0;
for (; !counter[i].empty(); i++) {
// merge upwards for stability.
counter[i].merge(carry);
counter[i].swap(carry);
}
counter[i].swap(carry);
if (i == fill) ++fill;
}
for (int i = 1; i < fill; i++)
counter[i].merge(counter[i-1]);
in.swap(counter[fill-1]);
}
Примечание: Эта версия отличается от оригинала впара способов. 1) Мы начинаем fill с единицы вместо нуля, это позволяет нам пропустить проверку размера и выполнить финальную замену, не влияя иначе на поведение. 2) Исходное условие внутреннего цикла добавляет i < fill, эта проверка является посторонней (вероятно, удержание от версии, где массив счетчиков был динамическим).