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

Question

使用时间复杂度为 O(NlgN) 且时间复杂度为 O(lgN) space 的双向迭代器实现快速排序似乎非常简单。那么，std::sort() 需要随机访问迭代器的特殊原因是什么？

我已阅读有关该主题的内容 why do std::sort and partial_sort require random-access iterators?。但它没有解释可能的 std::sort() 实现的哪个特定部分实际上可能需要随机访问迭代器来维持其时间和 space 复杂性。

O(NlgN) 时间和 O(lgN) 的可能实现 space:

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

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

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

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

第三，可能也是最重要的一点，无论您多么努力，快速排序都可能退化为 O(n²)。早期的 C++ 标准接受 std::sort 可能是 "O(n log n) on the average"，但由于接受了 DR713 the standard requires std::sort to be O(n log n) without qualifications. This cannot be achieved with a pure quicksort, so modern library sort algorithms are actually based on introsort 或类似的。如果该算法检测到分区过于偏向，则该算法回退到不同的排序算法——通常是堆排序。回退算法很可能需要随机访问迭代器（例如，heapsort 和 shellsort 都需要）。

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

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

Answer 2

简单的答案是快速排序很慢，除非特别针对小范围进行优化。要检测范围较小，需要一种确定其大小的有效方法。

我有一个演示文稿 (here are the slides and the code)，我在其中展示了用于快速实现快速排序的步骤。原来排序实现其实是一种混合算法

快速 quicksort 的基本步骤如下：

防止[大部分]排序序列。这里有趣的情况之一实际上是由所有相同元素组成的特殊排序序列：在实际数据中，相等的子序列并不罕见。这样做的方法是监视快速排序何时做太多工作并切换到具有已知复杂性的算法，例如 heapsort or mergesort to finish sorting the problematic subsequence. This approach goes under the name introsort.
快速排序在短序列上真的很糟糕。由于快速排序是 divide and conquer algorithm it actually produces many small sequences. Dealing with small sequences can, e.g., be done using insertionsort。要找出一个序列是否很小，有必要有效地检查序列的大小。这就是需要随机访问的地方。
有许多额外的优化是使快速排序变得非常快所必需的，尽管它们的影响总体上小于上述方法的影响。例如：
- 使用的partition需要利用sentinel减少比较次数
- 观察分区是否做任何工作可以通过赌运行插入排序进行早期纾困，该插入排序在做太多工作时停止。
- 使用中点而不是序列的任何一端来增加前一个点被排序的机会，因为枢轴有一个优势（这也需要随机访问，但这是一个相对较小的原因）。

我还没有做过实验，但是为双向迭代器实现这些必要的优化可能并不是真正有效：确定一个序列是否小的成本（不需要获取序列的大小但可以一旦清楚序列不小就停止）可能变得很高。如果快速排序变得受阻运行只慢了大约 20%，那么使用不同的排序算法是更可取的：使用，例如，mergesort 大致在那个范围内并且可以具有它也可以稳定的优点。

顺便说一句，传说中的中位数选择似乎没有任何有趣的影响：使用中间值而不是中位数似乎大致一样好（但它确实是比两端）。

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

Implement quicksort on bi-directional iterators

c++

algorithm

iterator

quicksort

c++-standard-library