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

Question

使用具有O(NlgN)时间和O(lgN)空间的双向迭代器来实现快速排序似乎非常简单.那么,std::sort()需要随机访问迭代器的特殊原因是什么？

我已经读过有关为什么std :: sort和partial_sort需要随机访问迭代器的主题？.但它没有解释可能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算法:选择分区的第一个,中间和最后一个元素的中值,这对于有序矢量是稳健的.(正如DieterKühl指出的那样,只选择中间元素几乎也可以工作,但三元算法的中位数实际上没有额外的成本.)选择一个随机元素也是一个很好的策略,因为它更难对游戏而言,对PRNG的要求可能令人沮丧.除了获取端点之外,任何选择枢轴的策略都需要随机访问迭代器(或线性扫描).

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

第三,也许最重要的是,无论你怎么努力,快速排序都可以退化为O(n ²).早期的C++标准接受的std::sort可能是"O(n log n)平均值",但自从接受DR713以来,标准要求std::sortO(n log n)没有资格.使用纯粹的快速排序无法实现这一点,因此现代库排序算法实际上是基于内部或类似的.如果算法检测到分区过于偏向,则该算法会回退到不同的排序算法 - 通常为heapsort.回退算法很可能需要随机访问迭代器(例如,heapsort和shellsort都需要).

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

实际分类的其他方面可能需要随机访问迭代器; 那些只是我的头脑.