使用具有O(NlgN)时间和O(lgN)空间的双向迭代器来实现快速排序似乎很简单。那么，std::sort()需要随机访问迭代器的特殊原因是什么？
我已经阅读了有关why do std::sort and partial_sort require random-access iterators?的主题。但是，它没有说明可能的std::sort()实现的哪个特定部分实际上可能需要随机访问迭代器来维持其时间和空间复杂性。
O(NlgN)时间和O(lgN)空间的可能实现:
template <typename BidirIt, typename Pred>
BidirIt partition(BidirIt first, BidirIt last, Pred pred) {
while (true) {
while (true) {
if (first == last) return first;
if (! pred(*first)) break;
++first;
}
while (true) {
if (first == --last) return first;
if (pred(*last)) break;
}
iter_swap(first, last);
++first;
}
}
template <typename BidirIt, typename Less = std::less<void>>
void sort(BidirIt first, BidirIt last, Less&& less = Less{}) {
using value_type = typename std::iterator_traits<BidirIt>::value_type;
using pair = std::pair<BidirIt, BidirIt>;
std::stack<pair> stk;
stk.emplace(first, last);
while (stk.size()) {
std::tie(first, last) = stk.top();
stk.pop();
if (first == last) continue;
auto prev_last = std::prev(last);
auto pivot = *prev_last;
auto mid = ::partition(first, prev_last,
[=](const value_type& val) {
return val < pivot;
});
std::iter_swap(mid, prev_last);
stk.emplace(first, mid);
stk.emplace(++mid, last);
}
}
最佳答案
实用的库排序功能需要随机访问迭代器有几个原因。
最明显的一个事实是众所周知的事实，即如果对数据进行排序(或“大部分已排序”)，则为数据透视图选择分区的端点会减少快速排序为O(n2)，因此大多数现实生活中的快速排序实际上使用的是健壮的算法。我认为最常见的是Wirth算法:选择分区的第一个，中间和最后一个元素的中值，这对排序的 vector 是稳健的。 (正如DieterKühl指出的那样，仅选择中间元素几乎也可以工作，但是对于三位数中值算法几乎没有额外的成本。)选择随机元素也是一种不错的策略，因为这样做比较困难游戏，但对PRNG的要求可能会令人沮丧。选择端点以外的任何其他枢轴策略都需要随机访问迭代器(或线性扫描)。
其次，当分区较小时(对于较小的启发式定义)，快速排序次优。当元素不足时，插入排序的简化循环结合引用的局部性将是一个更好的解决方案。 (这不会影响整个算法的复杂性，因为阈值是固定大小；对于任何以前建立的k，最大k元素的插入排序为O(1)。我认为您通常会发现介于10和之间的值30.)插入排序可以使用双向迭代器来完成，但是要弄清楚分区是否小于阈值则不能(同样，除非使用了不必要的慢循环)。
第三，也是最重要的一点是，无论您多么努力，快速排序都可以退化为O(n2)。较早的C++标准接受std::sort可能平均为“O(n log n)”，但是由于接受DR713，因此该标准要求std::sort不得为O(n log n)。单纯的快速排序是无法实现的，因此现代的库排序算法实际上是基于introsort或类似的。如果该算法检测到分区过于偏向，则会退回到另一种排序算法(通常是堆排序)。后备算法很可能需要随机访问迭代器(例如，heapsort和shellsort都需要)。
最后，通过使用在最小分区上递归并在较大分区上进行尾递归(显式循环)的简单策略，可以将递归深度减小到最大log2n。由于递归通常比显式维护堆栈要快，并且如果最大递归深度在两位数以内，则递归是完全合理的，因此这种小的优化是值得的(尽管并非所有库实现都使用它。)再次，这要求能够计算分区的大小。
实际排序中可能还有其他方面需要随机访问迭代器。这些只是我的头上。