c++ - std::partition 调用两次以进行快速排序

Question

来自 http://en.cppreference.com/w/cpp/algorithm/partition 的示例中对 std::partition 的两次调用背后的逻辑是什么？ ？我理解快速排序算法的高级设计，但我很难完全理解这个实现。

 template <class ForwardIt>
 void quicksort(ForwardIt first, ForwardIt last)
 {
    if(first == last) return;
    auto pivot = *std::next(first, std::distance(first,last)/2);
    ForwardIt middle1 = std::partition(first, last, 
                         [pivot](const auto& em){ return em < pivot; });
    ForwardIt middle2 = std::partition(middle1, last, 
                         [pivot](const auto& em){ return !(pivot < em); });
    quicksort(first, middle1);
    quicksort(middle2, last);
 }

谢谢。

Answer 1

第一个分区调用将我们的数据集分成两部分:(1) 小于左侧基准的数据和 (2) 大于或等于右侧基准的数据。

第二个分区将第二个集合 (2) 分成两个集合:(2a) 等于主元的集合和 (2b) 严格大于主元的集合。

然后我们递归 (1) 和 (2b)。基本上，这确保所有等于枢轴的元素都在正确的位置，而不必再次查看。

我不猜测这是否是比规范的单分区实现更好的算法 - 但它就是这样做的。

---

让我们来看一个例子:

initial array:  {3, 4, 5, 3, 4, 6, 4, 1, 4, 8, 8, 1, 6}
                                   ↑
                                   pivot

after 1st part: {3, 3, 1, 1, 4, 5, 4, 6, 4, 4, 8, 8, 6}
                             ↑
                             middle1

after 2nd part: {3, 3, 1, 1, 4, 4, 4, 4, 5, 6, 8, 8, 6}
                 [-----------)           [------------)
                    recurse  ↑           ↑   recurse
                             ↑           ↑
                             middle1     middle2