c++ - 在双向迭代器上实现快速排序

Question

使用具有 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);
  }
}

Answer 1

实用库排序函数需要随机访问迭代器的原因有几个。

最明显的一个是众所周知的事实，即如果数据已排序(或“大部分排序”)，则为数据透视选择分区的端点会将快速排序减少到 O(n²) ，所以大多数现实生活中的快速排序实际上使用更健壮的算法。我认为最常见的是 Wirth 算法:选择分区的第一个、中间和最后一个元素的中位数，该算法对已排序的 vector 具有鲁棒性。 (正如 Dieter Kühl 指出的那样，只选择中间元素几乎也能奏效，但三中值算法实际上没有额外成本。)选择随机元素也是一个很好的策略，因为它更难游戏，但对 PRNG 的要求可能令人沮丧。除了采用端点之外的任何选择枢轴的策略都需要随机访问迭代器(或线性扫描)。

其次，当分区很小时(对于小的一些启发式定义)，快速排序不是最优的。当元素足够少时，插入排序的简化循环与引用的局部性相结合将使其成为更好的解决方案。 (这不会影响整个算法的复杂性，因为阈值是固定大小；对于任何先前建立的 k 元素，最多 k 元素的插入排序是 O(1)。我认为您通常会发现值介于 10 和 30 之间。)插入排序可以使用双向迭代器完成，但不能确定分区是否小于阈值(同样，除非您使用不必要的慢循环)。

第三点，也可能是最重要的一点，无论您多么努力，快速排序都可能退化为 O(n²)。早期的 C++ 标准接受 std::sort可能是“平均 O(n log n)”，但由于接受了 DR713标准要求 std::sort是 O(n log n) 没有资格。这不能用纯快速排序来实现，所以现代库排序算法实际上是基于 introsort 的。或类似的。如果该算法检测到分区过于偏向，则该算法回退到不同的排序算法——通常是堆排序。回退算法很可能需要随机访问迭代器(例如，heapsort 和 shellsort 都需要)。

最后，通过使用在最小分区上递归和在较大分区上尾递归(显式循环)的简单策略，递归深度可以减少到最大值 log₂n。由于递归通常比显式维护堆栈更快，并且如果最大递归深度在低两位数时递归是完全合理的，这种小优化是值得的(尽管并非所有库实现都使用它)。同样，这需要能够计算分区的大小。

实际排序的其他方面可能需要随机访问迭代器；这些就在我的脑海中。